隊(duì)列-隊(duì)列的順序表示和實(shí)現(xiàn)

和順序棧相類(lèi)似，在利用順序分配存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)隊(duì)列時(shí)，除了用一維數(shù)組描述隊(duì)列中數(shù)據(jù)元素的存儲(chǔ)區(qū)域之外，尚需設(shè)立兩個(gè)指針front和rear分別指示“隊(duì)頭”和“隊(duì)尾”的位置。

為了在C語(yǔ)言中描述方便，在此我們約定：初始化建空隊(duì)列時(shí)，令front＝rear＝0。每當(dāng)插入新的隊(duì)列尾元素時(shí)，“尾指針增1”；每當(dāng)刪除隊(duì)列頭元素時(shí)，“頭指針增1”。因此，在非空隊(duì)列中，頭指針始終指向隊(duì)列頭元素位置，隊(duì)尾指針始終指向隊(duì)列尾元素的下一個(gè)位置。如圖所示：

從圖中可以看到，隨著入隊(duì)出隊(duì)的進(jìn)行，會(huì)使整個(gè)隊(duì)列整體向后移動(dòng)，這樣就出現(xiàn)了循環(huán)隊(duì)列操作示意圖(d)中的現(xiàn)象(假溢出現(xiàn)象)：隊(duì)尾指針已經(jīng)移到了最后,再有元素入隊(duì)就會(huì)出現(xiàn)溢出，而事實(shí)上此時(shí)隊(duì)中并未真的“滿(mǎn)員”，這種現(xiàn)象為“假溢出”，這是由于“隊(duì)尾入隊(duì)頭出”這種受限制的操作所造成。解決假溢出的方法之一是將隊(duì)列看成頭尾相接的循環(huán)結(jié)構(gòu)，頭尾指針的關(guān)系不變，將其稱(chēng)為“循環(huán)隊(duì)列”，“循環(huán)隊(duì)列”的示意圖如下圖所示：

因?yàn)槭穷^尾相接的循環(huán)結(jié)構(gòu)，

入隊(duì)時(shí)的隊(duì)尾指針加1操作修改為：q.rear=(q.rear+1) % MAXSIZE;

出隊(duì)時(shí)的隊(duì)頭指針加1操作修改為：q.front=(q.front+1) % MAXSIZE;

設(shè)MAXSIZE=10，下圖是循環(huán)隊(duì)列操作示意圖。

如上圖所示的循環(huán)隊(duì)可以看出，(a)中具有a5、a6、a7、a8四個(gè)元素，此時(shí)front=5,rear=9；隨著a9~a14相繼入隊(duì)，隊(duì)中具有了10個(gè)元素--隊(duì)滿(mǎn)，此時(shí)front=5,rear=5,如(b)所示，可見(jiàn)在隊(duì)滿(mǎn)情況下有：front==rear。若在(a)情況下，a5~a8相繼出隊(duì)，此時(shí)隊(duì)空，front=9，rear=9，如(c)所示，即在隊(duì)空情況下也有：front==rear。就是說(shuō)“隊(duì)滿(mǎn)”和“隊(duì)空”的條件是相同的了。這顯然是必須要解決的一個(gè)問(wèn)題。

方法之一是附設(shè)一個(gè)存儲(chǔ)隊(duì)中元素個(gè)數(shù)的變量如num，當(dāng)num==0時(shí)隊(duì)空，當(dāng)num==MAXSIZE時(shí)為隊(duì)滿(mǎn)。

另一種方法是少用一個(gè)元素空間，把圖(d)所示的情況就視為隊(duì)滿(mǎn)，此時(shí)的狀態(tài)是隊(duì)尾指針加1就會(huì)從后面趕上隊(duì)頭指針，這種情況下隊(duì)滿(mǎn)的條件是：(q->rear+1) % MAXSIZE == q->front，也能和空隊(duì)區(qū)別開(kāi)。

隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

typedef?struct?{

QElemtype?*base;//初始化的動(dòng)態(tài)分配存儲(chǔ)空間

int?front;//隊(duì)頭指針

int?rear;//隊(duì)尾指針

}SqQueue;

循環(huán)隊(duì)列的實(shí)現(xiàn)

下面的循環(huán)隊(duì)列及操作按第二種方法實(shí)現(xiàn)。

#include?

#include?

#define?MAXSIZE?10

#define?OK?1

#define?ERROR?0

#define?OVERFLOW?-2

typedef?int?Status;

typedef?int?QElemtype;

typedef?struct?{

QElemtype?*base;//初始化的動(dòng)態(tài)分配存儲(chǔ)空間

int?front;//隊(duì)頭指針

int?rear;//隊(duì)尾指針

}SqQueue;//循環(huán)隊(duì)列

//--------------------循環(huán)隊(duì)列的基本操作的算法描述------------------

Status?InitQueue(SqQueue?*q)

{//構(gòu)造一個(gè)空隊(duì)列Q

q->base=(QElemtype*)malloc(MAXSIZE*sizeof(QElemtype));

if(!q->base)exit(OVERFLOW);//存儲(chǔ)分配失敗

q->front=?q->rear?=0;

return?OK;

}

int?queuelength(SqQueue?q)

{//返回Q的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度

return?(q.rear?-?q.front?+?MAXSIZE)?%?MAXSIZE;

}

Status?EnQueue?(SqQueue?*q,QElemtype?e)

{//插入元素e為Q的新的隊(duì)尾元素

if?((q->rear+1)?%?MAXSIZE?==?q->front)?return?ERROR;//隊(duì)列滿(mǎn)，不進(jìn)行任何操作，不能再入隊(duì)

q->base[q->rear]=e;

//入隊(duì)的操作

q->rear=(q->rear+1)?%?MAXSIZE;

return?OK;

}

Status?DeQueue?(SqQueue?*q,QElemtype?*e)

{//若隊(duì)列不空，則刪除Q的對(duì)頭元素，用e返回其值，并返回OK；否則返回ERROR

if?(q->front==q->rear)?return?ERROR;//隊(duì)列滿(mǎn)

*e=q->base[q->front];?//指針的下標(biāo)運(yùn)算

q->front=(q->front+1)?%?MAXSIZE;

return?OK;

}

void?display_queue(SqQueue?*q){

if(q->front==q->rear){

printf("queue?is?empty!!\n");

}else?{

//遍歷該循環(huán)隊(duì)列

int?front?=?q->front;

int?rear?=?q->rear;

while(front!=rear){

printf("%d\n",q->base[front]);

++front;

}

}

}

int?main(){

SqQueue?q;

InitQueue(&q);

int?i;

for(i=0;i<11;i++){

if(EnQueue(&q,i)==ERROR){

printf("循環(huán)隊(duì)列已滿(mǎn)，該隊(duì)列長(zhǎng)度為9?\n");

}

}

printf("the?length?of?queue?is?%d?\n",queuelength(q));?//the?length?of?queue?is?9

int?e1,e2,e3,e4,e5;

DeQueue(&q,&e1);

DeQueue(&q,&e2);

DeQueue(&q,&e3);

DeQueue(&q,&e4);

DeQueue(&q,&e5);

printf("%d--%d--%d--%d--%d?\n",e1,e2,e3,e4,e5);

printf("the?length?of?queue?is?%d?\n",queuelength(q));

printf("循環(huán)隊(duì)列的遍歷\n");

display_queue(&q);

int?e6;

DeQueue(&q,&e6);

printf("循環(huán)隊(duì)列的遍歷\n");

display_queue(&q);

system("pause");

return?0;

}

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

循環(huán)隊(duì)列已滿(mǎn)，該隊(duì)列長(zhǎng)度為9

循環(huán)隊(duì)列已滿(mǎn)，該隊(duì)列長(zhǎng)度為9

the?length?of?queue?is?9

0--1--2--3--4

the?length?of?queue?is?4

循環(huán)隊(duì)列的遍歷

5

6

7

8

循環(huán)隊(duì)列的遍歷

6

7

8

請(qǐng)按任意鍵繼續(xù).?.?.

注：數(shù)學(xué)中的余數(shù)其實(shí)就是取模運(yùn)算

如，m模n (c語(yǔ)言表示 m%n )

x mod y = x % y

數(shù)學(xué)中的余數(shù)概念和我們的計(jì)算機(jī)中的余數(shù)概念一致，但實(shí)現(xiàn)卻不一致。

========END========

總結(jié)

以上是生活随笔為你收集整理的队列的顺序数组c语言代码,队列-队列的顺序表示和实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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