循環隊列

什么是隊列？

隊列(Queue)也是一種運算受限的線性表。它僅僅同意在表的一端進行插入，而在還有一端進行刪除。同意刪除的一端稱為隊頭(front)，同意插入的一端稱為隊尾(rear)。

FIFO原則

隊列具有先進先出原則，與棧的先進后出形成對照。

為什么設計循環隊列？

隊列的順序存儲結構稱為順序隊列，順序隊列實際上是運算受限的順序表，和順序表一樣，順序隊列也是必須用一個向量空間來存放當前隊列中的元素。

入隊，出隊操作原理

因為隊列的隊頭和隊尾的位置是變化的，因而要設兩個指針和分別指示隊頭和隊尾元素在隊列中的位置，它們的初始值地隊列初始化時均應置為０。入隊時將新元素插入所指的位置，然后將加１。出隊時，刪去所指的元素，然后將加１并返回被刪元素。

杜絕“假上溢”

和棧類似，隊列中亦有上溢和下溢現象。此外，順序隊列中還存在“假上溢”現象。由于在入隊和出隊的操作中，頭尾指針僅僅添加不減小，致使被刪除元素的空間永遠無法又一次利用。因此，雖然隊列中實際的元素個數遠遠小于向量空間的規模，但也可能由于尾指針巳超出向量空間的上界而不能做入隊操作。

為充分利用向量空間。克服上述假上溢現象的方法是將向量空間想象為一個首尾相接的圓環，并稱這樣的向量為循環向量，存儲在當中的隊列稱為循環隊列（Circular?Queue)。在循環隊列中進行出隊、入隊操作時，頭尾指針仍要加1，朝前移動。僅僅只是當頭尾指針指向向量上界（QueueSize-1）時，其加1操作的結果是指向向量的下界0。

實現代碼：

if(I+1 == QueueSize)
{I = 0;
}
else
{i++;
}

利用模運算可簡化為：

i = (i + 1)%QueueSize；

何時隊列為空？何時為滿？

因為入隊時尾指針向前追趕頭指針，出隊時頭指針向前追趕尾指針，故隊空和隊滿時頭尾指針均相等。因此，我們無法通過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 DeQueue(cirqueue *q)
{datatype temp;assert(QueueEmpty(q) == 0);//q空，則終止程序，打印錯誤信息temp = q->data[q->front];q->count--;q->front = (q->front + 1)%QueueSize;return temp;
}

取頭指針

//取頭指針
datatype QueueFront(cirqueue *q)
{assert(QueueEmpty(q) == 0);return (q->data[q->front]);
}