队列的介绍与实现
前面几篇文章，我们介绍了链表，栈。他们都有各自独特的性质，接下来我们来看看队列。
队列和栈很像，但是它遵循先进先出(FIFO——first in first out)的原则！这也让他看上去更守规矩，像排队一样。
栈有栈顶，而队列则有队头（front）和队尾（rear)。
队列通常由以下几种方法（不同的库实现的名称可能不一致！）：
- EnQueue(x)——入队：入队操作应该在队列尾部插入一个元素。
- DeQeue()——出队：也是队列的删除操作，应该从对头删除！并且会返回删除的元素。
- front()或peek()——返回队头：这个类似栈里面的top（）
- IsEmpty
这些方法的时间复杂度均为O（1）
一、模拟入队出队
不同于我们的栈是一端开口的，队列是两端开口，长下面的样子
当前入队了一个2，所以队头front和队尾指针都指着他。
再插入两个元素就会变成这样
我们来删除一个元素
对头的2会被删除，并且我们会拿到这个被作为返回值的2.
二、使用场景
什么时候会去使用队列呢？常见的如下
- 服务器处理请求
- 内核调度进程
- 12306抢票候车
- 巴拉巴拉
三、数组实现队列
我们创建一个数组，然后取他的部分作为队列！
如果要增加元素，我们可以移动rear，使队列扩张。
这里增删了队列里的元素，同时front和rear也增加了！我们可以不管front之前的那个值，因为可以将其覆盖。
好啦，我们回到创建数组哪里。
对于空队列来说，根本没有front和rear，这里我们只是利用伪代码演示，-1也是个假想值。
我们还可以顺便借着这个特性实现一下检查是否为空。
接着我们实现了入队方法，囊括了满队（超出数组边界），空队，正常入队的情景。
现在我们来模拟一下🤔
我们让2入队，一开始为空队，所以会走else if的分支，挪动front和rear指向0，并写入2.
接着我们实现一下出队方法。
特殊情况有，队列为空，队列只有一个元素。
在我们的一顿操作之下，添加和删除了很多元素，现在rear到了申请的数组尽头。
这里前两个为了简化所以我没有画数字进去，实际上还是存在数字的，我们只是移动了指针而已。
到这里你可能会发现问题了，前面两个空我们好像使用不了啊！？他们就被白白浪费了吗？🤔
我们可以利用循环数组来解决这个问题。
循环数组如由上图
对于当前位置我们设为i，那么下一个位置则不能简单的取i+1，而是(i+1)%N，N是数组大小。
为什么会这样？？？你用脚趾头想想，走到9后再i+1会跑哪去💢
取先前的位置则如上，这里不用i-1而加了个N的目的是转成正数。
既然用了循环数组了，那我们继续修改一下之前的伪代码
我们执行在队头添加11，删除队尾元素。原本在9的rear，走else分支使得rear=(1+9)%10 =0所以11被加到了0里面。
删除同理。
四、代码实现
#include<iostream>using namespace std;int front=-1;int rear=-1;int A[4];bool isEmpty(){ if(front==-1&&rear==-1){ return true; } else return false;}void Enqueue(int x,int N){ //数组饱满的情况 if((rear+1)%N==front)return; //空队列情况 else if(isEmpty()){ front=rear=0; } else{ rear=(rear+1)%N; } A[rear]=x;}void Dequeue(int N){ if(isEmpty()){ return; } else if(front==rear){ front=rear=-1; } else{ front=(front+1)%N; }}void print() { if (isEmpty()) { cout << "Empty queue\n"; return; } int i = front; while (true) { cout << A[i] << " "; if (i == rear) break; // 到达尾部就停 i = (i + 1) % 4; //循环数组下一位 } cout << endl;}int main(){ int n=sizeof(A) / sizeof(A[0]); //一个int类型占四个字节，这里整除，不能直接用sizeof会返回16！ Enqueue(1,n); Enqueue(2,n); Enqueue(3,n); Enqueue(4,n); print(); Dequeue(n); Dequeue(n); Enqueue(5,n); print(); return 0;}部分信息可能已经过时