循环队列的实现（静态数组实现）

竟然立了一个flag，说好的每个星期一篇数据结构的博文……….顿时心塞

开始把开始吧

今天我们来了解并实现循环队列（静态数组）这一数据结构。

队列和栈都是两种非常重要而且非常常见的数据结构类型。前一期我们说了栈这个结构是后进先出；而今天讲的队列这个结构呢，是先进先出，后进后出，类似于排队买票，先排的人先买到票，后排的人后买到票。这个就是队列的特殊地方。

讲完了队列这个结构。现在我们讲讲如何用代码去实现这个数据结构。

队列这个结构可以用链表，也可以用静态数组实现。链表实现的形式其实很简单，只需要将上一期的栈结构的代码稍作改动就可以实现队列这个结构。今天我们来讲讲用静态数组来实现，还是循环队列。（这里盗用下某篇博客的图片）

我们可以看到，在普通的静态数组实现的队列这一数据结构中，如果一开始1,2,3三个数据入队列后再出列，那么头结点就在3这个位置，这个时候在将4,5,6三个数据入队列，之后就会告诉你队列已经“满了”，然而这个满不是真的满，为了有效的利用空间，我们就想，能不能将这个数组循环起来，以便于充分的利用空间——因此才有了循环队列的数组实现形式。（再次盗用下某篇博客的图片）

我们可以看到，我们已经将静态数组“循环化”，很容易看出，队列空的状态条件为queue.front==queue.rear，队列满的条件也是queue.front==queue.rear，这里就有一个问题。这两个状态如何区分？很简单，有两种解决方案，一是像图中所示，我们牺牲一个单元，用来区分；二是加入一个操作判别状态，如果你是执行入队操作，那么操作判别状态为插入，此时如果queue.front==queue.rear时，就是队列已经满了，如果是出队操作，那么操作判别状态为出队，在下一次进行入队操作时，如果上一次操作状态为出队，此时的queue.front==queue.rear，则此时队列为空。在这里，我们将采用第一种解决方式，即牺牲一个存储单元进行区分。

那么，第一种方式的队列满和空的判别是如何实现呢？首先说下队列空的判别，就是queue.front==queue.rear，此时队列为空队列，如果(queue.rear+1) % MAXSIZE == queue.front时，队列已经满了。这个公式的得来是由于我们约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。我们不清楚当前的队列的对头结点是不是在0这个位置，如果是，那么对头与对尾的位置差为MAXSIZE-1，求余就是因为循环这个特殊的性质。接下来，我们来看看具体的代码实现：

#include <iostream>
using namespace std;

typedef struct {
    int queue[6];
    int front;
    int rear;
} LQueue;

void InitQueue(LQueue &amp;Lq) {
    Lq.front = Lq.rear = 0;
}

void IntoQueue(LQueue &amp;Lq, int i) {
    if ((Lq.rear + 1) % 6 == Lq.front)
        return;
    Lq.queue[Lq.rear] = i;
    Lq.rear = (Lq.rear + 1) % 6;
}

void OutQueue(LQueue &amp;Lq, int &amp;e) {
    if (Lq.rear == Lq.front)
        return;   //可能队列为空，没有元素可以出队列
    e = Lq.queue[Lq.front];
    Lq.front = (Lq.front + 1) % 6;
}

int main() {
    LQueue queue;
    InitQueue(queue);
}

（我学习的某篇博客：csdn博客地址 ）