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

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

一 栈

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

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

public class StackTest {        private long[] 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)，栈的操作不依赖栈中元素大小，栈不须要挪动和比拟操作。

二 队列

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

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

public class QueueTest {    private long[] 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)。

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

public class FirstQueueTest {    private long[] 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;    }}

四 总结

  1. 栈的特点是先进后出，栈只能查看栈顶的一个元素
  2. 队列的特点是先进先出，只能查看队头的一个元素
  3. 优先级队列插入一条元素，均匀须要挪动2/N个元素，因而插入的复杂度为O(N)
  4. 栈和队列，能够用数组实现，也能够用其余数据结构实现
  5. 栈和队列是为了实现某些工作，手动结构的数据结构

点关注、不迷路

如果感觉文章不错，欢送关注、点赞、珍藏，你们的反对是我创作的能源，感激大家。

如果文章写的有问题，请不要悭吝，欢送留言指出，我会及时核查批改。

如果你还想更加深刻的理解我，能够微信搜寻「Java旅途」进行关注。回复「1024」即可取得学习视频及精美电子书。每天7:30准时推送技术文章，让你的下班路不在孤单，而且每月还有送书流动，助你晋升硬实力！