第三章棧和隊(duì)列

1、 第三章 棧和隊(duì)列3.1 棧 3.1.1 抽象數(shù)據(jù)類(lèi)型棧的定義 3.1.2 棧的表示和實(shí)現(xiàn)3.2 棧的應(yīng)用舉例3.3 隊(duì)列 3.3.1 抽象數(shù)據(jù)類(lèi)型隊(duì)列的定義 3.3.2 隊(duì)列的表示和實(shí)現(xiàn)棧的定義棧棧是只能在表尾插入和刪除的線(xiàn)性表。入棧出棧anan-1a1棧頂棧底后進(jìn)先出后進(jìn)先出練習(xí)一個(gè)棧的入棧序列是ABCDE，則其輸出序列不可能是（ ）A,EDCBAB,DECBAC,DCEABD,ABCDEC順序棧-存儲(chǔ)結(jié)構(gòu)以順序存儲(chǔ)方式存儲(chǔ)的棧叫做順序棧順序棧。basetopbasetopABCDEbasetopAB順序棧-存儲(chǔ)結(jié)構(gòu)類(lèi)型說(shuō)明：#define MAXSIZE 100typedef struc

2、tSElemType *base;SElemType *top;int stacksize;SqStack棧的運(yùn)算初始化棧：InitStack(S)取棧頂元素：GetTop(S,x)入棧：Push(S,x)出棧：Pop (S)初始化棧：void InitStack(SqStack &S) S.base=(SElemType *)malloc(MAXSIZE*sizeof(SElemType); if(!S.base)exit(-1); S.top=S.base; S.stacksize=MAXSIZE; 取棧頂元素：SElemType GetTop(SqStack S) if(S.to

3、p=S.base)exit(-1); else return *(S.top-1); 入棧：void Push (SqStack &S, SElemType x) if (S.top-S.base=S.stacksize) error(“溢出”); else *S.top+=x; n出棧：void Pop (SqStack &S, SElemType &x) if(S.top=S.base)error(“?？?，不能刪除”);else x= *-S.top; 鏈棧用動(dòng)態(tài)方式來(lái)存儲(chǔ)棧可節(jié)省空間采用鏈表存儲(chǔ)的棧為鏈棧鏈棧由于棧的操作是線(xiàn)性表操作的特例，所以不作詳細(xì)討論。a1a

4、2a3an top3.2 棧的應(yīng)用舉例 3.2.1 數(shù)制轉(zhuǎn)換 3.2.2 括號(hào)匹配的檢驗(yàn) 3.2.3 迷宮求解 3.2.4 表達(dá)式求解 3.2.2 括號(hào)匹配問(wèn)題算法的設(shè)計(jì)思想：（1）若是“左括號(hào)”，則入棧；（2）若是“右括號(hào)”，則有兩種情況： a) 若?？眨瑒t表明“右括號(hào)”多了，匹配失敗； b) 否則，與棧頂元素比較： 若相匹配，則“左括號(hào)”出棧； 否則匹配失敗。（3）當(dāng)表達(dá)式檢驗(yàn)結(jié)束時(shí)： 若?？眨ヅ涑晒?； 否則表明“左括號(hào)”多了，匹配失敗。算法如下：Status matching(string &exp) int state=1; while(ifront=0; Q-rear=0;

5、n判斷隊(duì)列是否為空：BOOL queue_empty(seqqueue Q) if (Q.front=Q.rear) return TRUE; else return FALSE; n判斷隊(duì)列是否為滿(mǎn)：BOOL queue_full(seqqueue Q) if (1+Q.rear) % maxsize=Q.front) return TRUE; else return FALSE; 尾指針的下一個(gè)位置是頭指針?biāo)肝恢脮r(shí)為滿(mǎn)n入隊(duì)void Enqueue(seqqueue * Q,elementtype x)if (full(Q) error(“溢出”); else Q-rear=(1+Q-r

6、ear) % maxsize; Q-dataQ-rear=x； 循環(huán)隊(duì)列的運(yùn)算取隊(duì)頭元素：elementtype queue_front(seqqueue Q,elementtype *x) if (queue_empty(Q) )error(“隊(duì)空”);else *x=Q.data(Q.front+1)% maxsize); n出隊(duì)void Outqueue(seqqueue * Q, elementtype *x)if (empty(*Q) )error(“隊(duì)空，不能出隊(duì)”); else Q-front=(Q-front+1) % maxsize; *x= Q-dataQ-front; 鏈

7、隊(duì)列-存儲(chǔ)結(jié)構(gòu)頭指針始終指向表頭，尾指針始終指向表尾；采用帶頭節(jié)點(diǎn)的鏈表形式。a1a2anfrontrearlinkqueue類(lèi)型說(shuō)明typedef struct node *front,*rear； /僅需要頭尾指針即可 linkqueue鏈隊(duì)列的運(yùn)算初始化隊(duì)列：void init_queue(linkqueue *Q) Q-front=(node *)malloc(sizeof(node); Q-rear=Q-front; Q-front-next=NULL; n取隊(duì)頭元素：void queue_front(linkqueue * Q, elementtype * x); if (empt

8、y(*Q) ) error(“隊(duì)空，不能取元素”); else *x=Q-front-next-data; n判斷隊(duì)為空：BOOL queue_empty(linkqueue Q) return Q.front=Q.rear;鏈隊(duì)列的運(yùn)算入隊(duì)：void Enqueue(linkqueue * Q, elementtype x) node *P=(node *)malloc(sizeof(node); P-data=x; P-next=NULL; Q-rear-next=P; Q-rear=P; n出隊(duì)：void Outqueue(linkqueue * Q, elementtype * x); if (empty(*Q) )error(“隊(duì)空，不能出隊(duì)”); else *x=Q-front-next-data; node * u=Q-fron