关于队列，首先要知道的一点就是，队列是一个先进先出的数据结构。
我们可以使用数组实现队列，也可以使用链表实现队列。本文将的是数组队列

普通队列

定义

普通队列的定义很简单，我们首先知道一个定义

  • front 代表队首指针，指向的是队列中第一个元素的前一个位置，默认为 -1
  • rear 代表队尾指针，指向队列中最后一个元素，默认为-1
  • maxSize 代表队列的最大容量
  • data[] 用来存放队列数据的数组

至于为什么要让 front 指向第一个元素的前一个位置呢？
举个🌰
假设我们现在有3 个元素
image.png
这个时候如果1出队，front++ 变成了0
2出队，front++ 变成了1
然后我们可以直接 return data[front] 就可以返回出队的元素了，而且出队，front++也更容易让我们理解这代表出队了

满队列 和 空队列的判断

如何判断队列为空？

当 rear == front 的时候，队列为空
初始情况下，front == rear == -1
全部元素出队的情况下：
image.png
front 仍然与 rear 相等

如何判断队列为满？

rear + 1 = maxSize的情况下判断队列为满
要记得，数组的下标是从0开始数的，所以，如图中，队列中存在3个元素，那么rear = 2
所以 rear + 1 = maxSize 为满队列

代码实现

  1. public class ArrayQueueDemo {
  3.     public static void main(String[] args) {
  4.         ArrayQueue queue = new ArrayQueue(3);
  5.         char key = ' '; 
  6.         Scanner scanner = new Scanner(System.in);//
  7.         boolean loop = true;
  9.         while(loop) {
  10.             System.out.println("s(show): 遍历队列");
  11.             System.out.println("e(exit): 退出程序");
  12.             System.out.println("a(add): 添加一个数据到队列");
  13.             System.out.println("g(get): 从队列中取出一个数据");
  14.             System.out.println("h(head): 显示队头元素");
  15.             key = scanner.next().charAt(0);
  16.             switch (key) {
  17.             case 's':
  18.                 queue.showQueue();
  19.                 break;
  20.             case 'a':
  21.                 System.out.println("输入一个值");
  22.                 int value = scanner.nextInt();
  23.                 queue.addQueue(value);
  24.                 break;
  25.             case 'g': 
  26.                 try {
  27.                     int res = queue.getQueue();
  28.                     System.out.printf("取出的元素为%d\n", res);
  29.                 } catch (Exception e) {
  30.                     System.out.println(e.getMessage());
  31.                 }
  32.                 break;
  33.             case 'h': 
  34.                 try {
  35.                     int res = queue.headQueue();
  36.                     System.out.printf("队首的元素为%d\n", res);
  37.                 } catch (Exception e) {
  38.                     System.out.println(e.getMessage());
  39.                 }
  40.                 break;
  41.             case 'e': 
  42.                 scanner.close();
  43.                 loop = false;
  44.                 break;
  45.             default:
  46.                 break;
  47.             }
  49.         }
  51.         System.out.println("退出程序");
  52.     }
  54. }
  56. //使用数组模拟队列
  57. class ArrayQueue {
  58.     //队列的最大容量
  59.     private int maxSize;
  60.     //队首
  61.     private int front;
  62.     //队尾
  63.     private int rear;
  64.     //存放的数据
  65.     private int[] data;
  67.     //创建一个队列
  68.     public ArrayQueue(int maxSize) {
  69.         this.maxSize = maxSize;
  70.         data = new int[maxSize];
  71.         front = -1;//指向队列头部的前一个位置
  72.         rear = -1;//指向队尾（指向队列的最后一个数据）
  73.     }
  75.     //添加数据到队列
  76.     public void addQueue(int n) {
  77.         if (isFull()) {
  78.             System.out.println("队列已满");
  79.             return;
  80.         }
  82.         //让队尾指针后移
  83.         rear++;
  84.         data[rear] = n;
  85.     }
  87.     //获取队列元素（出队列）
  88.     public int getQueue() {
  89.         if (isEmpty()) {
  90.             throw new RuntimeException("队列为空,不能取数据");
  91.         }
  93.         //队首指针后移
  94.         front++;
  95.         return data[front];
  96.     }
  98.     //遍历队列的元素
  99.     public void showQueue() {
  100.         if (isEmpty()) {
  101.             System.out.println("队列为空，没有数据");
  102.             return;
  103.         }
  104.         for (int i = front+1; i <= rear; i++) {
  105.             System.out.println(data[i]);
  106.         }
  107.     }
  109.     //显示队列的头数据
  110.     public int headQueue() {
  111.         if(isEmpty()) {
  112.             throw new RuntimeException("队列为空,不能取数据");
  113.         }
  115.         return data[front+1];
  116.     }
  118.     //判断队列是否满了
  119.     public boolean isFull() {
  120.         //如果队尾 == 最大容量-1 那么说明队列为空
  121.         return maxSize-1 == rear;
  122.     }
  124.     public boolean isEmpty() {
  125.         //队首==队尾时 说明队列为空
  126.         return front == rear;
  127.     }
  129. }

环形队列

环形队列与普通队列相比，有什么优点呢？
如果在普通队列中，全部元素全部出队，这个时候 rear和 front指针都指向了最后一个空间
image.png
如果我们不让front 和 rear 重新初始化，那么这个队列就不能够循环使用了
为了解决这个问题，我们提出了环形队列的概念

定义

首先在定义这方面，相比于普通队列，我们做了一个改变

  • front 队首指针，指向队列中第一个元素，默认为0
  • rear 队尾指针，指向队列中最后一个元素的后一个位置，默认为0
  • 我们要预留一个空间，用来判断队满还是队空

所以我们的实际的最大有效元素个数为 maxSize - 1

满队列 和 空队列的判断

首先要明白最最最最重要的一点，我们的预留空间是动态变化的

因为是环形队列，所以存在 rear指针的下标 可能会比front 还小
如果，当满队列后
front的下标为0
rear的下标为 3
如果这个时候1出队，然后4入队，这个时候
那么 front 变成了1
rear变成了0，就出现了 rear比front 小的情况
如图（❌为预留空间，不存放元素）
image.png
所以，计算有效个数的时候我们要考虑这种raer 比 front 小的情况
环形队列中的有效元素个数的公式为
(rear + maxSize - front ) % maxSize

我们可以做一个计算，当图左的时候，front = 0，rear =3
(3 + 4 -0) % 4 = 3
图右的时候，front = 1, rear = 0
(0 + 4 - 1) % 4 = 3

那么如何判断是否为 满队列呢？
我们可以通过
(rear + 1) % maxSize = front
% maxSize 是为了当出现图2的时候，我们仍然可以计算出 队列是否为满
这个公式来判断队列是否为空，具体可以进行计算
图左 rear 的下标3, front = 0
(3 + 1 )% 4 = 0 == front
这个时候队列为满
图右
rear = 0，front =1
(0 + 1 )% 4 = 1 == front

同样的，front == rear仍然表示队列为空的情况，没发生改变。

代码实现

  1. public class CircleArrayQueueDemo {
  2.     public static void main(String[] args) {
  3.         CircleArrayQueue queue = new CircleArrayQueue(4);
  4.         char key = ' '; 
  5.         Scanner scanner = new Scanner(System.in);//
  6.         boolean loop = true;
  8.         while(loop) {
  9.             System.out.println("s(show): 遍历队列");
  10.             System.out.println("e(exit): 退出程序");
  11.             System.out.println("a(add): 添加一个数据到队列");
  12.             System.out.println("g(get): 从队列中取出一个数据");
  13.             System.out.println("h(head): 显示队头元素");
  14.             key = scanner.next().charAt(0);
  15.             switch (key) {
  16.             case 's':
  17.                 queue.showQueue();
  18.                 break;
  19.             case 'a':
  20.                 System.out.println("输入一个值");
  21.                 int value = scanner.nextInt();
  22.                 queue.addQueue(value);
  23.                 break;
  24.             case 'g': 
  25.                 try {
  26.                     int res = queue.getQueue();
  27.                     System.out.printf("取出的元素为%d\n", res);
  28.                 } catch (Exception e) {
  29.                     System.out.println(e.getMessage());
  30.                 }
  31.                 break;
  32.             case 'h': 
  33.                 try {
  34.                     int res = queue.headQueue();
  35.                     System.out.printf("队首的元素为%d\n", res);
  36.                 } catch (Exception e) {
  37.                     System.out.println(e.getMessage());
  38.                 }
  39.                 break;
  40.             case 'e': 
  41.                 scanner.close();
  42.                 loop = false;
  43.                 break;
  44.             default:
  45.                 break;
  46.             }
  48.         }
  50.         System.out.println("退出程序");
  51.     }
  52. }
  54. //使用数组模拟队列
  55. class CircleArrayQueue {
  56.     //队列的最大容量
  57.     private int maxSize;
  58.     //队首
  59.     private int front;
  60.     //队尾
  61.     private int rear;
  62.     //存放的数据
  63.     private int[] data;
  65.     //创建一个队列
  66.     public CircleArrayQueue(int maxSize) {
  67.         this.maxSize = maxSize;
  68.         data = new int[maxSize];
  69.         front = 0;//指向队列中第一个元素
  70.         rear = 0;//指向队列中最后一个元素的后一个位置
  71.     }
  73.     //添加数据到队列
  74.     public void addQueue(int n) {
  75.         if (isFull()) {
  76.             System.out.println("队列已满");
  77.             return;
  78.         }
  80.         //先添加元素
  81.         data[rear] = n;
  83.         //再让队尾指针后移
  84.         //但是要注意是环形队列，所以我们可以对 maxSize求余
  85.         rear = (rear + 1) % maxSize;
  87.     }
  89.     //获取队列元素（出队列）
  90.     public int getQueue() {
  91.         if (isEmpty()) {
  92.             throw new RuntimeException("队列为空,不能取数据");
  93.         }
  95.         //这里一定要注意啊，因为我们的 队首指针也是会环形变化的
  96.         //所以我们可以先把值拿出来，然后再对指针进行操作
  97.         //队首指针后移
  98.         int value = data[front];
  99.         front = (front + 1) % maxSize;
  100.         return value;
  101.     }
  103.     //遍历队列的元素
  104.     public void showQueue() {
  105.         if (isEmpty()) {
  106.             System.out.println("队列为空，没有数据");
  107.             return;
  108.         }
  109.         //这里我们可以直接遍历 有效元素个数。
  110.         //而且还有一点，在环形队列中 i 也是有可能大于 最大下标的
  111.         for (int i = front; i < front + size(); i++) {
  112.             System.out.println(data[(i % maxSize)]);
  113.         }
  114.     }
  116.     //判断队列中的有效元素个数
  117.     public int size() {
  118.         return (rear + maxSize - front) % maxSize;
  119.     }
  121.     //显示队列的头数据
  122.     public int headQueue() {
  123.         if(isEmpty()) {
  124.             throw new RuntimeException("队列为空,不能取数据");
  125.         }
  127.         return data[front];
  128.     }
  130.     //判断队列是否满了
  131.     public boolean isFull() {
  132.         return (rear + 1) % maxSize == front;
  133.     }
  135.     public boolean isEmpty() {
  136.         //队首==队尾时 说明队列为空
  137.         return front == rear;
  138.     }
  140. }