数据结构与算法--队列
队列如其名，就是一列元素。举个我们熟知的场景，火车站窗口购票，排队买票的人们就组成一个队列。先去的人排在前头，后去的站在队伍后面。买票的顺序也是队伍头的人买了离开后，才轮到下一个。什么？你为了先买票想在队伍前头插入，对不起不允许的，请排队。新来的只能站在队列末端，只是最后一个才离开。队列是一种只允许在一端插入，在另一端删除的数据结构。能进行数据插入的那端是队尾，进行数据删除的那端是队列头。显然队列是先进先出的（First In First Out），就是平常说的FIFO。
队列也是一种线性表，可以用顺序存储或链式存储。先看使用数组实现的顺序存储。
队列的数组实现
撇开数组容量限制不谈，光是出列（删除队列头元素）就很费劲——删除a[0]处元素后将引起其后所有元素的移动，时间复杂度为O(n)。有没有办法降低到O(1)呢？
可能会想到：那我出列就出列，你后面的元素不要动嘛！这样会造成什么后果？前面的人走了留下了大片可用的空间，后面的元素占据着接近数组末尾的位置。如果数组最后一个位置被占用了，后面的元素不能插入进来了。这不合理嘛，明明前面还有那么多空！这就好比你上课迟到了，跑到教室门口发现教室后排都坐满了，但是教室第一二排还空着没人坐。你总不能和老师说：”老师，没位置了。“老师肯定会把你安排到前排去坐的。
我们可由此受到启发：出列后留下的空，由新来的去补上。这样就有可能a[0]处站的是队列的最后一个元素。这就意味着一旦到达末尾我们就又回到开头，这不就是循环结构嘛。所以这样的队列称为循环队列。队列尾可以存在于数组中的任何位置，所以我们需要使用一个标志物记住队列尾的所在位置，用last表示；同样，队列头也可以在数组中的任何位置，使用一个标志物记住队列头的所在位置，用first表示。
first和last的具体含义是什么呢？假如first是队列第一个元素的下标，last是队列最后一个元素的下标。那么当第一个元素入列后，first和last应该相同都为0，表示只有一个元素时，first和last指向同一个元素。所以刚开始还没元素入列时（空列），因为入列只涉及last的自增，last应初始化为-1，而first被初始化为0。
再看，队列满时满足什么条件？很明显当first和last所在位置相邻时，相邻什么意思？由于是循环队列，相当于把这个数组首尾相连，当last的下一位置刚好是first的时候（想象成循环结构，数组的最后一个位置的下一个位置就是数组的第一个位置），last与first之间已无空余空间，所以不能再插入元素，队列满了。看下图，这是last与first相邻的两种情况。
有可能last在first的前面，则last + 1 = first，而因为last + 1 < a.lebgth故有(last + 1) % length = last + 1；也有可能last在first的后面，last比first大了一圈，由于last + 1== a.length，则(last + 1) % a.length刚好等于0，与first值一样。两种情况可以用一个式子统一起来，只用判断以下条件即可：
(last + 1) % a.length == first
回到first和last的含义以及其初始值。first = 0, last = -1，由于在入列时肯定会先判断是否已满后才进行后续操作，就像下面一样：
if ((last + 1) % a.length == first) {
throw new RuntimeException("已达到最大容量，不可再入列！");
// 其他操作
}
这时要入列第一个元素时，我们发现last和first的值代入刚好满足这个条件。这就意味着，当last和first表达的是上述意思时，一个元素都不能入列！
所以换个理解方式咯。如果last表示的不是最后一个元素所在位置，而是最后一个元素位置的下一个位置。因为当第一个元素入列后，first指向数组下标0位置，last应该指向下标1的位置，所以空列时last初始化为0，first应该初始化为0。而当队列满时，条件也变成了last == first，表示两个指针相遇。这又回到了上面说的困境，在第一个元素想入列时，经判断满足条件，被告知不能入列！
有没有什么办法可以解决上面的困境呢？假设我们保持first表示第一个元素所在的位置，last表示最后一个元素位置的下一个位置。则空列时first = last = 0。而将判断满的条件改一下，改成(last + 1) % a.length == first，则可以在入列第一个元素时完美避开这个条件。相应地，付出的代价就是数组的空间没有使用完。即使队列满时，也还有一个空余空间，last就指向它。 任何时候last所在的位置都是空的，没有任何元素填充。
好了搞清楚last和first是啥了，也清楚了队列满时的条件，是时候放代码了。
package Chap4;
import java.util.Iterator;
public class ArrayQueue<Item> implements Iterable<Item> {
private Item[] a;
// 指向队列的第一个元素
private int first; // 默认值0
// 指向最后一个元素的下一位置
private int last; // 默认值0
public ArrayQueue(int maxsize) {
if (maxsize <= 0) {
maxsize = 512;
}
a = (Item[]) new Object[maxsize];
}
public ArrayQueue() {
this(512);
}
public boolean isEmpty() {
return size() == 0;
}
public int size() {
/* 1. last > first时：长度应该是last -first
而(last - first + a.length) % a.length
即(last - first) % a.length + 0 = last -first
2. last < first时：长度应该是last - first + a.length
而(last - first + a.length) % a.length
即last - first + a.length
综上，统一使用下面的表达式
*/
return (last - first + a.length) % a.length;
}
public void enqueue(Item item) {
// 先判断是否已满，无论何时，即使满时，last所在都是空
if ((last + 1) % a.length == first) {
throw new RuntimeException("已达到最大容量，不可再入列！");
}
a[last] = item;
// 当新元素入列成占据数组最后一个位置时，last应该变成0（循环结构，数组最后一个位置的下一个位置就是数组的第一个位置）；其余情况保持自增
last = (last + 1) % a.length;
}
public Item dequeue() {
Item item = a[first];
// 既然弹出，此处应变成null
a[first] = null;
// first的更新和last一样的
first = (first + 1) % a.length;
return item;
}
// 获得队头元素
public Item getHead() {
return a[first];
}
// 清空相当于初始化到原来的样子
public void clear() {
for (int i = 0; i < a.length; i++) {
a[i] = null;
}
first = 0;
last = 0;
}
@Override
public Iterator<Item> iterator() {
return new Iterator<Item>() {
private int current = first;
@Override
public boolean hasNext() {
// 1. 空队列时（first = last = 0）
// 2. first在last前一个位置，刚好访问了最后一个元素。之后和last相等时结束遍历
return current != last;
}
@Override
public Item next() {
Item item = a[current];
current = (current + 1) % a.length;
return item;
}
};
}
@Override
public String toString() {
Iterator<Item> it = iterator();
if (!it.hasNext()) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append("[");
while (true) {
Item item = it.next();
sb.append(item);
if (!it.hasNext()) {
return sb.append("]").toString();
}
sb.append(", ");
}
}
public static void main(String[] args) {
ArrayQueue<String> a = new ArrayQueue<>();
a.enqueue("a");
a.enqueue("b");
a.enqueue("c");
a.enqueue("d");
System.out.println(a);
a.dequeue(); // a
a.dequeue(); // b
for (String each: a) {
System.out.print(each+" "); // c d
}
a.clear();
System.out.println("\n"+a.isEmpty()); // true
a.enqueue("tiger");
a.enqueue("lion");
System.out.println("head: "+a.getHead()); // tiger
}
}
相信经过上面的讲解，enqueue和dequeue方法理解起来都不太难了，需要注意的是last和first的更新方式，注释里说明了当新元素入列成占据数组最后一个位置时，last应该变成0（循环结构，数组最后一个位置的下一个位置就是数组的第一个位置）；其余情况保持自增。用一句last = (last + 1) % a.length统一的这两种情况。同理在dequeue方法中first的更新方式和last一样。
然后是iterator中hasNext方法的判断，从first开始遍历，不断自增，只要first还不等于last，说明还没遍历完，当first在last前一个位置，刚好访问到了最后一个元素，之后和last相等，结束遍历。
最后看看如何队列的长度，由于使用了两个指针，本着节约内存的考虑，就不再新增一个变量专门保存队列的长度了。画画图可以轻松看出。
情况1长度就一段即last - first ；情况2长度有两段，一段长度为last，另一段长度是a.length - first，相加即是队列的长度。为了统一这两种情况，使用(last - first + a.length) % a.length就行了。至于为什么可以使用这个式子代替，图中给了解释，注意看。
队列的链表实现
用链表实现栈和队列都十分方便。代码都不用改的，把方法名从add改成enqueue，pop改成dequeue就行了。
package Chap4;
import java.util.Iterator;
public class MyQueue<Item> implements Iterable<Item> {
private class Node {
Item data;
Node next;
}
// 指向第一个节点
private Node first;
// 指向最后一个节点
private Node last;
private int N;
public int size() {
return N;
}
public boolean isEmpty() {
return N == 0;
}
// 入列，表尾加入元素
public void enqueue(Item item) {
Node oldlast = last;
last = new Node();
last.data = item;
// last应该指向null，但是新的结点next默认就是null
// 如果是第一个元素，则last和first指向同一个，即第一个
if (isEmpty()) {
first = last;
} else {
oldlast.next = last;
}
N++;
}
// 出列，即删除表头元素
public Item dequeue() {
Item item = first.data;
Node next = first.next;
// 这两行有助于垃圾回收
first.data = null;
first.next = null;
first = next;
N--;
// 最后一个元素被删除，first自然为空了，但是last需要置空。
// 注意是先减再判断是否为空
if (isEmpty()) {
last = null;
}
return item;
}
public Item getHead() {
return first.data;
}
public void clear() {
while (first != null) {
Node next = first.next;
// 下面两行帮助垃圾回收
first.next = null;
first.data = null;
first = next;
}
// 所有元素都空时，last也没有有所指了。记得last置空
last = null;
N = 0;
}
@Override
public Iterator<Item> iterator() {
return new Iterator<Item>() {
private Node current = first;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item item = current.data;
current = current.next;
return item;
}
};
}
@Override
public String toString() {
Iterator<Item> it = iterator();
if (!it.hasNext()) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append("[");
while (true) {
Item item = it.next();
sb.append(item);
if (!it.hasNext()) {
return sb.append("]").toString();
}
sb.append(", ");
}
}
public static void main(String[] args) {
MyQueue<Integer> a = new MyQueue<>();
a.enqueue(1);
a.enqueue(2);
a.enqueue(3);
a.enqueue(4);
System.out.println(a);
a.dequeue();
a.dequeue();
System.out.println(a); // [3, 4]
a.clear();
System.out.println(a.size()); // 0
a.enqueue(999);
a.enqueue(777);
System.out.println(a.getHead()); // 999
}
}
代码比较简单，而且在实现单链表的时候已经说得比较详细了，这里就不再赘述。
比较循环队列和链表实现的队列，入列出列的时间复杂度都是O(1)，不过循环队列有长度的限制，适合实现知道数据量的情况。链表实现的队列虽然有指针域Node会产生一些内存开销，不过总的来说可以接受，而且没有队列长度的限制。
by @sunhaiyu
2017.8.18
