队列
如何理解“队列”
- 操作受限的线性表数据结构：先进先出
- 最基本的操作：入队和出队
- 队列分为队头和队尾，在队尾插入数据（入队），在队头删除数据（出队）。
用数组实现的顺序队列和用链表实现的链式队列
思路：使用两个指针，一个head指针指向队头，一个tail指针指向队尾。
-
代码
// 用数组实现的队列 public class ArrayQueue { // 数组：items，数组大小：n private String[] items; private int n = 0; // head 表示队头下标，tail 表示队尾下标 private int head = 0; private int tail = 0; // 申请一个大小为 capacity 的数组 public ArrayQueue(int capacity) { items = new String[capacity]; n = capacity; } // 入队 public boolean enqueue(String item) { // 如果 tail == n 表示队列已经满了 if (tail == n) return false; items[tail] = item; ++tail; return true; } // 出队 public String dequeue() { // 如果 head == tail 表示队列为空 if (head == tail) return null; // 为了让其他语言的同学看的更加明确，把 -- 操作放到单独一行来写了 String ret = items[head]; ++head; return ret; } } 代码存在问题：随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。
代码优化思路：在tail移动到最右边时，判断head是否为0，如果是0，说明队列已满，如果不是，说明队列未满，此时进行一次队列的迁移，队列从head到tail整体迁移到从0开始。
-
优化代码
// 入队操作，将 item 放入队尾 public boolean enqueue(String item) { // tail == n 表示队列末尾没有空间了 if (tail == n) { // tail ==n && head==0，表示整个队列都占满了 if (head == 0) return false; // 数据搬移 for (int i = head; i < tail; ++i) { items[i-head] = items[i]; } // 搬移完之后重新更新 head 和 tail tail -= head; head = 0; } items[tail] = item; ++tail; return true; }
使用循环队列避免数据搬移操作
顾名思义，就是对队列的收尾是连接的，并不是真的像循环链表一样首尾连接，而是有相同的效果。
使用数组实现思路：数组实现队列，就是通过两个链表来访问数组，实现先进先出的效果。所以在入队和出队时，把控好数组的下标的变换即可实现循环队列的效果。所以需要了解判断队满的情况指针变换的情况。
-
思考：队列长度为n
- 队满的情况（针对队尾）：循环队列不能再使用tail等于n来判断是否有队满的可能。此时，因为是循环队列，由于其循环进行入队和出队的操作的特殊性，当队满时，队列就是全部被填满的，所以此时，出队和入队指针指向的值的和为n-1.（也可以用表达式(tail+1)%n==head）
- 队空的情况（针对队头）：不变，依然是head == tail时为队空。
- 指针变换的思考：不考虑队满和队空时，head和tail指针需要在等于n-1时，下一次变换为0.所以，可以使用一个判断或者使用+1整除n。
-
代码
public class CircularQueue { // 数组：items，数组大小：n private String[] items; private int n = 0; // head 表示队头下标，tail 表示队尾下标 private int head = 0; private int tail = 0; // 申请一个大小为 capacity 的数组 public CircularQueue(int capacity) { items = new String[capacity]; n = capacity; } // 入队 public boolean enqueue(String item) { // 队列满了 if (tail + head + 1 == n) return false; items[tail] = item; tail = (tail + 1) % n; return true; } // 出队 public String dequeue() { // 如果 head == tail 表示队列为空 if (head == tail) return null; String ret = items[head]; head = (head + 1) % n; return ret; } }
