循环队列

什么是队列？

队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。

FIFO原则

队列具有先进先出原则，与栈的先进后出形成对比。

为什么设计循环队列？

队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队列中的元素。

入队，出队操作原理

由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置，它们的初始值地队列初始化时均应置为０。入队时将新元素插入所指的位置，然后将加１。出队时，删去所指的元素，然后将加１并返回被删元素。

杜绝“假上溢”

和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的

空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。

为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。

实现代码：

if(I+1 == QueueSize)

{

    I = 0;

}

else

    i++;

利用模运算可简化为：

何时队列为空？何时为满？

由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。

注：先进入的为‘头’，后进入的为‘尾’。

解决此问题的方法至少有三种：

其一是另设一个布尔变量以匹别队列的空和满；

其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；

其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）。

队列的基本操作：

数据元素定义

#include <stdio.h>

#include <assert.h>

#define QueueSize 100

typedef char datatype;

//队列的数据元素

typedef struct

     int front;

     int rear;

     int count;  //计数器，用来记录元素个数

     datatype data[QueueSize]; //数据内容

}cirqueue;

队列置空

//置空队

void InitQueue(cirqueue *q)

     q->front = q->rear = 0;

     q->count = 0;

//判断队满

int QueueFull(cirqueue *q)

     return (q->count == QueueSize);

//判断队空

int QueueEmpty(cirqueue *q)

     return (q->count == 0);

入队

//入队

void EnQueue(cirqueue *q, datatype x)

     assert(QueueFull(q) == 0); //q满，终止程序

     q->count++;

     q->data[q->rear] = x;

     q->rear = (q->rear + 1)%QueueSize; //循环队列设计，防止内存浪费

• //取头指针
• datatype QueueFront(cirqueue *q)
•      assert(QueueEmpty(q) == 0);
•      return (q->data[q->front]);
• //队内有效长度
• （rear-front+N）%N