如果再对线性表增加一些额外的限制和约束，例如，去除普通线性表中通过索引访问数据元素的功能。去除普通线性表中查询某个元素在表中位置的功能，去除普通线性表中可以在任意位置增加、删除元素的功能，而是改为只允许在线性表的某端添加、删除元素，这时候普通线性表就会变为另外两种特殊的线性表：栈和队列。

从逻辑上来看，栈和队列其实是由普通线性表发展而来的，为普通线性表增加一些特殊的限制就可以得到栈和队列了。从功能上看，栈和队列比普通线性表功能相对弱一些，但在一些特殊的场合下，使用栈和队列会更有利，例如，编译器实现函数调用的时候需要使用栈来存储断点，实现递归算法时也需要使用栈来存储。

栈

栈的引文单词是 Stack，它代表一种特殊的线性表，这种线性表只能在固定一端（通常认为是线性表的尾端）进行插入、删除操作。

栈的基本定义

栈是一种数据结构，它代表只能在某一端进行插入、删除操作的特殊线性表，通常就是在线性表的尾端进行插入、删除操作。

对于栈而言，允许进行插入、删除操作的一端被称为栈顶（top），另一端被称为栈底（bottom）。

如果一个栈不包含任何元素，那这个栈就被称为空栈。

从栈顶插入一个元素被称为进栈，讲一个元素插入栈顶被称为“压入栈”————对应的英文说法为 push。

从栈顶删除一个元素被称为出栈，将一个元素从栈顶删除被称为“弹出栈”————对应的英文说法为 pop。

对于元素为 a1，a2，a3，…，an 的栈，假设栈中元素按 a1，a2，a3，…，an 的次序依次进栈，那么 a1 为栈底元素，an 为栈顶元素。出栈时第一个弹出的元素应为栈顶元素，也就是 an。也就是说栈中元素的修改是按后进先出（LIFO）的原则进行的。

归纳起来，可以再对栈下一个定义：栈就是一种后进先出（LIFO）的线性表。

栈的常用操作

栈是一种被限制过的线性表，通常不应该提供线性表中的如下方法：

• 获取指定索引处的元素；
• 按值查找数据元素的位置；
• 向指定索引处插入数据元素；
• 删除指定索引处的数据元素。

从上面这些方法可以看出，栈步应该提供从中间位置访问元素的方法。也就说，栈只允许在栈顶插入、删除元素。

栈的常用操作如下：

• 初始化：通常是一个构造器，用于创建一个空栈；
• 返回栈的长度：该方法用于返回栈中数据元素的个数；
• 入栈：向栈的栈顶插入一个数据元素，栈的长度+1；
• 出栈：从栈的栈顶删除一个数据元素，栈的长度-1，该方法通常返回被删除的元素；
• 访问栈顶元素：返回栈顶的数据元素，但不删除栈顶元素；
• 判断栈是否为空：该方法判断栈是否为空，如果栈为空返回 true，否则返回 false；
• 清空栈：将栈清空。

对于栈这种数据结构而言，入栈、出栈和访问栈顶元素这三个方法就是它作为栈的标志性方法。

类似于线性表既可采用顺序存储的方式来实现，也可使用链式结构来实现，栈同样既可采用顺序结构来存储栈内元素，也可采用链式结构来存储栈内元素。

栈的顺序存储结构及实现

顺序存储结构的栈简称为顺序栈，它利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。栈底位置固定不变，它的栈顶元素可以直接通过顺序栈底层数组的数组元素 arr[size - 1] 来访问。顺序栈中数据元素的物理关系和逻辑关系是一致的，先进栈的元素位于栈底，存储栈底元素的存储位置相对也比较小。

1. 进栈
   对于顺序栈的进栈操作而言，只需将新的数据元素存入栈内，然后再让记录栈内元素个数的变量+1，程序即可再次通过 arr[size-1] 重新访问新的栈顶元素。
   由于顺序栈底层通常会采用数组来保存数据元素，因此可能出现的情况是：当程序试图让一个数据元素进栈时，底层数组已满，那么就必须扩充底层数组的长度来容纳新进栈的数据元素。

2. 出栈
   对于顺序栈的出栈操作而言，需要将栈顶元素弹出栈，程序要做两件事情：

   • 让记录栈内元素个数的变量减 1；
   • 释放数组对栈顶元素的引用。

对于删除操作来说，只要让记录站内元素个数的 size 减少 1，程序即可通过 arr[size - 1] 访问到新的栈顶元素。但不要忘记释放原来栈顶元素的数组引用，否则会引起内存泄漏。

下面程序代码实现了一个顺序栈：

public class SequenceStack<T> {
    private final int DEFAULT_SIZE = 10;
    //保存数组的长度
    private int capacity;
    //定义当底层数组容量不够时，程序每次增加的数组长度
    private int capacityIncrement = 0;
    //定义一个数组用于保存顺序栈的元素
    private Object[] elementData;
    //保存顺序栈中元素的当前个数
    private int size = 0;
    //以默认数组长度创建空顺序栈
    public SequenceStack() {
        capacity = DEFAULT_SIZE;
        elementData = new Object[capacity];
    }
    //以一个初始化元素来创建顺序栈
    public SequenceStack(T element) {
        this();
        elementData[0] = element;
        size++;
    }

    /**
     * 以指定长度的数组来创建顺序栈
     * @param element 指定顺序栈中第一个元素
     * @param initSize 指定顺序栈底层数组的长度
     */
    public SequenceStack(T element, int initSize) {
        this.capacity = initSize;
        elementData = new Object[capacity];
        elementData[0] = element;
        size++;
    }

    /**
     * 以指定长度的数组来创建顺序栈
     * @param element 指定顺序栈中第一个元素
     * @param initSize 指定顺序栈底层数组的长度
     * @param capacityIncrement 指定当顺序栈底层数组不够时，底层数组每次增加的长度
     */
    public SequenceStack(T element, int initSize, int capacityIncrement) {
        this.capacity = initSize;
        this.capacityIncrement = capacityIncrement;
        elementData = new Object[capacity];
        elementData[0] = element;
        size++;
    }
    //获取顺序栈的大小
    public int length() {
        return size;
    }
    //入栈
    public void push(T element) {
        ensureCapacity(size + 1);
        elementData[size++] = element;
    }
    //很麻烦，而且性能很差
    private void ensureCapacity(int minCapacity) {
        if (minCapacity > capacity) {
            if (capacityIncrement > 0) {
                while (capacity < minCapacity) {
                    //不断地将capacity长度加capacityIncrement
                    //直到capacity大于minCapacity为止
                    capacity += capacityIncrement;
                }
            } else {
                //不断第将capacity*2，直到capacity大于minCapacity为止
                while (capacity < minCapacity) {
                    capacity <<= 1;
                }
            }
            elementData = Arrays.copyOf(elementData, capacity);
        }
    }
    //出栈
    public T pop() {
        T oldValue = (T)elementData[size - 1];
        //释放栈顶元素
        elementData[--size] = null;
        return oldValue;
    }
    //返回栈顶元素，但不删除栈顶元素
    public T peek() {
        return (T)elementData[size - 1];
    }
    //判断顺序栈是否为空栈
    public boolean empty() {
        return size == 0;
    }
    //清空顺序栈
    public void clear() {
        //将底层数组所有元素赋为null
        Arrays.fill(elementData, null);
        size = 0;
    }
    @Override
    public String toString() {
        if (size == 0) {
            return "[]";
        } else {
            StringBuilder sb = new StringBuilder("[");
            for (int i = size - 1;i > -1;i--) {
                sb.append(elementData[i].toString() + ",");
            }
            int len = sb.length();
            return sb.delete(len - 2, len).append("]").toString();
        }
    }
}

从上面程序可以看出，当采用基于数组的方式来实现顺序栈时，程序比普通线性表更简单。这复合前面介绍的：从功能上来看，栈比普通线性表的功能更弱；栈是一种被限制过的线性表，只能从栈顶插入、删除元素。

下面程序简单测试了上面的顺序栈：

public class SequenceStackTest {
    public static void main(String[] args) {
        SequenceStack<String> stack = new SequenceStack<>();
        //不断的入栈
        stack.push("aaaa");
        stack.push("bbbb");
        stack.push("cccc");
        stack.push("dddd");
        System.out.println(stack);
        //访问栈顶元素
        System.out.println("访问栈顶元素：" + stack.peek());
        //弹出一个元素
        System.out.println("第一次弹出栈顶元素：" + stack.pop());
        //再次弹出一个元素
        System.out.println("第二次弹出栈顶元素：" + stack.pop());
        System.out.println("两次pop之后的栈：" + stack);
    }
}

运行上面的程序，结果如下：

[dddd,cccc,bbbb,aaa]
访问栈顶元素：dddd
第一次弹出栈顶元素：dddd
第二次弹出栈顶元素：cccc
两次pop之后的栈：[bbbb,aaa]

栈的链式存储结构及实现

类似地，程序可以采用单链表来保存栈中所有元素，这种链式结构的栈也被称为链栈。对于链栈而言，栈顶元素不断地改变，程序只要使用一个 top 引用来记录当前的栈顶元素即可。top 引用变量永远引用栈顶元素，再使用一个 size 变量记录当前栈中包含多少元素即可。

1. 进栈
   对于链栈的进栈操作，程序只需要做如下两件事情：

   • 让 top 引用指向新添加的元素，新元素的 next 引用指向原来的栈顶元素；
   • 让记录栈内元素个数的 size 变量 +1。

2. 出栈
   对于链栈的出栈操作，需要将栈顶元素弹出栈，程序需要做两件事情：

   • 让 top 引用指向原栈顶元素的下一个元素，并释放原来的栈顶元素；
   • 让记录栈内元素个数的变量 -1。

下面程序代码实现了一个链栈：

public class LinkStack<T> {
    //定义一个内部类Node,Node实例代表链栈的节点
    private class Node {
        //保存节点的数据
        private T data;
        //指向下个节点的引用
        private Node next;
        //无参数的构造器
        public Node(){
        }
        //初始化全部属性的构造器
        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
    //保存该链栈的栈顶元素
    private Node top;
    //保存该链栈中已包含的节点数
    private int size;
    //创建空链栈
    public LinkStack() {
        //空链栈，top的值为null
        top = null;
    }
    //以指定数据元素来创建链栈，该链栈只有一个元素
    public LinkStack(T element) {
        top = new Node(element, null);
        size++;
    }
    //返回栈的长度
    public int length() {
        return size;
    }
    //进栈
    public void push(T element) {
        //让top指向新创建的元素，新元素的next引用指向原来的栈订元素
        top = new Node(element, top);
        size++;
    }
    //出栈
    public T pop() {
        Node oldTop = top;
        //让top引用指向原栈顶元素的下一个元素
        top = top.next;
        //释放原栈顶元素的next引用
        oldTop.next = null;
        size--;
        return oldTop.data;
    }
    //访问栈顶元素，但不删除栈顶元素
    public T peek() {
        return top.data;
    }
    //判断是否为空栈
    public boolean empty() {
        return size == 0;
    }
    //清空链栈
    public void clear() {
        top = null;
        size = 0;
    }
    @Override
    public String toString() {
        if (empty()) {
            return "[]";
        } else {
            StringBuilder sb = new StringBuilder("[");
            for (Node current = top;current != null;current = current.next) {
                sb.append(current.data.toString() + ",");
            }
            int len = sb.length();
            return sb.delete(len - 2, len).append("]").toString();
        }
    }
}

采用类似单链表的方式来实现链栈也比较容易，下面程序简单测试了上面栈的功能：

public class LinkStackTest {
    public static void main(String[] args) {
        LinkStack<String> stack = new LinkStack<>();
        //不断的入栈
        stack.push("aaaa");
        stack.push("bbbb");
        stack.push("cccc");
        stack.push("dddd");
        System.out.println(stack);
        //访问栈顶元素
        System.out.println("访问栈顶元素：" + stack.peek());
        //弹出一个元素
        System.out.println("第一次弹出栈顶元素：" + stack.pop());
        //再次弹出一个元素
        System.out.println("第二次弹出栈顶元素：" + stack.pop());
        System.out.println("两次pop之后的栈：" + stack);
    }
}

经过上面介绍可以看出，为了实现栈这种数据结构，程序有两种实现选择：顺序栈和链栈。由于栈不需要实现随机存、取的功能，它只需从栈顶插入、删除元素，因此顺序结构所提供的高效存、取就没有太大的价值了，即使采用链式结构的实现，程序同样可以高效的出栈、入栈。

对于链栈而言，站内包含几个元素，底层链式结构就只需要保存几个节点，每个节点需要额外添加一个 next 引用，这会引起部分空间的浪费。但对于顺序栈来说，程序开始就需要再底层为它开辟一块连续的内存（数组），这种空间浪费其实更大。从空间利用率的角度来看，链栈的空间利用率比顺序栈的空间利用率要高一些。

Java 集合中的栈

栈也是一种常用的数据结构，因此 Java 集合框架也提供了栈来共开发者使用。对于 Java 集合而言，它并未专门提供一个 Stack 接口，再为该接口提供顺序栈、链栈两种实现。

但 Java 集合实际上提供了以下两种栈供开发者使用：

• java.util.Stack：它就是一个最普通的顺序栈，底层基于数组实现。这个 Stack 类是线程安全的，在多线程环境下也可放心使用；
• java.util.LinkedList：前面已经介绍过，LinkedList 是一个双向链表。但如果查看该类的 API 将会发现，它同样提供了 push()、pop()、peek() 等方法，这表名 LinkedList 其实还可以当成栈来使用。LinkedList 代表栈的链式实现，但它是线程不安全的，如果需要再多线程环境下使用，应该使用 Collections 类的工具方法将其“改造”成线性安全的类。

队列

队列（Queue）是另一种被限制过的线性表，它使用固定的一端来插入数据元素，另一端只用于能删除元素。也就是说，队列中元素的移动方向总是固定的，就像排队购物一样：先进入队伍的顾客先获得服务，队伍中的顾客总是按固定方向移动，只有当排在自己前面的所有顾客获得服务之后，当前顾客才会获得服务。

队列的基本定义

队列是一种特殊的线性表，它只允许再表的前端（front）进行删除操作，只允许再表的后端（rear）进行插入操作。进入插入操作的端称为队尾，进行删除操作的端称为对头。

如果队列中不包含任何元素，该队列就被称为空队列。

对于一个队列来说，每个元素总是从队列的 rear 端进入队列，然后等待该元素之前的所有元素出队之后，当前元素才能出队。因此，把队列简称为先进先出（FIFO）的线性表。

队列的常用操作

队列同样是一种被限制过的线性表，通常不应该提供线性表中的如下方法：

• 获取指定索引处的元素；
• 按值查找数据元素的位置；
• 向指定索引处插入数据元素；
• 删除指定索引处的数据元素。

从上面这些方法可以看出，队列不应该提供从中间任意位置访问元素的方法。也就是说，队列只允许在队列的前端（front）删除元素，只允许再队列的后端（rear）插入元素。

队列的常用操作如下：

• 初始化：通常是一个构造器，用于创建一个空队列；
• 返回队列的长度：该方法用于返回队列中数据元素的个数；
• 加入元素：向队列的 front 端插入一个数据元素，队列的长度+1；
• 删除元素：从队列的 rear 端删除一个数据元素，队列长度-1，该方法返回被删除的元素；
• 访问队列的前端元素：返回队列的 front 端的数据元素，但不删除该元素；
• 判断队列是否为空：该方法判断队列是否为空，如果队列为空返回 true，否则返回 false；
• 清空队列：将队列清空。

对于队列这种数据结构，加入元素、删除元素和访问队列的前端元素的方法就是它作为队列的标志性方法。

类似于线性表既可以采用顺序存储的方式来实现，也可链式结构来实现，队列同样既可采用顺序结构来存储队列内元素，也可以采用链式结构来存储队列内元素。

队列的顺序存储结构及实现

系统采用一组地址连续的存储单元依次存放队列从 rear 端到 front 端的所有数据元素，程序只需 front 和 rear 两个整型变量来记录队列 front 端的元素索引、rear 端的元素索引。

顺序队列的 front 总是保存着队列中即将出队列的元素的索引，顺序队列中的 rear 总是保存着下一个即将进入队列的元素的索引。队列中元素的个数为 rear-front。

对于顺序队列而言，队列底层将采用数组来保存队列元素，每个队列元素再数组中的位置固定不变的，变的只是 rear 和 front 两个整型变量。但有元素进入队列时，rear 变量的值+1；当有元素从队列中移除时，front 变量的只+1。

下面程序实现了一个简单的顺序队列：

public class SequenceQueue<T> {
    private final int DEFAULT_SIZE = 10;
    //保存数组的长度
    private int capacity;
    //定义一个数组用于保存顺序队列的元素
    private Object[] elementData;
    //保存顺序队列中的对头和队尾元素索引
    private int front = 0;
    private int rear = 0;
    //以默认数组长度创建空顺序队列
    public SequenceQueue() {
        capacity = DEFAULT_SIZE;
        elementData = new Object[capacity];
    }
    //以一个初始化元素创建顺序队列
    public SequenceQueue(T element) {
        this();
        elementData[0] = element;
        rear++;
    }

    /**
     * 以指定长度的数组来创建顺序队列
     * @param element 指定顺序队列中第一个元素
     * @param initSize 指定顺序队列底层数组的长度
     */
    public SequenceQueue(T element, int initSize) {
        this.capacity = initSize;
        elementData = new Object[capacity];
        elementData[0] = element;
        rear++;
    }
    //获取顺序队列的大小
    public int length() {
        return rear - front;
    }
    //插入队列
    public void add(T element) {
        if (rear > capacity - 1) {
            throw new IndexOutOfBoundsException("队列已满的异常");
        }
        elementData[rear++] = element;
    }
    //移除队列
    public T remove() {
        if (empty()) {
            throw new IndexOutOfBoundsException("空队列的异常");
        }
        //保留队列的rear端的元素的值
        T oldValue = (T)elementData[front];
        //释放队列的 rear 端的元素
        elementData[front++] = null;
        return oldValue;
    }
    //返回队顶元素，但步删除队顶元素
    public T element() {
        if (empty()) {
            throw new IndexOutOfBoundsException("空队列的异常");
        }
        return (T)elementData[front];
    }
    //清空顺序队列
    public void clear() {
        //将底层数组所有元素赋为 null
        Arrays.fill(elementData, null);
        front = 0;
        rear = 0;
    }
    //判断顺序队列是否为空队列
    public boolean empty() {
        return front == rear;
    }
    @Override
    public String toString() {
        if (empty()) {
            return "[]";
        } else {
            StringBuilder sb = new StringBuilder("[");
            for (int i = front;i < rear;i++) {
                sb.append(elementData[i].toString() + ",");
            }
            int len = sb.length();
            return sb.delete(len - 2, len).append("]").toString();
        }
    }
}

上面程序使用一个固定长度数组来实现队列，队列元素在 elementData 中的位置不会改变，改变的是 front、rear 两个变量。使用下面程序来测试上面的队列类：

public class SequenceQueueTest {
    public static void main(String[] args) {
        SequenceQueue<String> queue = new SequenceQueue<>();
        //依次将4个元素加入队列
        queue.add("aaaa");
        queue.add("bbbb");
        queue.add("cccc");
        queue.add("dddd");
        System.out.println(queue);
        System.out.println("访问队列的 front 端元素：" + queue.element());
        System.out.println("移除队列的 front 端元素：" + queue.remove());
        System.out.println("移除队列的 front 端元素：" + queue.remove());
        System.out.println("两次调用 remove 方法后的队列：" + queue);
    }
}

运行结果如下：

[aaaa,bbbb,cccc,ddd]
访问队列的 front 端元素：aaaa
移除队列的 front 端元素：aaaa
移除队列的 front 端元素：bbbb
两次调用 remove 方法后的队列：[cccc,ddd]

对于上面这个队列的实现，由于数据元素再底层数组的位置是固定的，改变的只是 rear、front 两个整型的值。这个队列在依次添加满整个队列元素之后，再依次移除队列中的所有元素。此时，队尾 rear 指针固定再队尾不变，而对头 front 指针则依次向后移动，当所有元素都出队列之后，此时 front、rear 都指向了队尾。此时，队列其实是空的，但是，此时已经不能在往队列中添加元素了，造成了“假满”的现象。

由于 rear 等于该队列底层的容量 capacity，如果此时试图向队列添加元素，将会引起“队列已满”的异常。这其实是一种“假满”的现象，此时该队列底层的数组依然有 capacity 个空位可存储数据元素，但程序已经加不进去了。

对于“假满”问题，程序有如下解决方法：

• 每次将元素移除队列时都将队列中的所有元素向 front 端移动一位，这种方式下 front 值永远为 0，元素插入队列时 rear 值+1，元素移除队列时 rear-1。但这种方式非常浪费时间，因为每次将元素从队列移除时都需进行“整体搬家”；
• 将数组存储区看成一个首尾相接的环形区域，当存放到数组的最大地址之后，rear 的值再次变为 0。采用这种技巧存储的队列称为循环队列。

循环队列

为了重新利用顺序队列底层数组中已删除元素所占用的空间，消除可能出现的“假满”现象，可以将顺序队列改进为循环队列。

循环队列的是首尾相连的队列：当 front、rear 变量达到底层数组的 capacity-1 之后，再前进一位就自动变成 0。

对于循环队列而言，不管队列是空还是满，都会出现一个情况：front == rear。如果底层数组中 elementData[front] == null 表明此时队列为空，否则表明该队列已满。

掌握上面理论之后，下面用 Java 代码来实现一个循环队列：

public class LoopQueue<T> {
    private final int DEFAULT_SIZE = 10;
    //保存数组的长度
    private int capacity;
    //定义一个数组用于保存循环队列的元素
    private Object[] elementData;
    //保存循环队列中的对头和队尾元素索引
    private int front = 0;
    private int rear = 0;
    //以默认数组长度创建空循环队列
    public LoopQueue() {
        capacity = DEFAULT_SIZE;
        elementData = new Object[capacity];
    }
    //以一个初始化元素创建循环队列
    public LoopQueue(T element) {
        this();
        elementData[0] = element;
        rear++;
    }

    /**
     * 以指定长度的数组来创建循环队列
     * @param element 指定循环队列中第一个元素
     * @param initSize 指定循环队列底层数组的长度
     */
    public LoopQueue(T element, int initSize) {
        this.capacity = initSize;
        elementData = new Object[capacity];
        elementData[0] = element;
        rear++;
    }
    //获取循环队列的大小
    public int length() {
        if (empty()) {
            return 0;
        }
        return rear > front ? rear - front : capacity - (front - rear);
    }
    //插入队列
    public void add(T element) {
        if (rear == front && elementData[front] != null) {
            throw new IndexOutOfBoundsException("队列已满的异常");
        }
        elementData[rear++] = element;
        //如果rear已经到头，那就转头
        rear = rear == capacity ? 0 : rear;
    }
    //移除队列
    public T remove() {
        if (empty()) {
            throw new IndexOutOfBoundsException("空队列的异常");
        }
        //保留队列的rear端的元素的值
        T oldValue = (T)elementData[front];
        //释放队列的 rear 端的元素
        elementData[front++] = null;
        //如果front已经到头，那就转头
        front = front == capacity ? 0 : front;
        return oldValue;
    }
    //返回队顶元素，但步删除队顶元素
    public T element() {
        if (empty()) {
            throw new IndexOutOfBoundsException("空队列的异常");
        }
        return (T)elementData[front];
    }
    //清空循环队列
    public void clear() {
        //将底层数组所有元素赋为 null
        Arrays.fill(elementData, null);
        front = 0;
        rear = 0;
    }
    //判断循环队列是否为空队列
    public boolean empty() {
        //rear==front且rear处的元素为null
        return front == rear && elementData[rear] == null;
    }
    @Override
    public String toString() {
        if (empty()) {
            return "[]";
        } else {
            StringBuilder sb = new StringBuilder("[");
            //如果front < rear，有效元素就是 front 到 rear 之间的元素
            if (front < rear) {
                for (int i = front;i < rear;i++) {
                    sb.append(elementData[i].toString() + ",");
                }
            //如果front >= rear，有效元素就是 front 到 capacity 之间的元素
            } else {
                for (int i = front;i < capacity;i++) {
                    sb.append(elementData[i].toString() + ",");
                }
                for (int i = 0;i < rear;i++) {
                    sb.append(elementData[i].toString() + ",");
                }
            }
            int len = sb.length();
            return sb.delete(len - 2, len).append("]").toString();
        }
    }
}

上面的程序就将一个普通队列升级成了循环队列。程序控制 front、rear 到了 capacity 之后就自动回到 0，从而实现将顺序队列升级为循环对的功能。

public class LoopQueueTest {
    public static void main(String[] args) {
        LoopQueue<String> queue = new LoopQueue<>("aaaa", 3);
        //添加两个元素
        queue.add("bbbb");
        queue.add("cccc");
        //此时队列已满
        System.out.println(queue);
        //删除一个元素后，队列可以再添加一个元素
        queue.remove();
        System.out.println("删除一个元素后的队列：" + queue);
        //再次添加一个元素，此时队列又满
        queue.add("dddd");
        System.out.println(queue);
        System.out.println("队列满时的长度：" + queue.length());
        //删除一个元素后，队列可以再多加一个元素
        queue.remove();
        //再次加入一个元素，此时队列又满
        queue.add("eeee");
        System.out.println(queue);
    }
}

下面是运行结果：

[aaaa,bbbb,ccc]
删除一个元素后的队列：[bbbb,ccc]
[bbbb,cccc,ddd]
队列满时的长度：3
[cccc,dddd,eee]

队列的链式存储结构及实现

类似于使用链式结构保存线性表，也可以采用链式结构来存储队列的各元素，采用链式存储结构的队列也被称为链队列。

对于链队列而言，由于程序需要从 rear 端添加元素，然后从 front 端移除元素，因此考虑对链队列增加 front、rear 两个引用变量，使它们分别指向链队列的头、尾两个节点。

1. 插入队列
   对于插入队列而言，插入操作的实现非常简单，只要将创建一个新街点，让原 rear 节点的 next 引用指向新的节点，再让 rear 引用指向该新节点。
2. 移除队列
   对于链队列而言，移除操作的实现也非常简单，只要让 front 引用指向原 front 所引用节点的下一个节点即可。当然，不要忘记释放原 front 节点的引用。

掌握了上面理论后，接下来使用 Java 程序实现一个简单的链队列。

public class LinkQueue<T> {
    //定义一个内部类Node，Node实例代表链队列的节点
    private class Node {
        //保存节点的数据
        private T data;
        //指向下个节点的引用
        private Node next;
        //无参数的构造器
        public Node() {
        }
        //初始化全部属性的构造器
        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
    //保存该链队列的头节点
    private Node front;
    //保存该链队列的尾节点
    private Node rear;
    //保存该链队列中已包含的节点数
    private int size;
    //创建空链队列
    public LinkQueue() {
        //空链队列，front和rear都是null
        front = null;
        rear = null;
    }
    //以指定数据元素来创建链队列，该链队列只有一个元素
    public LinkQueue(T element) {
        front = new Node(element, null);
        //只有一个节点，front、rear都指向该节点
        rear = front;
        size++;
    }
    //返回链队列的长度
    public int length() {
        return size;
    }
    //将新元素加入队列
    public void add(T element) {
        //如果该链队列还是空链队列
        if (front == null) {
            front = new Node(element, null);
            //只有一个节点，front、rear都指向该节点
            rear = front;
        } else {
            //创建新节点
            Node newNode = new Node(element, null);
            //让尾节点的next指向新增的节点
            rear.next = newNode;
            //以新节点作为新的尾节点
            rear = newNode;
        }
        size++;
    }
    //删除队列front端的元素
    public T remove() {
        Node oldFront = front;
        front = front.next;
        oldFront.next = null;
        size--;
        return oldFront.data;
    }
    //获取链式队列中最后一个元素
    public T element() {
        return rear.data;
    }
    //判断链式队列是否为空队列
    public boolean empty() {
        return size == 0;
    }
    //清空链队列
    public void clear() {
        front = null;
        rear = null;
        size = 0;
    }
    @Override
    public String toString() {
        //链队列为空链队列时
        if (empty()) {
            return "[]";
        } else {
            StringBuilder sb = new StringBuilder("[");
            for (Node current = front;current != null;current = current.next) {
                sb.append(current.data.toString() + ",");
            }
            int len = sb.length();
            return sb.delete(len - 2, len).append("]").toString();
        }
    }
}

上面程序实现了链式队列插入元素、删除元素的关键代码：插入元素的关键就是在 rear 端添加一个节点，删除元素的关键就是再 front 端移除一个节点。下面程序测试了上面的链队列。

public class LinkQueueTest {
    public static void main(String[] args) {
        LinkQueue<String> queue = new LinkQueue<>("aaaa");
        //添加两个元素
        queue.add("bbbb");
        queue.add("cccc");
        System.out.println(queue);
        //删除一个元素后
        queue.remove();
        System.out.println("删除一个元素后的队列：" + queue);
        //再次添加一个元素
        queue.add("dddd");
        System.out.println("再次添加元素后的队列：" + queue);
        //删除一个元素后，队列可以再多加一个元素
        queue.remove();
        //再次放入一个元素
        queue.add("eeee");
        System.out.println(queue);
    }
}

上面程序创建了一个链队列，链队列不会出现队列“满”的情形，因此程序可以不受任何限制地向链队列中添加元素。

Java 集合中的队列

从 JDK1.5 开始，Java 的集合框架中提供了一个 Queue 接口，该接口代表了一个队列，实现该接口的类可以当成队列使用。Queue 里包含了 6 个方法，用于代表队列所包含的 3 个标志性方法，如下所示：

• 插入：在队列的 rear 端插入元素；
• 移除：在队列的 front 端删除元素；
• 访问：访问队列的 front 端的元素。

Java 为上面每个方法都提供了 2 个版本：返回特殊值的版本和抛出异常的版本，这样就产生了 6 个方法。关于 Queue 接口里定义的 6 个方法的说明如下表：

Java 提供了一个 Queue 接口，并为该接口提供了众多的实现类：ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue、PriorityQueue、ConcurrentLinkedQueue 和 SynchronousQueue，它们都是线程安全的队列。

ArrayBlockingQueue 和 LinkedBlockingQueue 一个代表顺序存储结构的队列，一个代表链式存储结构的队列，而且它们都是线程安全的。可以想象，LinkedBlockingQueue 队列的吞吐量通常比 ArrayBlockingQueue 队列高，但在大多数并发应用程序中，LinkedBlockingQueue 的性能要低。

除了 LinkedBlockingQueue 队列之外，JDK 还提供了另外一种队列 ConcurrentLinkedQueue，它基于一种先进的、无等待（wait-free）队列算法实现。

除了上面这些实现类之外，JDK1.5 还为 Queue 接口提供了一个 Deque 接口，这个接口代表另一种特殊的队列————双向队列。

双向队列

双向队列（由英文单词 Deque 代表）代表一种特殊的队列，它可以在两端同时进行插入、删除操作。

对于双向队列，由于它可以从两端分别进行插入、删除操作，如果程序将所有的插入、删除操作固定再一端进行，这个双向队列就变成前面介绍的栈了。

双向队列（Deque）既可说是 Queue 的子接口，也可说是 Stack（JDK 并未提供这个接口）的子接口。因此，Deque 既可当队列使用，也可当成栈使用。

由此可见，Duque 其实就是 Queue 和 Stack 混合而成的一种特殊线性表，完全可以参考前面的 Queue、Stack 的实现类来实现此处的 Deque，此处不再赘述。

JDK 虽然提供了一个古老的 Stack 类，但现在已经不再推荐开发者使用这个古老的“栈”实现，而是推荐使用 Deque 实现类作为“栈”使用。

JDK 为 Deque 提供了 ArrayDeque、LinkedBlockingDeque、LinkedList 这 3 个实现类。其中，ArrayDeque 代表顺序存储结构的双向队列，LinkedList 则代表链式存储结构的双向队列，LinkedBlockingDeque 其实是一个线程安全的、链式结构的双向队列。

前面还提到，LinkedList 代表一种双向、链式存储结构的循环线性表，这里又提到 LinkedList 代表线程安全的、链式结构的双向队列，由此可见 LinkedList 实在是一个功能非常强大的集合类。事实上，LinkedList 几乎是 Java 集合框架中方法最多的类。

从上面的表可以看出，JDK 提供的工具类确实非常强大，它分别为线性表、队列、栈 3 种数据结构提供了两种实现：顺序结构和链式结构。虽然 LinkedList 工具类非常强大，它既可以当成线性表使用，也可以当成栈使用，还可以当成队列使用，但对于大部分程序而言，使用 ArrayList、ArrayDeque 的性能比 LinkedList 更好。

本文转载自：《疯狂Java 突破程序员基本功的16课》第十章 栈和队列