1 简介
队列是一个有序列表，遵循先入先出的原则。可以用链表或数组来实现。本文全部实现以及测试源码可在如下链接获取。
https://gitee.com/flying-morning/data-structure/tree/master/src/com/datastructure/queue
2 使用数组实现
2.1 简单顺序队列
需要分别使用 front 和 rear 来记录队列的前后端的下标。取出的时候是在队头，因此 front 会改变，放入的时候则影响队尾，rear 会改变。我们做出如下约定：
- font 指向的是对头元素的位置，而 rear 指向队尾元素的后一个位置。这样做是为了，避免当只有一个元素时，队头队尾重合，处理起来比较麻烦。
- 初始值，front = 0，rear =0。这样设置是与这两个值的含义相关的。
- 队列为空：front == rear；
- 队列满了：rear = maxSize。
入队
对尾指针进行操作，此时要考虑：
- 如果队列未满，则将数据存入 rear 所指的位置，尾指针后移，rear = rear +1；
- 如果 rear = maxSize 则说明队列满了，无法存入新数据。
出队
此时 front 对应的元素就是头元素：
- 如果队列为空，则无法取出；
- 否则，取出元素，然后 front + 1。
源码
package com.datastructure.queue;
public class ArrayQueue {
int[] array;
private int maxSize;//队列容量
private int front;
private int rear;
public ArrayQueue (int maxSize) {
array = new int[maxSize];
this.maxSize = maxSize;
front = 0;
rear = 0;
}
//取出队头元素
public int get() {
if (isEmpty()) {
throw new RuntimeException("队列为空，无法取出");
}
System.out.println("取出元素：" + array[front]);
return array[front++];//front 所指的就是队头元素
}
//添加元素
public void add(int num) {
if (isFull()) {
System.out.println("队列已满，无法添加 " + num);
return;
}
array[rear++] = num;//添加到 rear 所在位置，然后 rear+1
System.out.println("成功添加元素：" + num);
}
//判断队列是否满了
private boolean isFull() {
return rear == maxSize;
}
//队列是否为空
public boolean isEmpty() {
return rear == front;
}
//展示队列中的元素
public void show() {
if(isEmpty()) {
System.out.println("队列为空");
return;
}
System.out.print("当前队列为：");
for (int i=front;i<rear;++i) {
System.out.print(array[i] + " ");
}
System.out.println();
}
//显示队头元素，不取出
public int peek() {
if(isEmpty()) {
throw new RuntimeException("队列为空，无队头");
}
System.out.println("当前队头为：" + array[front]);
return array[front];
}
}
缺陷
经过测试，发现只要队列满过一次，也就是 rear = maxSize，即使后面取出了元素，rear 的值也不会改变，再判断是否满了的时候，依然会认为这个队列满了。但实际上，这个队列还没有满，仍然可以存入数据。简单来说，就是这种实现无法复用，出现了“假溢出”。
2.2 循环队列
前面实现的一个明显问题就是队列为满的判断方式存在问题。所以我们重新定义下什么叫做队列满了。
如图所示，根据我们对 rear 和 front 的定义，在下面这种情况，还有元素空间。但此时，我们保留这一个元素空间，认为已经满了。也即：
队列满：(rear + 1)%maxSzie == front，取模的原因是因为 rear 可能在 front 前面，也可能在后面；
队列空：rear == front；
元素个数：(rear + maxSize - front)%maxSize。
入队
对尾指针进行操作，此时要考虑：
- 如果队列未满，则将数据存入 rear 所指的位置，尾指针后移，rear = (rear +1)%maxSize；
- 如果 (rear + 1)%maxSize == front 则说明队列满了，无法存入新数据。
出队
此时 front 对应的元素就是头元素：
- 如果队列为空，则无法取出；
- 否则，取出元素，然后 (front + 1)%maxSize。
源码
其实没有多少改变，主要就是判断队列满的逻辑变了，以及 rear 和 front 在 +1 后需要取模。另外，这里多了个接口 MyQueue，是为了测试方便，对这几种 queue 进行相同操作的测试，2.1 中的 ArrayQueue 最后也改成了实现接口，这里就不重新贴源码了。
package com.datastructure.queue;
public class CycleArrayQueue implements MyQueue{
int[] array;
private int maxSize;//队列容量
private int front;
private int rear;
public CycleArrayQueue (int maxSize) {
array = new int[maxSize];
this.maxSize = maxSize;
front = 0;
rear = 0;
}
//取出队头元素
public int get() {
if (isEmpty()) {
throw new RuntimeException("队列为空，无法取出");
}
int value = array[front];
System.out.println("取出元素：" + value);
front = (front + 1)%maxSize;
return value;//front 所指的就是队头元素
}
//添加元素
public void add(int num) {
if (isFull()) {
System.out.println("队列已满，无法添加 " + num);
return;
}
array[rear] = num;//添加到 rear 所在位置，然后 rear+1
rear = (rear + 1)%maxSize;
System.out.println("成功添加元素：" + num);
}
//判断队列是否满了
private boolean isFull() {
return (rear + 1)%maxSize == front;
}
//队列是否为空
public boolean isEmpty() {
return rear == front;
}
public int size() {
return (rear + maxSize -front)%maxSize;
}
//展示队列中的元素
public void show() {
if(isEmpty()) {
System.out.println("队列为空");
return;
}
System.out.print("当前队列为：");
for (int i=front;i<front + size();++i) {
System.out.print(array[i%maxSize] + " ");
}
System.out.println();
}
//显示队头元素，不取出
public int peek() {
if(isEmpty()) {
throw new RuntimeException("队列为空，无队头");
}
System.out.println("当前队头为：" + array[front]);
return array[front];
}
}