数组模拟队列

队列本身是有序列表，若使用数组的结构存储队列的数据，则队列数组的声明如下图，其中maxSize是该队列的最大容量

因为队列的输出，输入是分别从前后端来处理，因此需要两个变量front和rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变，如图所示：

当我们将数据存入队列时称为“addQueue”，addQueue的处理有两个步骤：

思路分析：

1.判断尾指针rear是否小于最大下标maxSize-1

2.若为true，则将尾指针往后移，并将数据存入rear所指的数组元素中：rear+1；若为false，则无法存储

代码实现：

import java.util.Scanner; 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 i = scanner.nextInt(); queue.addQueue(i); break; case 'e': scanner.close(); loop = false; break; case 'g': try{ int i1 = queue.delQueue(); System.out.printf("取出的数据%d\n", i1); }catch (Exception e){ System.out.println(e.getMessage()); } break; case 'h': try{ int i1 = queue.headQueue(); System.out.printf("队头的数据%d\n", i1); }catch (Exception e){ System.out.println(e.getMessage()); } break; default: break; } } System.out.println("程序退出"); } static class ArrayQueue{ private int maxSize; private int head; private int tear; private int[] array; //初始化构建一个队列 ArrayQueue(int arrayMaxSize){ maxSize = arrayMaxSize; array = new int[maxSize]; head = -1; tear = -1; } //判断队列是否填满 boolean isFull(){ return tear == maxSize -1; } //判断队列是否为空 boolean isEmpty(){ return head == tear; } //往队列中添加一个元素 void addQueue(int num){ if (isFull()){ System.out.println("队列已经满了。。"); return; } tear++; array[tear]=num; } //从队列中取出一个元素 int delQueue(){ if (isEmpty()){ throw new RuntimeException("队列是空的。。"); } head++; return array[head]; } //显示队列的所有数据 void showQueue(){ if (isEmpty()){ System.out.println("队列是空的。。"); return; } for (int i=0;i<maxSize;i++){ System.out.printf("arr[%d]=%d\n", i, array[i]); } } //显示队列头部的元素，不是取出 int headQueue(){ if (isEmpty()){ throw new RuntimeException("队列是空的。。"); } return array[head+1]; } } }

数组模拟环形队列

分析示意图：

改变如下：

1.front变量的初始值为0，也就是开始指向队列的第一个元素arr[front]

2.rear变量的初始值为0，并且rear总是指向队列最后一个元素的后一个位置，也就是永远指向一个空的位置，除非队列是满的

3.队列满的条件：（rear + 1）%maxsize == front（对maxsize取模是为了防止下标越界）

​ 比如：maxsize为6时，这时rear指向队列的下标是5最后一个位置为空，当添加一个数据，rear就会往后移，而如果rear+1，则会越界，这时就得进行取模运算（rear + 1）%maxsize，rear指向的是0位置，就能够避免，而且

若没有取出过元素，front也是0不变，这时就可以说是满队列了

4.队列为空的条件：rear == front //刚开始rear =0 front=0 队列为空

5.队列中有效数据的个数：（rear-front+maxsize）%maxsize

​ 本来若是普通队列，有效个数为rear-front；而现在是环形队列（首尾相连），也就是rear所指的下标值可能比front的小，也就是rear在front的前面；所以进行取模运算（rear-front+maxsize）%maxsize可以防止负数的出现

6.往环形队列中添加数据时：rear++变为（rear + 1）%maxsize（对maxsize取模是为了防止下标越界）

7.显示环形队列头部数据时：直接取出front指向的下标的对应值就行了

8.取出环形队列数据时：首先要将当前front指向的数据存储起来，然后再改变front的下标，也要进行取模防止下标越界（front + 1）% maxsize

9.显示队列所有数据时：所有数据的个数为有效数据的个数，并且是从front开始的

10.队列中永远有一个空闲的位置，也就是说最大有效数据的个数为maxsize-1

代码实现：

import java.util.Scanner; public class CircleArrayQueue { public static void main(String[] args) { //测试 CircleArray queue = new CircleArray(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 i = scanner.nextInt(); queue.addQueue(i); break; case 'e': scanner.close(); loop = false; break; case 'g': try{ int i1 = queue.delQueue(); System.out.printf("取出的数据%d\n", i1); }catch (Exception e){ System.out.println(e.getMessage()); } break; case 'h': try{ int i1 = queue.headQueue(); System.out.printf("队头的数据%d\n", i1); }catch (Exception e){ System.out.println(e.getMessage()); } break; default: break; } } System.out.println("程序退出"); } static class CircleArray{ private int maxSize; private int head; private int tear; private int[] array; //初始化构建一个队列 CircleArray(int arrayMaxSize){ maxSize = arrayMaxSize; array = new int[maxSize]; } //判断队列是否填满 boolean isFull(){ return (tear +1)%maxSize == head; } //判断队列是否为空 boolean isEmpty(){ return head == tear; } //往队列中添加一个元素 void addQueue(int num){ if (isFull()){ System.out.println("队列已经满了。。"); return; } array[tear]=num; tear = (tear +1)%maxSize; } //从队列中取出一个元素 int delQueue(){ if (isEmpty()){ throw new RuntimeException("队列是空的。。"); } int i = array[head]; head = (head +1)%maxSize; return i; } //显示队列的所有数据 void showQueue(){ if (isEmpty()){ System.out.println("队列是空的。。"); return; } for (int i=head;i<head + size();i++){ //下标为i%maxSize，也是为了防止下标越界 System.out.printf("arr[%d]=%d\n", i%maxSize, array[i%maxSize]); } } //显示队列头部的元素，不是取出 int headQueue(){ if (isEmpty()){ throw new RuntimeException("队列是空的。。"); } return array[head]; } //获取队列的有效数据的个数 int size(){ return (tear - head +maxSize)%maxSize; } } }

视频链接：https://www.bilibili.com/video/BV1E4411H73v