队列的基本概念
遵循先入先出的原则，即：先存入队列的数据，要先取出，后存入的要后取出。
就像排队打饭一样，来的早，走的也早（此早非彼早）
示意图：自己脑补
队列最基本的两个操作：
入队（enqueue），放一个数据到队列的尾部；
出队（dequeue）从队列头部取一个元素。
顺序队列和链式队列
用数组实现的队列叫顺序队列，用链表实现的队列叫链式队列。
我们先分析下基于数组实现的顺序队列：比如这里有一个Length为4的队列，默认是空值，啥也没有存入
队列有两个指针，队头，Head，队尾，Rear
队列初始状态
- head = 0; 队头
- rear = 0; 队尾
队列的大小为size，队列数组的第一个元素下标为0，最后一个元素的下标为size-1。
代码如下
private int head=0;//队头
private int rear=0;//队尾
private int size=0;//长度
private int[] arr;//队列数组
//用构造函数初始化队列
public Queue(int size)
{
this.size = size;
arr = new int[size];
}
入队
给数组队列加入数据6，7
每加入一个数据，rear(队尾) 就向后移动一位，队头(Head) 不动，当tail == size 时表示队列已满。
代码如下：
//入队
public void AddData(int num)
{
//判断是否已满
if (size==rear)
{
Console.WriteLine("添加失败，队列已满");
return;
}
arr[rear] = num;
rear++;
Console.WriteLine(num+"：加入队列");
}
出队
即 按照先进先出的原则，取出数据
当6出队之后，队头(Head) 指针向后移动一个位置，队尾指针rear指向不变，当head == rear 时表示队列为空。
代码如下：
//出队
public Integer dequeue() {
// 判断队列是否为空
if(head == rear) {
return null;
}
int item = arr[head];
head++;
return item;
}
话不多说，奉上全部代码
private int head=0;//队头
private int rear=0;//队尾
private int size=0;//长度
private int[] arr;//队列数组
//初始化队列
public Queue(int size)
{
this.size = size;
arr = new int[size];
}
//入队
public void AddData(int num)
{
//判断是否已满
if (size==rear)
{
Console.WriteLine("添加失败，队列已满");
return;
}
arr[rear] = num;
rear++;
Console.WriteLine(num+"：加入队列");
}
//出队
public Integer dequeue() {
// 判断队列是否为空
if(head == rear) {
return null;
}
int item = arr[head];
head++;
return item;
}
//获取队列首位元素
public void GetOneElement()
{
if (head==rear)
{
Console.WriteLine("获取失败，队列为空");
return;
}
Console.WriteLine("首位元素：" + arr[head]);
}
//元素
public void QueueList()
{
if (head==rear)
{
throw new Exception("队列为空");
}
Console.WriteLine("--------------------遍历队列-----------------------");
foreach (var a in arr)
{
Console.Write(" "+a);
}
Console.WriteLine();
}
实现以上代码后，问题来了！！！
首先我这里重新定义一下队头和队尾
队尾：Head，队头：Tail
这里有两个需要特别注意的地方
- 入队时判断队列已满条件
tail == size - 出队时判断队列为空条件
head == tail
随着不断的入队和出队操作，最后head和tail都会一直向队尾移动，当head == tail && tail == size的时候，如下图所示，即使队列有空闲空间也无法向队列中添加任何元素了，也就是说，我们上面创建的队列只能使用一次。
如何解决这个问题呢，我们可以使用循环队列，现在的队列是一条直线，如果我们把首尾相连就形成了一个环，如下图所示：
循环队列
我可以用循环队列来解决顺序队列只能使用一次的问题。在循环队列中，我们依然需要使用两个变量head（指向队列中的第一个元素，初始值为0）和tail（指向队列中最后一个元素的下一个位置，初始值为0）。
在顺序队列中，我们需要判断队空和队满的情况，同样在循环队列也需要判断队满和队空的情况。
上图中这个队列大小size为8，开始队列空时head和tail都指向下标0。依次添加元素a、b，此时如上图所示head位置不变，tail向后移指向下标为2的位置。继续添加元素c、d、e、f、g， 此时tail指向了最后一个位置。
数组实现的非循环队列中，队空的情况是head == tail，循环队列中队空的情况也是head == tail。非循环队列中队满的情况是tail == size，循环队列中队满的情况是(tail + 1) % size == head。
上图可以看出，当队列满时，tail指向的位置是没有存储元素的。如果我们想要最后一个位置也存储元素，那么tail需要继续向后移动一个位置，此时tail和head指向了同一个位置，与队列为空的情况是一样的条件head == tail，
所以我们约定牺牲一个存储空间来区分队空和队满的情况。
同样可以计算出队列中实际有效元素的个数为 (tail + size - head) % size。
下面我们使用代码来实现循环队列：
private int[] arr;
private int size;
private int tail = 0;
private int head = 0;
public QueueLoop(int size)
{
this.size = size;
arr = new int[size];
}
//入列
public void Add(int num)
{
//判断队列是否已满
if ((tail + 1) % size == head)
{
Console.WriteLine("队列已满，不能再添加");
return;
}
arr[tail] = num;
// (n+1) % size 相当于取 1~size的范围，（不包含size）
tail = (tail + 1) % size;
}
//出列
public void DeQueue()
{
//判断队列是否为空
if (head == tail)
{
Console.WriteLine("队列元素为空");
return;
}
Console.Write(" " + arr[head]);
head = (head + 1) % size;
}
//获取头元素
public void GetHeadElement()
{
//判断队列是否为空
if (head == tail)
{
Console.WriteLine("队列元素为空");
return;
}
Console.WriteLine("头元素" + arr[head]);
}
public void QueueList()
{
// 实际有效元素个数
int num = (tail + size - head) % size;
for (int i = head, len = head + num; i < len; i++)
{
Console.Write(" "+arr[i % size]);
}
}
注意：素材来源于网络，仅作为学习笔记记录
本人充分尊重原创劳动成果：如有侵权纠纷，请留言反馈，谢谢
