队列② 顺序队列和循环队列

摘要：讲解了顺序队列的原理和基本操作，由于顺序队列解决假溢出效率低，引入循环队列的概念。

一个空的顺序队列长这个样：

存储空间基址是队列首节点的地址。把这个顺序队列看成一个通道，数据从上面依次存入队列。从上方进来一个数据，尾指针就向上移动一个单位；从下方取出一个数据，头指针就向上移动一个单位。所以顺序队列的头指针和尾指针都不是真的指针，而是整数，它们参照存储空间基址进行位置变动。

typedef struct
{
        int* base;
        int front;
        int rear;
}SQue;

为了形象地讲解一些概念，在下方我构建了一个顺序队列 Q：

#include<stdio.h>
#include<stdlib.h>

#define OK 0
#define ERR -1

typedef struct
{
        int* base;
        int front;
        int rear;
}SQue;

//声明我自定义的顺序队列类型的变量Q
SQue Q;

//开辟空间
Q.base = (int*)malloc(10);
//现在我依次存入{1,2,3,6,6,8}，从上方每进来一个数据，尾指针就向上移动一个单位
Q.base[Q.rear] = 1; Q.rear++;
Q.base[Q.rear] = 2; Q.rear++;
Q.base[Q.rear] = 3; Q.rear++;
Q.base[Q.rear] = 6; Q.rear++;
Q.base[Q.rear] = 6; Q.rear++;
Q.base[Q.rear] = 8; Q.rear++;

这时候可以发现，Q.rear 的值变成了6，指到队列外面的空间了。这时候队列满了，叫溢出，溢出了就不能再存数据了。现在队列中的6个位置都存放了数据，这种情况称为队列真溢出，队列的空间被充分利用了。

接着前边的代码，我从队列取一个数据放到我的数组里， 从下方每取出一个数据，头指针就向上移动一个单位 。

   maxsize = 6;
   int e = 0;
   e = Q.base[Q.front]; Q.front++;

拷走首节点的数据后，头指针上移一位。这时首节点中的数据已经失去了价值，队列中只存放了5个有价值的数据。从宏观上想，队列能存6个数据，现在只存了5个，已经可以存放新数据了。但是实际上，队列没有办法存放新的数据，因为我们看上面那个逻辑图，最上面还是没有空间，这种情况称为假溢出。设计算法时，应该避免假溢出，使队列的空间得到充分利用，进行高效率的数据处理。

如果顺序队列要解决假溢出的问题，需要将队列中的所有数据下移一个单位，头指针和尾指针也下移一个单位：

int i = 0; 
for(;i < maxsize ;i++)
{
     Q.base[i-1] = Q.base[i];
}
Q.rear--;
Q.front--;

这样的话就解决了假溢出的问题，可以存放新的数据了。但是这样操作的话，每加入一个新数据，每个数据都要下移一位，效率太低了吧。有人问这么麻烦干什么，把空间基址往上移一位不就行了？好家伙，你每存一个数据，基址就往上移动一位，那你占用新的空间存数据叫做越界，这是很严重的问题。

为了更好解决假溢出的问题，就引入了循环队列的概念。把上文提到的顺序队列首尾相接就得到了循环队列：

可以注意到两个问题：

1. 尾指针没有指向存储空间之外，而是回到了 0 。这是怎么实现的呢? 用到了取模，即 (指针+1) mod maxsize，比如Q.rear == maxsize – 1时, 那么 (Q.rear+1) mod maxsize == 0；
2. 在队满和队空时，头尾指针相等。如何区分队满和队空呢? 那就是在 (尾指针+1) mod maxsize == 头指针 时，是队满，否则是队空。

明白了这些就可以构造一个循环队列并进行操作了。

/* 构造循环队列 */
int initCircleQueue(SQue &Q)
{
        Q.base = (int *)malloc(MAXQSIZE);
        if(!Q.base)
          exit(ERR);
        Q.front = Q.rear = 0;
        return OK;
}

/* 将数据存入循环队列 */
int inCircleQue(SQue &Q)
{
       //判断是否队满
       if((Q.rear + 1) % maxsize == Q.front)
           return ERR;
       //存数据
       Q.base[Q.rear] = e;
       //更新尾指针的位置
       Q.rear = (Q.rear + 1) % maxsize;
       return OK;
}

/* 数据从循环队列出队 */
int outCircleQue(SQue &Q)
{
     //判断是否队空
     if(Q.rear == Q.front)
         return ERR;
     //取数据
     e = Q.base[Q.front];
     //更新头指针的位置
     Q.front = (Q.front + 1) % maxsize;
     return OK;
}

参考资料：《数据结构与算法考研复习指导》— 王道考研系列