題目

設(shè)計(jì)一個(gè)循環(huán)隊(duì)列，用front和rear分別作為隊(duì)頭和隊(duì)尾指針，另外用一個(gè)標(biāo)志tag表示隊(duì)列是空還是不空，約定當(dāng)tag為0時(shí)隊(duì)空，當(dāng)tag為1時(shí)隊(duì)不空，這樣就可以用front==rear作為隊(duì)滿(mǎn)的條件要求，設(shè)計(jì)隊(duì)列的結(jié)構(gòu)和相關(guān)基本運(yùn)算算法（隊(duì)列元素是int型）。

分析

結(jié)構(gòu)體定義：

/* 順序隊(duì)類(lèi)型定義 */ typedef struct {int data[maxSize];int front;// 隊(duì)首指針int rear;// 隊(duì)尾指針int tag;// 表示隊(duì)列是空還是不空，約定tag=0時(shí)隊(duì)空，tag=1時(shí)隊(duì)不空 } SqQueue;

要素：

• qu.tag=0;qu.front=qu.rear=0;// 初始時(shí)
• qu.front==qu.rear&&qu.tag==0;// 隊(duì)空條件
• qu.front==qu.rear&&qu.tag==1;// 隊(duì)滿(mǎn)條件

對(duì)于tag值的設(shè)置，初始時(shí)一定為0,插入成功后應(yīng)設(shè)置為1,刪除成功后應(yīng)設(shè)置為0.因?yàn)橹挥性诓迦氩僮骱?#xff0c;隊(duì)列才有可能滿(mǎn)，在刪除操作后，隊(duì)列才有可能空。tag?的值再配合上front==rear這一句的判斷就能正確區(qū)分隊(duì)滿(mǎn)與隊(duì)空。

代碼

核心代碼：

/* 初始化隊(duì)列 */ void initQueue(SqQueue &qu) {qu.front=0;// 隊(duì)首和隊(duì)尾指針重合并指向0qu.rear=0;qu.tag=0;// 標(biāo)志位表示隊(duì)空 }/* 判斷隊(duì)空 */ int isQueueEmpty(SqQueue qu) {if(qu.tag==0&&qu.front==qu.rear) { // tag=0表示隊(duì)空return 1;// 1表示判斷結(jié)果為空} else {return 0;// 0表示判斷結(jié)果為非空} }/* 判斷隊(duì)滿(mǎn) */ int isQueueFull(SqQueue qu) {if(qu.tag==1&&qu.front==qu.rear) { // 由于有標(biāo)志位tag，故可以用此等式判斷是否隊(duì)滿(mǎn)return 1;} else {return 0;} }/* 入隊(duì) */ int enQueue(SqQueue &qu,int x) {if(isQueueFull(qu)==1) {return 0;} else {qu.rear=(qu.rear+1)%maxSize;// 若隊(duì)未滿(mǎn)，則移動(dòng)指針qu.data[qu.rear]=x;// 再存入元素qu.tag=1;// 只要進(jìn)隊(duì)就將tag設(shè)置為1，因?yàn)橹挥羞M(jìn)隊(duì)才可能會(huì)發(fā)生隊(duì)滿(mǎn)return 1;} }/* 出隊(duì) */ int deQueue(SqQueue &qu,int &x) {if(isQueueEmpty(qu)==1) { // 若隊(duì)空，則不能出隊(duì)return 0;} else {qu.front=(qu.front+1)%maxSize;// 若隊(duì)不空，則移動(dòng)指針x=qu.data[qu.front];// 再取出元素qu.tag=0;// 只要有元素出隊(duì)，就把tag置為0，因?yàn)橹挥谐鲫?duì)才可能隊(duì)空return 1;} }

完整代碼：

#include<stdio.h>#define maxSize 20/* 順序隊(duì)類(lèi)型定義 */ typedef struct {int data[maxSize];int front;// 隊(duì)首指針int rear;// 隊(duì)尾指針int tag;// 表示隊(duì)列是空還是不空，約定tag=0時(shí)隊(duì)空，tag=1時(shí)隊(duì)不空 } SqQueue;/* 初始化隊(duì)列 */ void initQueue(SqQueue &qu) {qu.front=0;// 隊(duì)首和隊(duì)尾指針重合并指向0qu.rear=0;qu.tag=0;// 標(biāo)志位表示隊(duì)空 }/* 判斷隊(duì)空 */ int isQueueEmpty(SqQueue qu) {if(qu.tag==0&&qu.front==qu.rear) { // tag=0表示隊(duì)空return 1;// 1表示判斷結(jié)果為空} else {return 0;// 0表示判斷結(jié)果為非空} }/* 判斷隊(duì)滿(mǎn) */ int isQueueFull(SqQueue qu) {if(qu.tag==1&&qu.front==qu.rear) { // 由于有標(biāo)志位tag，故可以用此等式判斷是否隊(duì)滿(mǎn)return 1;} else {return 0;} }/* 入隊(duì) */ int enQueue(SqQueue &qu,int x) {if(isQueueFull(qu)==1) {return 0;} else {qu.rear=(qu.rear+1)%maxSize;// 若隊(duì)未滿(mǎn)，則移動(dòng)指針qu.data[qu.rear]=x;// 再存入元素qu.tag=1;// 只要進(jìn)隊(duì)就將tag設(shè)置為1，因?yàn)橹挥羞M(jìn)隊(duì)才可能會(huì)發(fā)生隊(duì)滿(mǎn)return 1;} }/* 出隊(duì) */ int deQueue(SqQueue &qu,int &x) {if(isQueueEmpty(qu)==1) { // 若隊(duì)空，則不能出隊(duì)return 0;} else {qu.front=(qu.front+1)%maxSize;// 若隊(duì)不空，則移動(dòng)指針x=qu.data[qu.front];// 再取出元素qu.tag=0;// 只要有元素出隊(duì)，就把tag置為0，因?yàn)橹挥谐鲫?duì)才可能隊(duì)空return 1;} }/* 打印隊(duì)列 */ void printQueue(SqQueue qu) {printf("\n");while(qu.rear!=qu.front) {qu.front=(qu.front+1)%maxSize;printf("%d\t",qu.data[qu.front]);}printf("\n"); }int main() {SqQueue qu;int nums[]= {1,2,3,4,5,6};int n=6;initQueue(qu);for(int i=0; i<n; i++) {int m=enQueue(qu,nums[i]);// 將數(shù)組中的元素入隊(duì)}printQueue(qu);// 打印隊(duì)列int x;deQueue(qu,x);// 將元素1出隊(duì)printQueue(qu);// 打印隊(duì)列return 0; }

運(yùn)行結(jié)果：

總結(jié)

以上是生活随笔為你收集整理的考研数据结构之队列（3.3）——练习题之设计一个循环队列，用front和rear分别作为队头和队尾指针，另外用一个标志tag表示队列是空还是不空来设计队列的结构和相关基本运算算法（C表示）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。