1、2016數(shù)據(jù)結(jié)構(gòu)Data structure講授：司蕾3.4 循環(huán)隊列及其操作常州信息職業(yè)技術(shù)學(xué)院0203循環(huán)隊列-描述3.41循環(huán)隊列（Cirular Queue） 把向量空間的元素位置首尾相接的順序隊列稱為循環(huán)隊列?！臼纠?-4】設(shè)隊列的容量QueueSize=8，元素a1，a2，a3，a4，a5，a6，a7依次入隊，然后a1，a2，a3出隊的循環(huán)隊列如圖。07654321frontrear03循環(huán)隊列-描述3.41循環(huán)隊列（Cirular Queue） 把向量空間的元素位置首尾相接的順序隊列稱為循環(huán)隊列?！臼纠?-4】設(shè)隊列的容量QueueSize=8，元素a1，a2，a3，a4，a5，

2、a6，a7依次入隊，然后a1，a2，a3出隊的循環(huán)隊列如圖。07654321a1frontrear03循環(huán)隊列-描述3.41循環(huán)隊列（Cirular Queue） 把向量空間的元素位置首尾相接的順序隊列稱為循環(huán)隊列?！臼纠?-4】設(shè)隊列的容量QueueSize=8，元素a1，a2，a3，a4，a5，a6，a7依次入隊，然后a1，a2，a3出隊的循環(huán)隊列如圖。07654321a1a2frontrear03循環(huán)隊列-描述3.41循環(huán)隊列（Cirular Queue） 把向量空間的元素位置首尾相接的順序隊列稱為循環(huán)隊列。07654321a1a3a2frontrear【示例3-4】設(shè)隊列的容量Queu

3、eSize=8，元素a1，a2，a3，a4，a5，a6，a7依次入隊，然后a1，a2，a3出隊的循環(huán)隊列如圖。03循環(huán)隊列-描述3.41循環(huán)隊列（Cirular Queue） 把向量空間的元素位置首尾相接的順序隊列稱為循環(huán)隊列。07654321a1a4a3a2frontrear【示例3-4】設(shè)隊列的容量QueueSize=8，元素a1，a2，a3，a4，a5，a6，a7依次入隊，然后a1，a2，a3出隊的循環(huán)隊列如圖。03循環(huán)隊列-描述3.41循環(huán)隊列（Cirular Queue） 把向量空間的元素位置首尾相接的順序隊列稱為循環(huán)隊列。07654321a1a5a4a3a2frontrear【示例

4、3-4】設(shè)隊列的容量QueueSize=8，元素a1，a2，a3，a4，a5，a6，a7依次入隊，然后a1，a2，a3出隊的循環(huán)隊列如圖。03循環(huán)隊列-描述3.41循環(huán)隊列（Cirular Queue） 把向量空間的元素位置首尾相接的順序隊列稱為循環(huán)隊列。07654321a1a6a5a4a3a2frontrear【示例3-4】設(shè)隊列的容量QueueSize=8，元素a1，a2，a3，a4，a5，a6，a7依次入隊，然后a1，a2，a3出隊的循環(huán)隊列如圖。03循環(huán)隊列-描述3.41循環(huán)隊列（Cirular Queue） 把向量空間的元素位置首尾相接的順序隊列稱為循環(huán)隊列。07654321a1a7

5、a6a5a4a3a2frontrear【示例3-4】設(shè)隊列的容量QueueSize=8，元素a1，a2，a3，a4，a5，a6，a7依次入隊，然后a1，a2，a3出隊的循環(huán)隊列如圖。03循環(huán)隊列-描述3.41循環(huán)隊列（Cirular Queue） 把向量空間的元素位置首尾相接的順序隊列稱為循環(huán)隊列。07654321a7a6a5a4a3a2frontrear【示例3-4】設(shè)隊列的容量QueueSize=8，元素a1，a2，a3，a4，a5，a6，a7依次入隊，然后a1，a2，a3出隊的循環(huán)隊列如圖。03循環(huán)隊列-描述3.41循環(huán)隊列（Cirular Queue） 把向量空間的元素位置首尾相接的順

6、序隊列稱為循環(huán)隊列。07654321a7a6a5a4a3frontrear【示例3-4】設(shè)隊列的容量QueueSize=8，元素a1，a2，a3，a4，a5，a6，a7依次入隊，然后a1，a2，a3出隊的循環(huán)隊列如圖。03循環(huán)隊列-描述3.41循環(huán)隊列（Cirular Queue） 把向量空間的元素位置首尾相接的順序隊列稱為循環(huán)隊列。07654321a7a6a5a4frontrear【示例3-4】設(shè)隊列的容量QueueSize=8，元素a1，a2，a3，a4，a5，a6，a7依次入隊，然后a1，a2，a3出隊的循環(huán)隊列如圖。03循環(huán)隊列-描述3.41循環(huán)隊列（Cirular Queue） 把向

7、量空間的元素位置首尾相接的順序隊列稱為循環(huán)隊列。07654321a8a7a6a5a4思考：在示例基礎(chǔ)上再次入隊a8frontreari=(i+1)%QueueSize【示例3-4】設(shè)隊列的容量QueueSize=8，元素a1，a2，a3，a4，a5，a6，a7依次入隊，然后a1，a2，a3出隊的循環(huán)隊列如圖。03循環(huán)隊列-描述3.41循環(huán)隊列（Cirular Queue） 把向量空間的元素位置首尾相接的順序隊列稱為循環(huán)隊列。思考：在示例基礎(chǔ)上再次入隊a8思考： 如何表示隊列滿count計數(shù)，入隊一次加1，出隊一次減1隊列滿：count=QueueSizei=(i+1)%QueueSize076

8、54321a8a7a6a5a4rearfronta3a2a1【示例3-4】設(shè)隊列的容量QueueSize=8，元素a1，a2，a3，a4，a5，a6，a7依次入隊，然后a1，a2，a3出隊的循環(huán)隊列如圖。04循環(huán)隊列-描述3.42、循環(huán)隊列的描述#define QueueSize 100 /定義隊列最大容量typedef char DataType; /定義隊列元素類型typedef struct cirqueue DataType dataQueueSize;/隊列元素定義 int front;/隊頭指針定義 int rear;/隊尾指針定義 int count;/計數(shù)器定義CirQueue

9、; CirQueue *Q; /定義循環(huán)隊列Q05循環(huán)隊列-描述3.43、說明：（1）使用一個計數(shù)器count記錄隊列中元素的總數(shù)，計數(shù)器可表示為Q- count，當(dāng)Q-count =0時表示隊列空；當(dāng)Q-count =QueueSize時表示隊列滿。（2）設(shè)Q是CirQueue類型的指針變量，則Q是指向循環(huán)隊列的指針，隊頭指針、隊尾指可分別表示為Q-front、Q- rear。（3）隊頭元素可表示為Q-dataQ-front，隊尾元素可表示為Q-dataQ- rear。三、鏈表的插入06循環(huán)隊列-入隊3.41、入隊2、算法思路： 判斷隊列Q是否隊滿，當(dāng)隊列滿時，提示 “隊滿”返回0if(Qu

10、eueFull(Q) puts(隊滿); return 0;07654321a8a7a6a5a4rearfronta3a2a1三、鏈表的插入07循環(huán)隊列-入隊3.41、入隊2、算法思路： 判斷隊列Q是否隊滿，當(dāng)隊列滿時，提示 “隊滿”返回0當(dāng)隊列不滿時，先將計數(shù)器加1，再將元素入隊，最后將隊尾指針循環(huán)意義下加1。07654321a1a4a3a2frontrearQ-count +;Q-dataQ-rear=x;Q-rear=(Q-rear+1)%QueueSize;xrear08循環(huán)隊列-入隊3.43、具體算法：int EnQueue(CirQueue *Q,DataType x)/入隊if(

11、QueueFull(Q) puts(隊滿); return 0;Q-count +;/隊列元素個數(shù)加1Q-dataQ-rear=x;/新元素插入隊尾Q-rear=(Q-rear+1)%QueueSize;/循環(huán)意義下將尾指針加1return 1;將隊列Q和入隊元素x作為參數(shù)。將元素x進(jìn)入隊列Q，入隊操作成功時，返回1，否則返回0。三、鏈表的插入09循環(huán)隊列-出隊3.42、算法思路： 判斷隊列Q是否隊空，當(dāng)隊列空時，提示 “隊空”返回0 if(QueueEmpty(Q) puts(“隊空); return 0;1、出隊07654321frontrear三、鏈表的插入10循環(huán)隊列-出隊3.42、算法思路： 判斷隊列Q是否隊空，當(dāng)隊列空時，提示 “隊空”返回0當(dāng)隊不空時，先將隊頂元素的值存入指針x指向的變量，再將計數(shù)器減1、隊頭指針循環(huán)意義下加1。1、出隊07654321a1a4a3a2frontreara5*x=Q-dataQ-front; Q-count-; Q-front=(Q-front+1)%QueueSize;front11循環(huán)隊列-出隊3.4將隊列Q和指針x作為參數(shù)。保存隊頭元素的數(shù)據(jù)，隊頭指針后移。出隊操作成功時，返回1，否則返回0。3、具體