數(shù)據(jù)結(jié)構(gòu)第3章 棧和隊(duì)列

第3章棧和隊(duì)列3.1棧

3.2隊(duì)列

3.3應(yīng)用數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列本章學(xué)習(xí)目標(biāo)理解棧的定義及其基本運(yùn)算掌握順序棧和鏈棧的各種操作實(shí)現(xiàn)理解隊(duì)列的定義及其基本運(yùn)算掌握循環(huán)隊(duì)列和鏈隊(duì)列的各種操作實(shí)現(xiàn)學(xué)會(huì)利用棧和隊(duì)列解決一些問題數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列棧和隊(duì)列是兩種重要的線性結(jié)構(gòu)棧和隊(duì)列是操作受限的線性表出進(jìn)排隊(duì)買票漢諾塔進(jìn)出數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列3.1棧3.1.1棧的基本概念棧：限制僅在表的一端進(jìn)行插入和刪除操作的線性表?xiàng)５牟僮魈匦裕喊聪冗M(jìn)后出(FILO)或后進(jìn)先出(ＬIＦＯ)的原則

棧頂(top)：允許插入和刪除的一端。約定top始終指向棧頂位置。棧底(bottom):不允許插入和刪除的一端。

入棧順序：

e0e1e2…en-2en-1

出棧順序：

en-1en-2…e2e1e0

棧可以對(duì)序列實(shí)現(xiàn)求逆en-1e0e1en-2…進(jìn)棧（Push）出棧（Pop）棧頂top棧底bottom

數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列棧的基本運(yùn)算：InitStack(s)初始化操作，初始化為空棧s。IsEmpty(s)判斷?？蘸瘮?shù)。如果s是空棧，返回“true”，否則返回“false”。IsFull(s)判斷棧滿函數(shù)。主要應(yīng)用在順序存儲(chǔ)結(jié)構(gòu)中，如果s棧滿，返回“true”，否則返回“false”。Push(s，x)壓棧操作。將元素x插入到棧s中，并使x成為新的棧頂元素。Pop(s)出棧函數(shù)。如果棧s非空，那么返回棧頂元素，并刪除該棧頂元素，否則返回空值NULL。GetTop(s)獲取棧頂元素。如果棧s非空，那么返回值為棧頂元素，否則返回空值NULL。EmptyStack(s)清空棧操作。將棧s中的所有元素清除掉，使之成為一個(gè)空棧。DestroyStack()銷毀棧。釋放棧占用的存儲(chǔ)空間。數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列棧有兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

3.1.2棧的順序存儲(chǔ)結(jié)構(gòu)

順序棧：順序存儲(chǔ)結(jié)構(gòu)的棧。順序棧：用一組連續(xù)的存儲(chǔ)單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，一般用一維數(shù)組表示棧頂指針：指示棧頂位置

ABACBA(a)空棧（b）元素A進(jìn)棧（c）元素B、C進(jìn)棧（d）出棧一次（e）出棧二次top-1toptoptoptop-14321043210432104321043210數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列順序棧類型定義：

#defineStackSize100/*順序棧的初始分配空間*/typedefstruct{DataTypedata[StackSize];/*保存棧中元素*/inttop;/*棧指針*/}SeqStack;top為int型，取值范圍為0--StackSize-1。top=-l表示?？?；top=StackSize-1表示棧滿。棧的長度：棧頂指針top+1數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列順序棧的基本運(yùn)算：(1)初始化棧運(yùn)算功能：創(chuàng)建一個(gè)空棧，并將初始化棧頂下標(biāo)top=-1。intInitStack(SeqStack*&sq){sq=(SeqStack*)malloc(sizeof(SeqStack));if(!sq){printf(“memoryisnotenough!”);return0;}sq->top=-1;return1；

}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列(2)進(jìn)棧運(yùn)算功能：棧頂指針加1，將進(jìn)棧元素放進(jìn)棧頂指針?biāo)傅奈恢蒙稀?/p>

intPush(SeqStack*sq,DataTypex){if(sq->top==StackSize-1)/*棧滿*/return0;else{sq->top++;sq->data[sq->top]=x;return1;}}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列(3)出棧運(yùn)算功能：先將棧頂元素取出，然后將棧頂指針減1。intPop(SeqStack*sq,DataType&x){if(sq->top==-1)/*?？?/return0;else{x=sq->data[sq->top];sq->top--;return1;}}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列(4)取棧頂元素運(yùn)算功能：將棧中top處的元素取出賦給變量x。intGetTop(SeqStack*sq,DataType&x){if(sq->top==-1)/*?？?/return0;else{x=sq->data[sq->top];return1;}}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列(5)判斷棧空運(yùn)算算法功能：若棧為空(top==-1)則返回值l，否則返回值0。intStackEmpty(SeqStack*sq){if(sq->top==-1)return1;elsereturn0;}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列3.1.3棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈棧：棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。第一個(gè)結(jié)點(diǎn)為棧頂結(jié)點(diǎn)優(yōu)點(diǎn)：鏈?zhǔn)綏o棧滿問題，空間可擴(kuò)充特點(diǎn)：插入與刪除僅在棧頂處執(zhí)行…∧ls棧頂棧底datanext（棧頂指針）鏈棧的類型定義：typedefstructstnod{DataTypedata;/*存儲(chǔ)結(jié)點(diǎn)數(shù)據(jù)*/structstnode*next;/*指針域*/}LinkStack;數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列棧的基本運(yùn)算算法：

(1)初始化棧運(yùn)算功能：創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的鏈棧，頭結(jié)點(diǎn)指針ls；用ls->next=NULL標(biāo)識(shí)棧為空棧。

voidInitStack(LinkStack*&ls){ls=(LinkStack*)malloc(sizeof(LinkStack));ls->next=NULL;}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列(2)判斷?？者\(yùn)算功能：若棧為空則返回值1，否則返回值0。intStackEmpty(LinkStack*ls){if(ls->next==NULL)return1;elsereturn0;}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列

(3)進(jìn)棧運(yùn)算

voidPush(LinkStack*ls,DataTypex)

{LinkStack*p;p=(LinkStack*)malloc(Sizeof(LinkStack));p->data=x;p->next=ls->next;ls->next=p;}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列(4)出棧運(yùn)算功能:將棧頂結(jié)點(diǎn)的data域值賦給x,然后刪除該棧頂結(jié)點(diǎn)。

intPop(LinkStack*ls，DataType&x){LinkStack*p;if(ls->next==NULL)/*棧空，下溢出*/return0;else{p=ls->next;x=p->data;ls->next=p->next;free(p);return1;}}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列(5)取棧頂元素運(yùn)算算法

功能：將棧頂結(jié)點(diǎn)的data域值賦給x。intGetTop(LinkStack*ls,DataType&x){if(ls->next==NULL)/*?？?，下溢出*/return0;else{x=ls->next->data;return1;}}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列3.2隊(duì)列3.2.1隊(duì)列的基本概念隊(duì)列：限制插入操作只能在一端進(jìn)行，而刪除操作只能在另一端進(jìn)行的線性表操作特性：按先進(jìn)先出(FIFO)或后進(jìn)后出(LILO)的原則。隊(duì)首（front）：能進(jìn)行刪除的一端隊(duì)尾（rear）：能進(jìn)行插入操作的一端。出隊(duì)入隊(duì)隊(duì)首（front）隊(duì)尾（rear）數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列隊(duì)列的基本操作主要：1)InitQueue(Q)：構(gòu)造一個(gè)空隊(duì)列Q。2)QueueEmpty(Q)：判斷隊(duì)列是否為空。3)QueueLength(Q)：求隊(duì)列的長度。4)GetHead(Q)：返回Q的隊(duì)頭元素，不改變隊(duì)列狀態(tài)。5)EnQueue(Q，x)：插入元素x為Q的新的隊(duì)尾元素。6)DeQueue(Q)：刪除Q的隊(duì)頭元素。7)C1earQueue(Q)：清除隊(duì)列Q中的所有元素。數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列隊(duì)列有兩種存儲(chǔ)表示：順序隊(duì)列和鏈隊(duì)列。3.2.2隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)…^front隊(duì)首指針

隊(duì)首

隊(duì)尾rear隊(duì)尾指針鏈隊(duì)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的隊(duì)列；為一個(gè)同時(shí)帶有首指針和尾指針的單鏈表隊(duì)頭在鏈頭，隊(duì)尾在鏈尾。鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無隊(duì)滿問題，但有隊(duì)空問題。數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列鏈隊(duì)的類型定義：

typedefstructQNode{DataTypedata;structQNode*next;}QType;/*鏈隊(duì)中結(jié)點(diǎn)的類型*/typedefstructqptr{QType*front,*rear;}LinkQueue;/*鏈隊(duì)類型*/隊(duì)空的條件:lq->front==lq->next==NULL。數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列鏈隊(duì)基本運(yùn)算算法：(1)初始化隊(duì)列運(yùn)算

功能：置隊(duì)列l(wèi)q的rear和front均為NULL。voidInitQueue(LinkQueue*&lq){lq=(LinkQuene*)malloc(sizeof(LinkQuene));lq->rear=lq->front=NULL;/*初始情況*/}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列(2)入隊(duì)運(yùn)算功能：創(chuàng)建一個(gè)新結(jié)點(diǎn)，將其鏈接到鏈隊(duì)列的末尾，并由rear指向它。VoidEnQueue(LinkQueue*lq,DataTypex){QType*s;/*創(chuàng)建新結(jié)點(diǎn)，插入到鏈隊(duì)的末尾*/s=(QType*)malloc(sizeof(QType));/*創(chuàng)建新結(jié)點(diǎn)，插入到鏈隊(duì)的末尾*/s->data=x;s->next=NULL;if(lq->front==NULL&&lq->rear==NULL)/*空隊(duì)*/lq->rear=lq->front=s;else{lq->rear->next=s;lq->rear=s;}}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列(3)出隊(duì)運(yùn)算功能：將front結(jié)點(diǎn)的data域值賦給x，并刪除該結(jié)點(diǎn)。DataTypeDeQueue(LinkQueue*lq){QType*p;DataTypex;if(lq->front==NULL&&lq->rear==NULL)/*空隊(duì)*/exit(-1);p=lq->front;x=p->data;if(lq->rear==lq->front)/*若原隊(duì)列中只有一個(gè)結(jié)點(diǎn)，刪除后隊(duì)列變空*/lq->rear=lq->front=NULL;elselq->front=p->next;free(p);returnx;}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列(4)取隊(duì)頭元素運(yùn)算功能：將front指向結(jié)點(diǎn)的data域值賦給xDataTypeGetHead(LinkQueue*lq){DataTypex;if(lq->front==NULL&&lq->rear==NULL)/*空隊(duì)*/exit(-1);x=lq->front->data;returnx;}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列(5)判斷隊(duì)空運(yùn)算算法功能：若鏈隊(duì)為空，則返回1；否則返回0intQueueEmpty(LinkQueue*lq){if(lq->front==NULL&&lq->rear==NULL)return1;elsereturn0;}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列3.2.3循環(huán)隊(duì)列順序隊(duì)列：順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列，即用一組地址連續(xù)的存儲(chǔ)單元依次存放隊(duì)頭到隊(duì)尾的元素；順序隊(duì)列：實(shí)質(zhì)是運(yùn)算受限的順序表；543210543210543210543210rearfrontbadcfefrontrearrearfrontfrontrear(a)空隊(duì)（b）a、b入隊(duì)（c）a、b出隊(duì)，c、d入隊(duì)（d）假溢出數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列3.2.3循環(huán)隊(duì)列由于隊(duì)列的隊(duì)頭和隊(duì)尾的位置是變化的，設(shè)立兩個(gè)指針front和rear，指針front隊(duì)頭，rear指示隊(duì)尾下一個(gè)元素；每插入一新元素，rear增1，每刪除一元素，front增1。front=rear=0表示空隊(duì)列，rear=MAXSIZE表示隊(duì)滿。543210543210543210543210rearfrontbadcfefrontrearrearfrontfrontrear(a)空隊(duì)（b）a、b入隊(duì)（c）a、b出隊(duì)，c、d入隊(duì)（d）假溢出數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列543210543210543210543210rearfrontbadcfefrontrearrearfrontfrontrear(a)空隊(duì)（b）a、b入隊(duì)（c）a、b出隊(duì)，c、d入隊(duì)（d）假溢出避免假溢出有兩種辦法：

1)每次一個(gè)元素出隊(duì)，將整個(gè)隊(duì)列向前移動(dòng)一個(gè)位置。

2)采用循環(huán)隊(duì)列：將順序隊(duì)列的數(shù)據(jù)區(qū)data[0～MAXSIZE-1]看成一個(gè)首尾相接的圓環(huán)，頭尾指針的關(guān)系不變數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列循環(huán)隊(duì)列的類型定義：

#defineMAXSIZE100/*最大隊(duì)列長度*/typedefstruct{datatypedata[MAXSIZE];/*存儲(chǔ)隊(duì)列的數(shù)據(jù)空間*/intfront;/*隊(duì)頭指針，若隊(duì)列不空，則指向隊(duì)頭元素*/intrear;/*隊(duì)尾指針，若隊(duì)列不空，則指向隊(duì)尾元素的下一個(gè)位置*/}SeqQueue;

rearfront0123e4e3數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列循環(huán)隊(duì)列特點(diǎn)

rearfront

0123(3)隊(duì)空將頭尾連接成一個(gè)環(huán)，形成循環(huán)隊(duì)列。

rear(1)一般情況front0123e4e3

(2)隊(duì)滿

e3

e40123reare5rear=fronte6rear=frontfront數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列在入隊(duì)時(shí)，rear=（rear+1）%MAXSIZE。存儲(chǔ)隊(duì)列的數(shù)組就變?yōu)槭孜蚕嘟拥囊粋€(gè)環(huán)，即為循環(huán)隊(duì)列。在出隊(duì)時(shí)，front=(front+1)%MAXSIZE，實(shí)現(xiàn)存儲(chǔ)空間的首尾相接。判斷隊(duì)列“空”還是“滿”的處理方法：一是另設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列的“空”和“滿”；二是少用一個(gè)元素的空間，約定以“隊(duì)頭指針在隊(duì)尾指針的下一位置(指環(huán)狀的下一位置)上”作為隊(duì)列“滿”的標(biāo)志。數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列543210543210543210dcfedcgfrontrearrearfrontrearfront(a)正常情況（b）隊(duì)滿（c）隊(duì)空

在循環(huán)隊(duì)列中：若front=rear，則稱為隊(duì)空；若(rear+1)%maxsize=front,則稱為隊(duì)滿。循環(huán)隊(duì)列中能裝入的元素個(gè)數(shù)為maxsize-1，即浪費(fèi)一個(gè)存儲(chǔ)單元，但是這樣可以給操作帶來較大方便。數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列3．循環(huán)隊(duì)列的基本操作(1)構(gòu)造空隊(duì)列intInitQueue(SeqQueue*&q){q=(SeqQueue*)malloc(sizeof(SeqQueue));

/*開辟一個(gè)足夠大的存儲(chǔ)隊(duì)列空間*/if(!q)return0;q->front=q->rear=0;

/*將隊(duì)列頭尾指針置為零*/return1;}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列(2)判斷隊(duì)空intQueueEmpty(SeqQueue*q){return(q->front==q->rear);

/*如果隊(duì)列為空，則返回1，否則返回0*/}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列(3)入隊(duì)

intEnQueue(SeqQueue*q，DataTypex){if((q->rear+1)%MAXSIZE==q->front)

/*判斷隊(duì)列是否滿*/{printf("\n循環(huán)隊(duì)列滿!”);returnFALSE;/*若隊(duì)列滿，則終止*/}q->data[q->rear]=x;/*將元素x入隊(duì)*/q->rear=(q->rear+1)％MAXSIZE;/*修改隊(duì)尾指針*/returnTRUE;}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列(4)出隊(duì)

DataTypeDeQueue(SeqQueue*q){DataTypex;if(q->front==q->rear)/*判斷隊(duì)列是否空*/{printf("\n循環(huán)隊(duì)列空!不能做刪除操作!");returnFALSE;/*若隊(duì)列空，則終止*/}x=q->data[q->front];/*將隊(duì)頭元素出隊(duì)并賦給變量x*/q->front=(q->front+1)％MAXSIZE;/*修改隊(duì)列頭指針*/returnx;/*將被刪除元素返回*/}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列3.3應(yīng)用3.3.1棧的應(yīng)用【例3.1】

設(shè)計(jì)一個(gè)算法，判斷一個(gè)表達(dá)式中符號(hào)“(”與“)”、“[”與“]”、“{”與“}”是否匹配。若匹配，則返回1；否則返回0。設(shè)置一個(gè)棧st；用i掃描表達(dá)式exps，當(dāng)遇到“(”、“[”、“{”時(shí)，將其進(jìn)棧，遇到“}”、“]”、“)”時(shí)，判斷棧頂是否是相匹配的括號(hào)。若不是，則退出掃描過程，返回0；否則直至exps掃描完畢為止；若top==-1，則返回1，否則返回0。數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列#defineMax100intmatch(char*exps){charst[Max];inttop=-1,i=0;intnomatch=0;while(exps[i]!=’\0'&&nomatch==0){switch(exps[i]){case'(':top++;st[top]=exps[i];break;case'[':top++;t[top]=exps[i];break;case'{':top++;t[top]=exps[i];break;

case')':if(exps[top]=='(')top--;elsenomatch=l;break;case']':if(exps[top]==’]’)top--;elsenomatch=1;break;case'}':if(exps[top]==’{‘)top--;elsenomatch=l;break;}i++;}if(nomatch==0&&top==-1)

/*?？涨曳?hào)匹配則返回l*/return1;elsereturn0;/*否則返回0*/}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列【例3.2】數(shù)制轉(zhuǎn)換問題。把一個(gè)非負(fù)十進(jìn)制整數(shù)轉(zhuǎn)換成n（2≤n≤35）進(jìn)制數(shù)，其中各位的系數(shù)如果大于9的依次用大寫英文字母A~Z表示。十進(jìn)制整數(shù)x轉(zhuǎn)換成n進(jìn)制數(shù)的法則是：對(duì)x除n取余，直到整商為０為止，先得到的余數(shù)需要后輸出。例如，十進(jìn)制整數(shù)83轉(zhuǎn)換成8進(jìn)制數(shù)的過程如下圖所示，結(jié)果為(123)8。數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列Typedef****SeqStack；main(){ intx,n; SeqStack*stack; InitStack(stack);

/*初始化棧stack*/ do { printf("x="); scanf("%d",&x); printf("n="); scanf("%d",&n); }while(n<2||n>35||x<0);/*輸入有效數(shù)據(jù),x是十進(jìn)制數(shù),n是進(jìn)制*/while(x)/*除n取余,余數(shù)保存在堆棧中*/

{ Push(stack,x%n); x/=n;} while(!ISEmpty(stack))/*依次出棧，直到?？?/ { Pop(stack,&x); if(x<10) printf("%c",x+'0'); /*輸出位的系數(shù)，范圍’0’~’9’*/ else printf("%c",x+'A'-10); /*輸出位的系數(shù)，范圍’A’~’Z’*/ } printf("\n"); DestroyStack(stack);}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列【例3.3】利用一個(gè)棧逆置一個(gè)帶頭結(jié)點(diǎn)的單鏈表，已知head是帶頭結(jié)點(diǎn)的單鏈表(a1，a2，…，an)(其中n≥0)。說明如下：

typedefintDataType；

typedefstructnode{DataTypedata；

structnode*next；

}LinkList；

LinkList*head;請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，利用一個(gè)順序棧將上述單鏈表實(shí)現(xiàn)逆置利用一個(gè)順序棧將單鏈表(a1，a2，…，an)(其中

n≥0)逆置為(an，an-l，…，a1)數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列

解題思路：

1)建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表head。

2)輸出該單鏈表。

3)建立一個(gè)空棧s(順序棧)。

4)依次將單鏈表的數(shù)據(jù)入棧。

5)依次將單鏈表的數(shù)據(jù)出棧，并逐個(gè)將出棧的數(shù)據(jù)存入單鏈表的數(shù)據(jù)域(自前向后）。

6)再輸出單鏈表。數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列/*利用順序棧逆置單鏈表程序*/#include<stdio.h>#include<malloc.h>#definemaxsize100/*棧的最大元素?cái)?shù)為100*/typedefintDataType;typedefstructnode/*定義單鏈表結(jié)點(diǎn)類型*/{DataTypedata;structnode*next;}LinkList;LinkList*head;/*定義單鏈表的頭指針*/typedefstruct/*定義順序棧*/{DataTyped[maxsize];inttop;}SeqStack;SeqStacks;/*定義順序棧s，s是結(jié)構(gòu)體變量，s是全局變量*/數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列LinkList*CreatList()/*建立單鏈表*/{LinkList

*p,*q;intn=0;p=q=(LinkList

*)malloc(sizeof(LinkList

t));head=p;p->next=NULL;

/*頭結(jié)點(diǎn)的數(shù)據(jù)域不存放任何東西*/p=(LinkList

*)malloc(sizeof(LinkList

));scanf("%d",&p->data);while(p->data!=-1)

/*輸入-l表示鏈表結(jié)束*/

{n=n+1;q->next=p;q=p;p=(LinkList

*)malloc(sizeof(LinkList

));scanf("%d",&p->data);}

q->next=NULL;free(p)return(head);}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列voidprint(LinkList*head)

/*輸出單鏈表*/{LinkList

*p;p=head->next;if(p==NULL)printf("Thisisanempty1ist．\n");else{do{printf("%6d",p->data);p=p->next;}while(p!=NULL);printf("\n");}}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列SeqStackInitStack()

/*構(gòu)造一個(gè)空棧s*/{s.top=-1;returns;}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列intpush(SeqStack*s,DataTypex)/*入棧，此處s是指向順序棧的指針*/{if((*s).top==maxsize-1)/*(*s).top即為s->top，下同*/{printf("棧已滿，不能入棧!\n");return0;}

else{(*s).top++;/*棧頂指針上移*/(*s).d[(*s).top]=x;/*將x存入棧中*/returnx;}}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列DataTypepop(SeqStack*s)/*出棧，s是指向順序棧的指針*/{DataTypey;if((*s).top==-1){printf("棧為空，無法出棧!\n");return0;}else{y=(*s).d[(*s).top];/*棧頂元素出棧，存入y中*/(*s).top--;/*棧頂指針下移*/returny;}}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列intStackEmpty(SeqStacks)/*判棧空，此處s是結(jié)構(gòu)體變量*/{returns.top==-1;}intStackFull(SeqStacks)/*判棧滿，此處s是結(jié)構(gòu)體變量*/{returns.top==maxsize-1;}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列LinkList*backlinklist(LinkList*head)/*利用順序棧s逆置單鏈表head*/{LinkList*p;p=head->next;initstack();while(p){push(&s,p->data);/*單鏈表的數(shù)據(jù)依次入棧s*/p=p->next;}p=head->next;while(!stackempty(s)){p->data=pop(&s);/*數(shù)據(jù)出棧依次存入單鏈表的數(shù)據(jù)域*/p=p->next;}return(head);}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列voidmain(){linklist*head;head=creatlist();print(head);head=backlinklist(head);print(head);}數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列3.3.2隊(duì)列的應(yīng)用【例3．4】打印楊輝三角形是一個(gè)初等數(shù)學(xué)問題。系數(shù)表中的第i行有i+1個(gè)數(shù)，除了第1個(gè)和最后一個(gè)數(shù)為1外，其余的數(shù)則為上一行中位于其左、右的兩數(shù)之和(如圖3．10所示）。數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列分析第

i行元素與第i+1行元素的關(guān)系目的是從前一行的數(shù)據(jù)可以計(jì)算下一行的數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列從第i

行數(shù)據(jù)計(jì)算并存放第i+1行數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列#defineMAXSIZE10/*定義隊(duì)列的最大長度*/#include<stdio.h>typedefintdatatype;typedefstruct{intdata[MAXSIZE];intfront;intrear;}SeqQueue;數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列SeqQueue*InitQueue(){SeqQueue*q;

q=(SeqQueue*)malloc(sizeof(SeqQueue));q->front=q->rear=0;returnq;}

數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列voidEnQueue(SeqQueue*q,datatypex){if((q->rear+1)%MA