栈与队列和数组、链表、树这几种数据结构不太一样。栈与队列主要是做为程序员的工具来使用，它们主要做为构思算法的辅助工具，而不是完全的数据存储工具。

它们的生命周期比数组那些要短得多，在程序执行期间它们才会被创建，任务执行完就会被销毁。

一 栈

栈是一种只能在一端进行插入和删除数据的数据结构，这一端被称为栈顶（top）。其特点简单来讲就是先进后出。栈的主要机制可以用数组来实现，当然也可以用链表来实现。

用数组实现栈，并完成常用操作——出栈、入栈、查看元素（只能查看栈顶元素）、判断栈是否为空等操作。

publicclassStackTest{



privatelong[]arr;

// 栈顶

    private int top;

    public StackTest(){

        arr = new long[10];

        top = -1;

    }

    public StackTest(int maxsize){

        arr = new long[maxsize];

        top = -1;

    }

    /**

* 添加数据     * @param value     */

    public void push(int value){

        arr[++top] = value;

    }

    /**

* 移除数据     * @return     */

    public long pop() {

        return arr[top--];

    }

    /**

* 查看数据     * @return     */

    public long peek(){

        return arr[top];

    }

    public boolean isEmpty(){

        return top == -1;

    }

    /***

* 判断是否满了     * @return     */

    public boolean isFull(){

        return top == arr.length-1;

    }

}

栈的所有操作复杂度都为O(1)，栈的操作不依赖栈中元素大小，栈不需要移动和比较操作。

二 队列

队列的特点是先进先出。队列也是用数组来实现。

用数组实现队列，并完成常用操作——出队、入队、查看元素、判断队列是否为空等操作。

publicclassQueueTest{

privatelong[]arr;

// 有效数据的大小

    private int elements;

    // 队头

    private int front;

    // 队尾

    private int end;

    public QueueTest(){

        arr = new long[10];

        elements = 0;

        front = 0;

        end = -1;

    }

    public QueueTest(int maxsize){

        arr = new long[maxsize];

        elements = 0;

        front = 0;

        end = -1;

    }

    /**

* 插入数据     * @param value     */

    public void insert(long value){

        arr[++end] = value;

        elements++;

    }

    /**

* 删除数据     * @return     */

    public long remove(){

        elements--;

        return arr[front++];

    }

    /**

* 查看数据，从对头查看     * @return     */

    public long peek(){

        return arr[front];

    }

    /**

* 判断是否为空     * @return     */

    public boolean isEmpty(){

        return elements == 0;

    }

    public boolean isFull(){

        return elements == arr.length;

    }

}

队列的插入、删除等操作的复杂度都为O(1)。

三 优先级队列

优先级队列和普通队列一样，也是一个队头，一个队尾，从队头移除元素，优先级队列中，数据项是有序的，这样插入数据的时候就会根据某种规则去比较，然后插入到队列合适的位置。因此，优先级队列插入的复杂度为O(N)，删除和查看元素的复杂度为O(1)。

用数组实现优先级队列，并完成常用操作——出队、入队、查看元素、判断队列是否为空等操作。

publicclassFirstQueueTest{

privatelong[]arr;

// 有效数据的大小

    private int elements;

    // 队头

    private int front;

    // 队尾

    private int end;

    public FirstQueueTest(){

        arr = new long[10];

        elements = 0;

        front = 0;

        end = -1;

    }

    public FirstQueueTest(int maxsize){

        arr = new long[maxsize];

        elements = 0;

        front = 0;

        end = -1;

    }

    /**

* 插入数据     * @param value     */

    public void inser(long value){

        if(elements == 0){

            arr[++end] = value;

            elements++;

        }else{

            // 按某种规则进行比较，这里使用value的大小比较，按从小到大排序

            for(int i = elements-1;i>=0;i--){

                if(value<arr[i]){

                    arr[i+1] = arr[i];

                    arr[i] = value;

                }else{

                    arr[i+1] = value;

                    break;

                }

            }

            elements++;

            end++;

        }

    }

    /**

* 删除数据     * @return     */

    public long remove(){

        elements--;

        return arr[front++];

    }

    /**

* 查看数据，从对头查看     * @return     */

    public long peek(){

        return arr[front];

    }

    /**

* 判断是否为空     * @return     */

    public boolean isEmpty(){

        return elements == 0;

    }

    public boolean isFull(){

        return elements == arr.length;

    }

}

四 总结

栈的特点是先进后出，栈只能查看栈顶的一个元素

队列的特点是先进先出，只能查看队头的一个元素

优先级队列插入一条元素，平均需要移动2/N个元素，因此插入的复杂度为O(N)

栈和队列，可以用数组实现，也可以用其他数据结构实现

栈和队列是为了完成某些工作，手动构造的数据结构