引言
队列在日常生活中时一个十分常见的名词，比如去食堂打饭时排队，排在最前面的总是最先取到餐。最晚到达这个队列往往排在队列的最后面。也就是先进先出。这种排队的特点同样也被引入到了计算机中，也就是消息队列，电商在搞大促销的时候，峰值会是平常的好几倍，系统可能会处理不到位，我们一边将系统扩容，一边准备消息队列，将超过系统处理能力的强求放在消息队列中，系统依次处理消息队列中的请求。这种"先进先出"也别引入到了数据结构中，也就是队列。
队列
由上面的讨论我们可以总结出队列的逻辑结构，数据结构中的队列，即是把一个一个的结点按照某种顺序排列，对其处理的过程和日常生活中的对了是一样的。队列规则为:
- 排列顺序: 结点排成一队，后来的排在队尾。
- 处理过程: 在队头处理事件; 队列中有元素一直处理，直至队空或发生中断事件。
队列的定义:
队列(Queue) 是只允许在一端进行操作而在另一端进行删除操作的线性表。删除端被称为"队头"，插入端被称入"队尾"。
与栈的不同之处在于，队列是一种先进先出(First In First Out FIFO)的线性表；与栈相同的是，队列也是一种重要的线性结构。根据队列的定义，队列的基本操作有下列这些:
- 置空队列: 将已有队列置空
- 判空操作: 若队列为空, 则返回的值为true, 否则为false.
- 出队操作: 当队列非空时, 返回队列头元素的值, 修改队列头指针。
- 入队操作: 将结点插入队尾，修改队尾指针
- 取队头元素操作: 当队列非空时, 返回队列头元素的值，但不删除队列头元素。
栈使用top来指向栈顶元素，便于我们实现入栈出栈操作。那对于队列这种一端进一端出的数据结构，我们就需要两个变量来实现入队和出队操作，一个指向队头，一个指向队尾。我们依然用链式存储结构和顺序存储结构来分别实现队列。
顺序队列
对于顺序队列来说有两种类型，一种是无限制的队列, 自动扩容，对入队元素数量无限制。一种是限制容量的队列。对入队元素数量有限制。对于无限制的队列，我们可以仿照之前做线性表的思路，在原先的基础上进行扩展。在原先的基础上重新提供专属于队列的API，然后入队操作和出队操作在原先的基础上做包装。像下面这样:
public class SequenceQueue extends SequenceList{ public void offer(Integer data) { add(data); } public Integer remove() { return remove(size() - 1); } public Integer peek() { if (size() > 0){ return get(0); } return null; } public boolean empty(){ return size() == 0; } // 清空操作 在SequenceList中实现 } 复制代码
那对于容量限制的队列来说就有一个假溢出的问题， 我们举一个例子来说明这个问题，假定限制数组的容量为10，我们每次出队就是让头指针迁移，假设现在头指针已经到了最后，也就是前面的元素已经都出队了，但是有新元素过来仍然不能出队。 即使前面的空间已经废弃掉了，这样队列就只能使用一次，相当鸡肋，所以这种设计存在不合理之处，我们当然不能让队列只使用一次，那我们该如何使用前面的废弃的空间呢？ 有两种思路:
- 队头到队尾的元素向废弃空间平移，但这种方式比较浪费时间。
- 将存储区域看做一个首尾相接的环形区域，入队时判断队列已经满的时候，这个元素就放置在0位置上。
一般我们采用第二种方式来处理队列空间的重复使用问题，在结构上采用这种技巧来存储的队列被称为循环队列。因为循环队列的元素的空间可以被重复使用，除非队列真的全被占用，否则是不会发生上溢出。基本上除了一些简单的应用外，真正实用的顺序队列是循环队列。
其实在这里依然有两种设计, 第一种设计是如果队列全部被占用，那么拒绝入队， 第二种设计就是覆盖掉之前的元素。其实也可以两种设计都要，提供一个方法给调用者，根据参数的不同来采取不同的策略。其实这也是看源码的意义之一，理解设计者的设计思路。下面是我实现的一个简单循环队列:
public class CircularQueue { private int start; private int end; private Integer[] elements; private int maxElements; private boolean full; public CircularQueue(int size) { elements = new Integer[size]; maxElements = size; } public boolean offer(final Integer element){ if(element == null){ // 禁止空元素加入 } // 如果队列已经满了,则 if (isAtFullCapacity()){ remove(); } return false; } public Integer poll(){ if (isEmpty()){ // 或给提示 return null; } return remove(); } /** * 移除元素 */ private Integer remove() { if (isEmpty()){ // 给出提示 } Integer element = elements[start]; if (null != element){ elements[start++] = null; // 说明已经全面出队 if (start >= maxElements){ start = 0; } } return element; } public boolean isEmpty(){ return size() == maxElements; } public boolean isAtFullCapacity() { return size() == maxElements; } public Integer peek(){ if (size() == 0){ return null; } return elements[start]; } // 如何计算size // 循环队列, end到达最后被清置0 // 所以start完全可以大于end // 刚开始start == end // 在一种情况就是 刚超出被覆盖掉 public int size(){ int size = 0; // 说明 if (end < start){ size = maxElements - start + end; }else if (end == start){ size = this.full? maxElements:0; }else { size = end - start; } return size; } public boolean empty(){ return size() == maxElements; } public void clear(){ full = false; start = 0; end = 0; } } 复制代码
链式队列
队列是运算受限的线性表，线性表有两种方式进行存储一种是数组，一种是链表。用链表实现的队列我们一般称之为链队列。 Java中也封装了队列这种数据结构，Queue是接口，LinkedList是他的一个实现类，我们来大致的看一下LinkedList:
Deque 是双向队列，像是栈和队列的集合体，普通队列只能一端进，一端出。而双向队列就可以做到一端进一端出。我们在设计数据结构也可以参考LinkedList的设计。我们再讨论一下队列的结构，顺序队列的相邻可以依靠数组的下标，那么对于链式队列来说就需要再有一个变量来维持各个结点的相邻了。所以链式队列的存储结构就像下面这样:
代码实现如下:
public class LinkedQueue { private Node first; private Node last; private int size; public LinkedQueue() { } private class Node{ private int data; private Node next; public Node(int data , Node next){ this.data = data; this.next = next; } public int getData() { return data; } public Node getNext() { return next; } } public boolean empty(){ return size == 0; } public void clear(){ first = null; last = null; size = 0; } /** * 入队操作 * @param data * @return */ public boolean offer(Integer data) { Node l = last; Node node = new Node(data,null); if (l == null){ first = node; }else { last.next = node; } last = node; size++; return true; } /** * 可扩展该方法, 当头结点为空时, 可返回null,而不是抛出异常 * @return */ public Integer remove() { Node f = first; if (f == null){ // 队列为空 给出警告 } first = first.next; f = null; // help GC size--; return first.data; } public Integer peek() { Node f = first; return f.data; } }
