什么是队列？

队列，和栈一样，也是一种对数据的”存”和”取”有严格要求的线性存储结构。
与栈结构不同的是，队列的两端都”开口”，要求数据只能从一端进，从另一端出，如图 1 所示：

image.png
队列是一种先入，先出的一种结构。

通常，称进数据的一端为 “队尾”，出数据的一端为 “队头”，数据元素进队列的过程称为 “入队”，出队列的过程称为 “出队”。

就跟排队一样，先排队的先办理。新来的排队的人，得排到后面，就是进数据到队尾，队伍第一个办理完业务，就离开，就是出数据的一端就是队头。

队列可以用数组或者链表实现，用数组就是顺序存储，用链表就是链式存储。

数组模拟队列

思路

队列本身是有序表，可以使用数组来模拟队列。
队列的输入输出分别是从前后端来处理的，因此需要两个变量front和rear分别标记队列的前端和后端。front会随着数据出队而变化，rear会随着数据入队而变化。（想想排队，排在前面的就是前端，排在后面的就是后端，新来的排队，只能排在后面，所以rear后端发生变化，最前面的办完事就离开时队伍，前面的人员变动了，所以front前端发生变化。）

rear是队列的最后（包含） front是队列的最前（不含） 最开始定义空队列的时候front和rear都是-1

代码

声明一个队列类ArrayQueue

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Text;
  5. namespace ConsoleApp1
  6. {
  7.     class ArrayQueue
  8.     {
  9.         private int maxSize;//数组的最大容量
  10.         private int front;//队列头的指针
  11.         private int rear;//队列尾的指针
  12.         private int[] arr;//该数组用于存放队列的数据
  14.         //创建队列的构造函数，传入一个数组的最大容量
  15.         public ArrayQueue(int arrMaxSize)
  16.         {
  17.             maxSize = arrMaxSize;
  18.             arr = new int[maxSize];
  19.             front = -1;//指向队列头部，并不包含，指向队列的前一个位置
  20.             rear = -1;//指向队列尾部，包含，指向队列尾部的具体数据（就是队列的最后一个数据）
  21.         }
  23.         //判断队列是否满
  24.         public bool isFull()
  25.         {
  26.             return rear == maxSize - 1;
  27.         }
  29.         //判断队列是否为空
  30.         public bool isEmpty()
  31.         {
  32.             return rear == front;
  33.         }
  35.         //添加数据到队列，n是数据
  36.         public void addQueue(int n)
  37.         {
  38.             if (isFull())
  39.             {
  40.                 Console.WriteLine("队列满了，不能加数据");
  41.                 return;
  42.             }
  43.             rear++;//队列没满，就把尾部往后移一个位置
  44.             arr[rear] = n;
  45.         }
  47.         //获取队列数据，出队列
  48.         public int getQueue()
  49.         {
  50.             if (isEmpty())
  51.             {
  52.                 throw new Exception("队列为空，不能取数据");
  53.             }
  54.             front++;//front本身指向队列的前一个位置，++后就能指向当前队列的第一个位置，取出它 
  55.             return arr[front];
  56.         }
  58.         //显示队列所有数据
  59.         public void showQueue()
  60.         {
  61.             if (isEmpty())
  62.             {
  63.                 Console.WriteLine("队列为空，没有数据");
  64.                 return;
  65.             }
  66.             for(int i = front + 1; i <= rear; i++)
  67.             {
  68.                 Console.WriteLine(arr[i]);
  69.             }
  70.         }
  72.         //显示队列的头数据，不是取数据，front不用后移
  73.         public int headQueue()
  74.         {
  75.             if (isEmpty())
  76.             {
  77.                 throw new Exception("队列为空，没有头数据");
  78.             }
  79.             return arr[front+1];
  80.         }
  81.     }
  82. }

这种方法的弊端就是队列只能用一次，取出了数据后，数组前面的位置哪怕你把它清空了，还是占着位置。

数组模拟环形队列

思路

根据上面的数组模拟队列的代码进行一定的更改调整。

  1. front变量含义改变，front指向队列的第一个元素，front初始值为0
  2. rear变了含义改变，rear指向队列的最后一个元素的后一个位置，数组最后一个位置空着，预留一个空位，那个位置不装数据。rear初始值为0
  3. 当队列满时，条件是(rear+1)%maxSize=front
  4. 队列为空的条件，rear=front
  5. 有效数据个数，(rear+maxSize-front)%maxSize

image.png

用数组构成环形队列的里面，为什么会有空余？因为添加方法里面arr[rear] = n，添加后，rear = (rear + 1)%maxSize后移，然后再次循环的时候会进行一个是否满的判断，isFull()方法里面是进行的(rear+1)%maxSize == front，假设在倒数第二个位置（6）进行了添加，即arr[rear] = n （PS：这个里rear为maxSize -2），然后rear自增1变成maxSize -1，下次循环进行isFull()判断，rear又加1,变成maxSize，然后取模变成了0，与front相同，这时候队列满，所以这个maxSize-1这个位置并没有存入数据，所以空留了一个空间。

环形队列最后一位被牺牲（front在0，7就是空位，front在4，3就是空位…），不会用到，因为希望空出一个位置来做约定，判断队列是否满）（满的情况是除了最后一个被浪费，其余都有数据）,所以说环形队列是比如你得maxSize是1，就算里面没数据，队列也算满了。

判断队列为空，队列头指针等于尾指针 判断队列为满，队列头指针等于尾指针 ？ 满状态和空状态，判断的条件一样的，为了对其进行区分，最简单的解决办法是：牺牲掉数组中的一个存储空间，判断数组满员的条件是：尾指针的下一个位置（rear）和头指针（front）相遇，就说明数组满了

image.pngimage.png

代码

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Text;
  5. namespace ConsoleApp1
  6. {
  7.     class CircleArrayQueue
  8.     {
  9.         private int maxSize;//数组的最大容量
  10.         private int front;//队列头的指针，指向队列的第一个数据，初始就是0
  11.         private int rear;//队列尾的指针，指向队列的最后一个数据的后一个，初始就是0
  12.         private int[] arr;//该数组用于存放队列的数据
  14.         public CircleArrayQueue(int arrMaxSize)
  15.         {
  16.             maxSize = arrMaxSize;
  17.             arr = new int[maxSize];
  18.         }
  20.         //判断队列是否满
  21.         public bool isFull()
  22.         {
  23.             return (rear + 1) % maxSize == front;
  24.         }
  26.         //判断队列是否为空
  27.         public bool isEmpty()
  28.         {
  29.             return rear == front;
  30.         }
  32.         //添加数据到队列，n是数据
  33.         public void addQueue(int n)
  34.         {
  35.             if (isFull())
  36.             {
  37.                 Console.WriteLine("队列满了，不能加数据");
  38.                 return;
  39.             }
  40.             /*rear指向的是最后一个元素的后一个位置，假设现在最后一个元素3，有数据，那么rear指向的是4，还没有数据，可以直接赋值个arr[rear]
  41.              * 赋值完成后，现在的最后一个元素是4，rear向后移一位，指向5，5还没有数据.....
  42.              */
  43.             arr[rear] = n;
  44.             /*rear向后移，不是随便移的，一直移就会索引越界。假设容量为8，现在添加的就是最后一个数据，索引7。加完了以后，rear要移动到后一位8，下次再添加时arr[8]就越界了
  45.              * 这时候模一个maxSize，就可以从头开始，比如(7+1)%8=0，表示现在rear指向最后一个数据的一个位置，下一个位置是0，下次添加的时候就arr[0]
  46.              * 但是，环形队列的最后一位不用使用，maxSize-2就是这个环形队列的最后个元素。(6+1)%8=7,这时候rear等于7，当下一次添加数据时，要判断是否满
  47.              * isFull得出(7+1)%8=0,如果front也是0，(7+1)%8=front,就表示满了，比如front在索引3，那么索引2就是预留的空位
  48.              */
  49.             rear = (rear + 1) % maxSize;
  50.         }
  52.         //获取队列数据，出队列
  53.         public int getQueue()
  54.         {
  55.             if (isEmpty())
  56.             {
  57.                 throw new Exception("队列为空，不能取数据");
  58.             }
  60.             //front本身就只第一个元素，先保存到一个临时变量，然后front往后移，再返回数据
  61.             int val = arr[front];
  62.             //front往后移动和rear往后移动同样的原理，为了避免数组越界，+1后模一个maxSzie
  63.             front = (front + 1) % maxSize;
  64.             return val;
  66.         }
  68.         //求出当前队列的有效数据个数
  69.         public int size()
  70.         {
  71.             return (rear + maxSize - front) % maxSize;
  72.         }
  73.         //显示队列所有数据
  74.         public void showQueue()
  75.         {
  76.             if (isEmpty())
  77.             {
  78.                 Console.WriteLine("队列为空，没有数据");
  79.                 return;
  80.             }
  81.             for(int i = front; i < front + size(); i++)
  82.             {
  83.                 Console.WriteLine(arr[i % maxSize]);
  84.             }
  85.         }
  87.         //显示队列的头数据，不是取数据，front不用后移
  88.         public int headQueue()
  89.         {
  90.             if (isEmpty())
  91.             {
  92.                 throw new Exception("队列为空，没有头数据");
  93.             }
  94.             return arr[front];
  95.         }
  97.     }
  98. }

参考

什么是队列，队列及其应用（超详细）