# 1.2 队列-循环队列 #### 一.顺序 队列 队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。 \* 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变。 #### 数组模拟顺序队列 当我们将数据存入队列时称为"addQueue"，addQueue 的处理需要有两个步骤： \* 将尾指针往后移：rear+1 , 当front == rear 【空】 \* 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。 rear == maxSize - 1\[队列满\] \`\`\`java /\*\* \* desc: 使用数组模拟队列 \* @author GreyPigeon mail:2371849349@qq.com \* @since 2024-01-08-14:53 \*\*/ public class ArrayQueueDemo { public static void main(String\[\] args){ //测试 ArrayQueue queue = new ArrayQueue(3); char key = ' '; //接收用户输入 Scanner scanner = new Scanner(System.in); boolean loop = true; //输出一个菜单 while (loop) { System.out.println("s(show): 显示队列"); System.out.println("e(exit): 退出程序"); System.out.println("a(add): 添加数据到队列"); System.out.println("g(get): 从队列取出数据"); System.out.println("h(head): 查看队列头的数据"); key = scanner.next().charAt(0); //接收一个字符串 switch (key) { case 's': queue.showQueue(); break; case 'a': System.out.println("输入一个数"); int value = scanner.nextInt(); queue.addQueue(value); break; case 'g': //取出数据 try { int res = queue.getQueue(); System.out.printf("取出的数据是%d\\n", res); } catch (Exception e) { // TODO: handle exception System.out.println(e.getMessage()); } break; case 'h': //查看队列头的数据 try { int res = queue.headQueue(); System.out.printf("队列头的数据是%d\\n", res); } catch (Exception e) { // TODO: handle exception System.out.println(e.getMessage()); } break; case 'e': //退出 scanner.close(); loop = false; break; default: break; } } System.out.println("程序退出\~\~"); } } //编写一个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; //指向队列头部，分析出front是指向front是指向队列头的前一个位置。 rear = -1; //指向队列尾部，指向队列尾的的数据（即最后一个数据）。 } //判断队列是否已满 public boolean isFull(){ return rear == maxSize - 1; } //判断队列是否为空 public boolean isEmpty(){ return rear == front; } //添加数据到队列 public void addQueue(int n){ //判断队列是否已满 if (isFull()) { System.out.println("队列已满，不能添加数据\~"); return; } rear++; //让rear后移 arr\[rear\] = n; } //获取队列的数据，出队列 public int getQueue(){ //判断队列是否为空 if (isEmpty()) { //抛出异常 throw new RuntimeException("队列为空，不能获取数据"); } front++; //front后移（因为front始终指向第一个数据的前一个位置） return arr\[front\]; } //显示队列的所有数据 public void showQueue(){ //遍历 if (isEmpty()) { System.out.println("队列为空，没有数据"); return; } for(int i = 0; i \< arr.length; i++){ System.out.printf("arr\[%d\]=%d\\n", i, arr\[i\]); } } //显示队列的头数据，注意不是取出数据 public int headQueue(){ //判断是否为空 if(isEmpty()){ throw new RuntimeException("队列为空，没有数据"); } return arr\[front +1\]; } } \`\`\` #### 三. 顺序队列假溢出 什么是假溢出？这里需要考虑到顺序队列有什么缺点，对于顺序队列而言，其存在已经足够解决大多时候的设计问题了，但是其依旧存在一些缺陷和不足。由于入队和出队操作均是直接在其后面进行结点的链接和删除，这种操作会造成其使用空间不断向出队的那一边偏移，产生假溢出。 假设一个队列的总个数不超过5个，经过5次入队操作和两次出队操作后，如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做"假溢出"。 #### 四. 循环队列 解决假溢出的方法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。 当队首指针\`Q-\>front = MAXSIZE-1\`后，再前进一个位置就自动到0，这可以利用除法取余运算（%）来实现。 \*\*但由于空队列时，fromt等于rear，现在当队列满时，也是front等于rear，那么如何判断此时的队列究竟是空还是满呢？\*\* \* 办法一是设置一个标志变量fiag，当front= rear，且fag=0时为队列空，当font=rear，且filag = 1时为队列满。 \* 办法二是当队列空时，条件就是front = rear，当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。 我们重点来讨论第二种方法，由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大尺寸为QueueSize，那么队列满的条件是\*\*(rear+1) % QueueSize ==front \*\*（取模"%"的目的就是为了整合rear与front大小为一个问题）。 通用的就计算队列长度的公式：\*\*(rear - front + QueueSize) % QueueSize\*\* #### 五. 数组模拟循环队列 1. front变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr\[front)就是队列的第一个元素 front的初始值=0。 2. rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置。因为希望空出一个空间做为约定 rear的初始值=0。 \`\`\`java /\*\* \* desc:使用数组模拟循环队列 \* @author GreyPigeon mail:2371849349@qq.com \* @since 2024-01-08-17:55 \*\*/ public class CircleArrayQueueDemo { public static void main(String\[\] args) { System.out.println("测试数组模拟环形队列的案例\~\~\~"); // 创建一个环形队列 CircleArray queue = new CircleArray(4); //说明设置4, 其队列的有效数据最大是3 char key = ' '; // 接收用户输入 Scanner scanner = new Scanner(System.in);// boolean loop = true; // 输出一个菜单 while (loop) { System.out.println("s(show): 显示队列"); System.out.println("e(exit): 退出程序"); System.out.println("a(add): 添加数据到队列"); System.out.println("g(get): 从队列取出数据"); System.out.println("h(head): 查看队列头的数据"); key = scanner.next().charAt(0);// 接收一个字符 switch (key) { case 's': queue.showQueue(); break; case 'a': System.out.println("输出一个数"); int value = scanner.nextInt(); queue.addQueue(value); break; case 'g': // 取出数据 try { int res = queue.getQueue(); System.out.printf("取出的数据是%d\\n", res); } catch (Exception e) { // TODO: handle exception System.out.println(e.getMessage()); } break; case 'h': // 查看队列头的数据 try { int res = queue.headQueue(); System.out.printf("队列头的数据是%d\\n", res); } catch (Exception e) { // TODO: handle exception System.out.println(e.getMessage()); } break; case 'e': // 退出 scanner.close(); loop = false; break; default: break; } } System.out.println("程序退出\~\~"); } } class CircleArray { private int maxSize; // 表示数组的最大容量 //front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr\[front\] 就是队列的第一个元素 //front 的初始值 = 0 private int front; //rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定. //rear 的初始值 = 0 private int rear; // 队列尾 private int\[\] arr; // 该数据用于存放数据, 模拟队列 public CircleArray(int arrMaxSize) { maxSize = arrMaxSize; arr = new int\[maxSize\]; } // 判断队列是否满 public boolean isFull() { return (rear + 1) % maxSize == front; } // 判断队列是否为空 public boolean isEmpty() { return rear == front; } // 添加数据到队列 public void addQueue(int n) { // 判断队列是否满 if (isFull()) { System.out.println("队列满，不能加入数据\~"); return; } //直接将数据加入 arr\[rear\] = n; //将 rear 后移, 这里必须考虑取模 rear = (rear + 1) % maxSize; } // 获取队列的数据, 出队列 public int getQueue() { // 判断队列是否空 if (isEmpty()) { // 通过抛出异常 throw new RuntimeException("队列空，不能取数据"); } // 这里需要分析出 front是指向队列的第一个元素 // 1. 先把 front 对应的值保留到一个临时变量 int value = arr\[front\]; // 2. 将 front 后移, 考虑取模,防止越界 front = (front + 1) % maxSize; // 3. 将临时保存的变量返回 return value; } // 显示队列的所有数据 public void showQueue() { // 遍历 if (isEmpty()) { System.out.println("队列空的，没有数据\~\~"); return; } // 思路：从front开始遍历，遍历多少个元素？size() // arr的下标不一定是i，需要取模 （即使下标在长度范围内） for (int i = front; i \< front + size() ; i++) { System.out.printf("arr\[%d\]=%d\\n", i % maxSize, arr\[i % maxSize\]); } } // 求出当前队列有效数据的个数 public int size() { // rear = 2 // front = 1 // maxSize = 3 return (rear + maxSize - front) % maxSize; } // 显示队列的头数据， 注意不是取出数据 public int headQueue() { // 判断是否为空 if (isEmpty()) { throw new RuntimeException("队列空的，没有数据\~\~"); } return arr\[front\]; //front为队列的第一个元素 } } \`\`\` \> 参考：《大话数据结构》、尚硅谷