1 队列
1.1 何为队列及实现思路
何为队列？
- 队列是一个有序列表，可以通过数组或者链表来实现；
- 满足：先存入的数据先取出，后存入的数据后取出，即 先入先出。
实现思路：
队列本身是有序列表，可以使用数组进行模拟，上图所示，maxSize为队列的最大容量；
由于队列先入先出的特点，分别使用front和rear记录队列的队首与队尾，其中front指向队首的前一个位置，rear指向队尾（实际值）；
当入队操作完成时，则相应的rear要发生变化，如图（入队三个元素时），此时数组0、1、2索引都有值，rear指向队尾，即索引为2的位置；
取出队首元素时，由于front指向的是队尾的前一个元素，所以需要先让front自增1，而后再取值，即第一次取出时，front=0对应的为队首元素；
当front = rear时队列为空，当rear=maxSize-1，即队尾指向数组末尾，说明队列已满，在设计入队和出队方法时需要特别注意！
1.2 数组模拟队列ArrayQueue的实现
详细可见代码注释，ArrayQueue.java参考代码如下：
/** * 使用数组模拟队列 ArrayQueue类 */ class ArrayQueue{ private int maxSize; //数组的最大容量 private int front; //队列头 private int rear; //队列尾 private int[] arr; //用于存放数据 //创建队列的构造器 public ArrayQueue(int arrMaxSize){ maxSize = arrMaxSize; arr = new int[maxSize]; front = -1; //指向队列头的前一个位置 rear = -1; //指向队列尾部，指向具体的数据 } //判断队列是否已满 public boolean isFull(){ return rear == maxSize-1; } //判断队列是否为空 public boolean isEmpty(){ return rear==front; } //添加数据到队列 public void addQueue(int item){ //先判断队列是否满 if (isFull()){ System.out.println("队列已满,不能加入数据"); return; } //添加操作 arr[++rear] = item; //rear后移，加入元素item } //获取队列的数据 public int getQueue(){ //判断是否为空 if (isEmpty()){ throw new RuntimeException("当前队列为空"); } return arr[++front]; } //显示当前队列中的所有数据 public void showQueue(){ if (isEmpty()){ System.out.println("当前队列为空"); } for (int i = front+1; i <= rear; i++) { System.out.printf("arr[%d] = %d\n", i, arr[i]); } } //显示头数据 public int peek(){ if (isEmpty()){ throw new RuntimeException("当前队列为空!"); } return arr[front+1]; } }
1.3 测试队列ArrayQueueDemo测试类的实现
为了便于队列的测试，我们初始假定队列的最大元素数量为3，具体代码及结果如下：
import java.util.Scanner; /** * @author 兴趣使然黄小黄 * @version 1.0 * 使用数组模拟队列 */ public class ArrayQueueDemo { public static void main(String[] args) { //创建一个最大元素数量为3的队列 ArrayQueue arrayQueue = new ArrayQueue(3); char key = ' '; //接收用户输入 Scanner scanner = new Scanner(System.in); boolean loop = true; //菜单 while (loop){ System.out.println("s: 显示队列"); System.out.println("e: 退出程序"); System.out.println("a: 添加数据到队列"); System.out.println("p: 查看头数据"); System.out.println("g: 从队列里取出数据"); key = scanner.next().charAt(0); switch (key){ case 's': arrayQueue.showQueue(); break; case 'a': System.out.print("请输入一个数字: "); int item = scanner.nextInt(); arrayQueue.addQueue(item); break; case 'g': try { int queue = arrayQueue.getQueue(); System.out.println("取出的数据是: " + queue); } catch (Exception e) { e.printStackTrace(); } break; case 'p': try { int peek = arrayQueue.peek(); System.out.println("查看的数据是: " + peek); } catch (Exception e) { e.printStackTrace(); } break; case 'e': scanner.close(); loop = false; break; default: break; } } System.out.println("已退出程序"); } }
实现结果
s: 显示队列 e: 退出程序 a: 添加数据到队列 p: 查看头数据 g: 从队列里取出数据 a 请输入一个数字: 1 s: 显示队列 e: 退出程序 a: 添加数据到队列 p: 查看头数据 g: 从队列里取出数据 a 请输入一个数字: 3 s: 显示队列 e: 退出程序 a: 添加数据到队列 p: 查看头数据 g: 从队列里取出数据 a 请输入一个数字: 7 s: 显示队列 e: 退出程序 a: 添加数据到队列 p: 查看头数据 g: 从队列里取出数据 p 查看的数据是: 1 s: 显示队列 e: 退出程序 a: 添加数据到队列 p: 查看头数据 g: 从队列里取出数据 g 取出的数据是: 1 s: 显示队列 e: 退出程序 a: 添加数据到队列 p: 查看头数据 g: 从队列里取出数据 g 取出的数据是: 3 s: 显示队列 e: 退出程序 a: 添加数据到队列 p: 查看头数据 g: 从队列里取出数据 s arr[2] = 7 s: 显示队列 e: 退出程序 a: 添加数据到队列 p: 查看头数据 g: 从队列里取出数据 e 已退出程序 Process finished with exit code 0
但是，经过笔者的反复测试，很快就发现了一个巨大的bug！
比如：先让三个数入队，即先将队列存满。然后，让三个元素出队。此时理论上队列应该为空，但是当我继续入队一个元素时，结果如下:
队列虽然为空，但是无法继续存储数据！
实际上，此时虽然满足front=rear，但队列的样子应该是这样的：
即 此时队列虽然看起来是满的，但是，实际没满， 相当于以这种方式实现队列属于一次性产品！因此，我们通过算法进行优化，引出 环形队列。
2 环形队列
2.1 环形队列简介及实现思路
由于之前的方式会出现队列为满实际未满的情况，为了实现使用数组模拟队列，我们可以通过对前面的数组模拟队列进行优化，充分利用数组，即 将数组看成一个环形的（主要通过取模的方式来实现）。
实现思路：
front变量指向队首元素， 即arr[front]就是队列的第一个元素;
rear变量指向队尾元素的后一个位置， 即arr[rear-1]为队尾元素。这么做的目的是为了空出一个空间，为了区分队列满和队列空的条件；
当队列满时：(rear+1)%maxSize = front。 在环形队列中，由于空出一个空间，则数组最多存放maxSize-1个元素，rear的最大值为maxSize-1;
出队操作：(front+1)%maxSize = front，入队操作：(rear+1)%maxSize = rear；
当队列为空的时候：front = rear;
队列中有效的数据个数为：(rear+maxSize-front)%maxSize。 也可以写成 abs(rear-front)%maxSize。
当rear在front之后(这里指的是数组中索引位的前后，并非逻辑上的前后)，有效数据个数=rear-front=(rear+maxSize-front)%maxSize
当rear在front之前(这里指的是数组中索引位的前后，并非逻辑上的前后)，有效数据个数=(rear+maxSize-front)%maxSize
环形队列的图片出自：@csdn-所遇皆惊喜：数据结构 - 队列 && 环形队列（循环队列）
2.2 数组模拟环形队列CircleArrayQueue的实现
详细可见代码注释，CircleArrayQueue.java参考代码如下：
/** * @author 兴趣使然黄小黄 * @version 1.0 * 数组模拟环形队列 */ public class CircleArrayQueue { private int maxSize; //数组的最大容量 private int front; //队列头 private int rear; //队列尾后一个元素 private int[] arr; //用于存放数据 //创建队列的构造器 public CircleArrayQueue(int arrMaxSize){ maxSize = arrMaxSize; arr = new int[maxSize]; front = 0; rear = 0; } //判断队列是否已满 public boolean isFull(){ return (rear + 1) % maxSize == front; } //判断队列是否为空 public boolean isEmpty(){ return rear==front; } //添加数据到队列 public void addQueue(int item){ //先判断队列是否满 if (isFull()){ System.out.println("队列已满,不能加入数据"); return; } //添加操作 arr[rear] = item; //直接添加, 因为rear指向队尾后一个位置 rear = (rear + 1) % maxSize; //rear后移 } //获取队列的数据 public int getQueue(){ //判断是否为空 if (isEmpty()){ throw new RuntimeException("当前队列为空"); } //1.先把front对应的值保存 int value = arr[front]; //2.front后移 front = (front + 1) % maxSize; return value; } //返回有效数据的个数 public int size(){ return (rear + maxSize - front) % maxSize; } //显示当前队列中的所有数据 public void showQueue(){ if (isEmpty()){ System.out.println("当前队列为空"); } //注意取模 for (int i = front; i < front + size(); i++) { System.out.printf("arr[%d] = %d\n", i % maxSize, arr[i%maxSize]); } } //显示头数据 public int peek(){ if (isEmpty()){ throw new RuntimeException("当前队列为空!"); } return arr[front]; } }
2.3 测试队列CircleArrayQueueDemo测试类的实现
为了便于队列的测试，我们还是初始假定队列的最大元素数量为3，具体代码及结果如下：
import java.util.Scanner; /** * @author 兴趣使然黄小黄 * @version 1.0 * 测试环形队列 */ public class CircleArrayQueueDemo { public static void main(String[] args) { //创建一个最大元素数量为3的队列 CircleArrayQueue circleArrayQueue = new CircleArrayQueue(3); char key = ' '; //接收用户输入 Scanner scanner = new Scanner(System.in); boolean loop = true; //菜单 while (loop){ System.out.println("s: 显示队列"); System.out.println("e: 退出程序"); System.out.println("a: 添加数据到队列"); System.out.println("p: 查看头数据"); System.out.println("g: 从队列里取出数据"); key = scanner.next().charAt(0); switch (key){ case 's': circleArrayQueue.showQueue(); break; case 'a': System.out.print("请输入一个数字: "); int item = scanner.nextInt(); circleArrayQueue.addQueue(item); break; case 'g': try { int queue = circleArrayQueue.getQueue(); System.out.println("取出的数据是: " + queue); } catch (Exception e) { e.printStackTrace(); } break; case 'p': try { int peek = circleArrayQueue.peek(); System.out.println("查看的数据是: " + peek); } catch (Exception e) { e.printStackTrace(); } break; case 'e': scanner.close(); loop = false; break; default: break; } } System.out.println("已退出程序"); } }
结果如下
s: 显示队列 e: 退出程序 a: 添加数据到队列 p: 查看头数据 g: 从队列里取出数据 a 请输入一个数字: 1 s: 显示队列 e: 退出程序 a: 添加数据到队列 p: 查看头数据 g: 从队列里取出数据 a 请输入一个数字: 2 s: 显示队列 e: 退出程序 a: 添加数据到队列 p: 查看头数据 g: 从队列里取出数据 a 请输入一个数字: 3 队列已满,不能加入数据 s: 显示队列 e: 退出程序 a: 添加数据到队列 p: 查看头数据 g: 从队列里取出数据 g 取出的数据是: 1 s: 显示队列 e: 退出程序 a: 添加数据到队列 p: 查看头数据 g: 从队列里取出数据 g 取出的数据是: 2 s: 显示队列 e: 退出程序 a: 添加数据到队列 p: 查看头数据 g: 从队列里取出数据 g java.lang.RuntimeException: 当前队列为空 at com.hxh.queue.CircleArrayQueue.getQueue(CircleArrayQueue.java:48) at com.hxh.queue.CircleArrayQueueDemo.main(CircleArrayQueueDemo.java:36) s: 显示队列 e: 退出程序 a: 添加数据到队列 p: 查看头数据 g: 从队列里取出数据 a 请输入一个数字: 1 s: 显示队列 e: 退出程序 a: 添加数据到队列 p: 查看头数据 g: 从队列里取出数据 s arr[2] = 1 s: 显示队列 e: 退出程序 a: 添加数据到队列 p: 查看头数据 g: 从队列里取出数据 e 已退出程序 Process finished with exit code 0
可见，最大有效数量由于一个置空位置，由3变成了2。当两个元素入队后，将两个元素出队，再次入队，可以成功入队。说明，将数组看成环形数组，通过取模运算可以解决之前的一次性使用的问题。
