一 隊列的定義
隊列（queue）是隻允許在一端進行插入，而在另一端進行删除的運算受限的線性表
（1）允許删除的一端稱為隊頭（front）。
（2）允許插入的一端稱為隊尾（rear）。
（3）當隊列中沒有元素時稱為空隊列。
（4）隊列亦稱作先進先出（first in first out）的線性表，簡稱為fifo表。
二 順序隊列
隊列的順序存儲結構稱為順序隊列，順序隊列實際上是運算受限的順序表。
基本操作：
入隊時：将新元素插入rear所指的位置，然後将rear加1。
出隊時：删去front所指的元素，然後将front加1并傳回被删元素。
三 循環隊列
為充分利用向量空間，克服"假上溢"現象的方法是：将向量空間想象為一個首尾相接的圓環，并稱這種向量為循環向量。存儲在其中的隊列稱為循環隊列（circular queue）。即：循環隊列中進行出隊、入隊操作時，頭尾指針仍要加1，朝前移動。隻不過當頭尾指針指向向量上界（queuesize-1）時，其加1操作的結果是指向向量的下界0。
（1）循環意義上的加1操作可以
① 方法一：
if(i+1==queuesize) //i表示front或rear
i=0;
else
i++;
② 方法二： 利用"模運算"
i=(i+1)%queuesize；
（2）循環隊列的邊界問題
循環隊列中，由于入隊時尾指針向前追趕頭指針；出隊時頭指針向前追趕尾指針，造成隊空和隊滿時頭尾指針均相等。是以，無法通過條件front==rear來判别隊列是"空"還是"滿"。
解決這個問題的方法至少有三種：
① 另設一布爾變量以差別隊列的空和滿；
② 少用一個元素的空間。約定入隊前，測試尾指針在循環意義下加1後是否等于頭指針，若相等則認為隊滿（注意：rear所指的單元始終為空）；
③使用一個計數器記錄隊列中元素的總數（即隊列長度）。
（3）循環隊列資料類型
#define queursize 100 //應根據具體情況定義該值
typedef char datatype; //datatype的類型依賴于具體的應用
typedef struct{
int front; //頭指針，隊非空時指向隊頭元素
int rear; //尾指針，隊非空時指向隊尾元素的下一位置
int count;//計數器，記錄隊中元素總數
datatype data[queuesize]
}cirqueue;
（4）循環隊列的基本運算
① 置隊空
void initqueue(cirqueue *q)
{
q->front=q->rear=0;
q->count=0; //計數器置0
}
② 判隊空
int queueempty(cirqueue *q)
{
return q->count==0; //隊列無元素為空
}
③ 判隊滿
int queuefull(cirqueue *q)
{
return q->count==queuesize; //隊中元素個數等于queuesize時隊滿
}
④ 入隊
void enqueue(cirqueuq *q,datatype x)
{
if(queuefull((q))
{
printf("queue overflow"); //隊滿上溢
exit(1);
}
q->count ++; //隊列元素個數加1
q->data[q->rear]=x; //新元素插入隊尾
q->rear=(q->rear+1)%queuesize; //循環意義下将尾指針加1
⑤ 出隊
datatype dequeue(cirqueue *q)
{
datatype temp;
if(queueempty((q))
{
printf("queue underflow"); //隊空下溢
}
temp=q->data[q->front];
q->count--; //隊列元素個數減1
q->front=(q->front+1)%queuesize; //循環意義下的頭指針加1
return temp;
}
⑥取隊頭元素
datatype queuefront(cirqueue *q)
if(queueempty(q))
{
printf("queue if empty.");
}
return q->data[q->front];
}
轉載：http://blog.csdn.net/xsf50717/article/details/39937085