1、順序循環(huán)隊(duì)列表實(shí)現(xiàn)作者：日期：2隊(duì)列的基本概念隊(duì)列也是一種特殊的線性表，隊(duì)列的數(shù)據(jù)元素以及數(shù)據(jù)元素間的邏輯關(guān)系與線性表完全相同，其差別是線性表允許在任意位置插入和刪除， 而隊(duì)列只允許在其一端進(jìn)行插入操作， 在其另一端進(jìn)行刪除操作。隊(duì)列中允許進(jìn)行插入操作的一端稱為隊(duì)尾。 允許進(jìn)行刪除操作的一端稱為隊(duì)頭。 隊(duì)頭和隊(duì)尾分別由隊(duì)頭指針和隊(duì)尾指針指示。 隊(duì)列的插入操作稱為入隊(duì)列， 隊(duì)列的刪除操作稱為出隊(duì)列。最先入隊(duì)列的元素總是最先出隊(duì)列，所以隊(duì)列也稱為先進(jìn)先出表。下圖是一個(gè)一次向隊(duì)列中插入數(shù)據(jù)元素 a0,a1,a2, .an-1 后的示意圖，其中， a0 是當(dāng)前隊(duì)頭數(shù)據(jù)元素， an-1 是當(dāng)前隊(duì)尾的數(shù)據(jù)

2、元素。隊(duì)頭隊(duì)尾a0a1a2an-1<-出<-入隊(duì)列抽象數(shù)據(jù)類型數(shù)據(jù)集合：隊(duì)列的數(shù)據(jù)集合可以表示為a0,a1,a2,a3.an-1，每個(gè)數(shù)據(jù)元素的數(shù)據(jù)類型為DataType。操作集合：（ 1） 初始化 QueueInitiate(Q) ：初始化隊(duì)列 Q（2）非空否 QueueNotEmpty(Q) ：隊(duì)列 Q 非空否，若隊(duì)列非空，函數(shù)返回值為1。否則，函數(shù)返回 0。（3）入隊(duì)列 QueueAppend(Q,x) ：在隊(duì)列 Q 的隊(duì)尾插入數(shù)據(jù)元素x。入隊(duì)列成功返回 1；失敗則返回 0。（4）出隊(duì)列 QueueDelete(Q,d)：把隊(duì)列 Q 的隊(duì)頭數(shù)據(jù)元素刪除并由參數(shù)d 帶回。如出隊(duì)

3、列成功，返回1；失敗則返回 0。（5）取隊(duì)頭數(shù)據(jù)元素QueueGet(Q,d)：取隊(duì)頭數(shù)據(jù)元素并由參數(shù)d 帶回。如取到數(shù)據(jù)元素返回 1，否則，返回0。順序隊(duì)列順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列稱作順序隊(duì)列3假設(shè)為隊(duì)列開(kāi)辟的數(shù)組單元數(shù)目為 MAX_QUEUE ，在 C 語(yǔ)言中，它的下標(biāo)在 0MAX_QUEUE-1 之間，若增加隊(duì)頭或隊(duì)尾指針， 可以利用取模運(yùn)算 （一個(gè)整數(shù)數(shù)值整除以另一個(gè)整數(shù)數(shù)值的余數(shù)） 實(shí)現(xiàn)。如下所示：front=(front+1)%MAX_QUEUE；rear=(rear+1)%MAX_QUEUE；當(dāng) front 或 rear 為 MAXQUEUE-1時(shí)，上述兩個(gè)公式計(jì)算的結(jié)果就為0。這樣，

4、就使得指針自動(dòng)由后面轉(zhuǎn)到前面，形成循環(huán)的效果。隊(duì)空和隊(duì)滿的標(biāo)志問(wèn)題：隊(duì)列變?yōu)榭?，?duì)頭和隊(duì)尾指針相等43順序循環(huán)隊(duì)列的實(shí)現(xiàn)根據(jù)對(duì)順序循環(huán)隊(duì)列的分析，其結(jié)構(gòu)體定義如下：typedef structDataType queueMaxQueueSize;int rear;/* 隊(duì)尾指針 */int front;/* 隊(duì)頭指針 */int count;/* 計(jì)數(shù)器 */SeqCQueue;采用計(jì)數(shù)器法判斷隊(duì)列空和滿的順序循環(huán)隊(duì)列的算法實(shí)現(xiàn)如下：（1）初始化 QueueInitiate(SeqCQueue *Q)void QueueInitiate(SeqCQueue *Q)/* 初始化順序循環(huán)隊(duì)列 Q*

5、/Q->rear=0;/* 定義初始化隊(duì)尾指針下標(biāo)值 */Q->front=0;/* 定義初始化頭指針下標(biāo)值*/Q->count=0;/* 定義初始化計(jì)數(shù)器值*/（2）非空否 QueueNotEmpty(SeqCQueue Q)intQueueNotEmpty(SeqCQueue Q)/* 判斷順序循環(huán)隊(duì)列Q 非空否，非空返回1，否則返回0*/if(Q.count!=0)return 1;else return 0;(3) 入隊(duì)列 QueueAppend(SeqCQueue *Q,DataType x)intQueueAppend(SeqCQueue *Q,DataType

6、x)/* 把數(shù)據(jù)元素值x 插入順序循環(huán)隊(duì)列Q 的隊(duì)尾，成功返回1，失敗則返回0*/5if(Q->count>0&&Q->rear=Q->front) /*判斷隊(duì)列滿否 */printf( “隊(duì)列已滿無(wú)法插入!n ”);return 0;elseQ->queueQ->rear=x;Q->rear=(Q->rear+1)%MaxQueueSize;Q->count+;return 1;(4) 出隊(duì)列 QueueDelete(SeqCQueue*Q,DataType *d)int QueueDelete(SeqCQueue*Q,DataType *d)/* 刪除順序循環(huán)隊(duì)列Q 的隊(duì)頭元素并賦給d，成功返回1，失敗返回0*/if(Q->count=0)printf( “隊(duì)列已空無(wú)數(shù)據(jù)元素出隊(duì)列!n ”);return 0;else*d=Q->queueQ->front;Q->front=(Q->front+1)%MaxQueueSize;Q->count-;return 1;(5) 取隊(duì)頭數(shù)據(jù)元素QueueGet(SeqCQueue Q,DataType *d)intQueueGet(SeqCQueue Q,DataType *d)/* 取順序循環(huán)隊(duì)