1、棧與隊(duì)列,西安交通大學(xué)計(jì)教中心 ,棧的定義,棧是限制在表的一端進(jìn)行插入和刪除操作的線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂，另一端稱為棧底。 如果多個(gè)元素依次進(jìn)棧，則后進(jìn)棧的元素必然先出棧，所以堆棧又稱為后進(jìn)先出（LIFO）表。堆棧設(shè)有一個(gè)棧頂指針標(biāo)志棧頂位置。,棧示意圖,堆棧的主要操作有：, 創(chuàng)建空棧。 進(jìn)棧(push)操作: 在棧頂插入元素。 出棧(pop)操作: 在棧頂刪除元素。 讀棧頂元素: 只是讀出棧頂元素，并不改變棧內(nèi)元素。,順序棧,#define STACKSIZE 100/堆棧最大可分配空間數(shù)量 class SqStack public: ElemType dataSTAC

2、KSIZE; /存儲(chǔ)元素的數(shù)組 int top; /棧頂指針，存儲(chǔ)棧頂元素的下標(biāo) SqStack() top=-1; /構(gòu)造函數(shù) void Push(ElemType x);/入棧操作 void Pop(ElemType 一般將數(shù)組的0下標(biāo)單元作為棧底，將棧頂元素的下標(biāo)存儲(chǔ)在棧頂指針top中，它隨著元素進(jìn)棧出棧而變化。top為-1表示空棧，top等于stacksize-1則表示棧滿。 哈羅小說(shuō)網(wǎng),（1）進(jìn)棧操作 若棧不滿，則在棧頂插入元素x作為新的棧頂。 void SqStack:Push(ElemType x) if( top stacksize-1) top+; datatop=x; el

3、se cout”棧滿”; ,（2）出棧操作 若棧不空，則刪除棧頂元素，用result返回其值。 void SqStack:Pop(ElemType ,（3）取棧頂元素 若棧不空，則用result返回棧頂元素。 void SqStack:GetTop(ElemType ,鏈?zhǔn)綏?棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)質(zhì)上就是一個(gè)無(wú)頭結(jié)點(diǎn)、只能在頭部插入、刪除元素的單鏈表。 typedef struct node ElemType data; /數(shù)據(jù)域 struct node *next; / 指針域 SNode; class LinkStack public: SNode* top; /棧頂指針 LinkStack

4、() top=NULL; /構(gòu)造函數(shù) void Push(ElemType x);/入棧操作 void Pop(ElemType ,（1）進(jìn)棧操作 若棧不滿，則在棧頂插入元素x作為新的棧頂。 void LinkStack:Push(ElemType x) SNode *p=new SNode; if(p!=NULL) p-data=x; p-next=top; top=p; ,（2）出棧操作 若棧不空，則刪除棧頂元素，用result返回其值。 void LinkStack:Pop(ElemType ,舉例 : 后綴表達(dá)式求值,假定表達(dá)式是由加減乘除和數(shù)字構(gòu)成。最簡(jiǎn)單的表達(dá)式為下列形式： (操作

5、數(shù)S1)(運(yùn)算符OP)(操作數(shù)S2) 三種不同的表示方法： 前綴表示法 OPS1S2 例如6+3寫成+63 中綴表示法 OPS1S2 例如6+3寫成63+ 后綴表示法 S1S2OP 例如6+3寫成63+,同時(shí)，任何表達(dá)式都可分解為下列形式： (子表達(dá)式E1)(運(yùn)算符OP)(子表達(dá)式E2) 它的后綴表示法應(yīng)寫成： (E1的后綴表示)(E2的后綴表示)OP 只要不斷對(duì)子表達(dá)式進(jìn)一步分解，總能將子表達(dá)式分解為最簡(jiǎn)單形式，因此任何四則運(yùn)算表達(dá)式都可寫成前綴式或后綴式。 例如： 2*(6+3) 2(6+3)* 263+*。 (注意：轉(zhuǎn)化為后綴式后括號(hào)去掉),中綴式雖然容易理解，但在求值的時(shí)候利用前綴式或

6、后綴式更為簡(jiǎn)單。用后綴式求值的算法為： 首先設(shè)立一個(gè)堆棧，依此讀取后綴式中的字符，若字符是數(shù)字，則進(jìn)棧并繼續(xù)讀取，若字符是運(yùn)算符（記為OP），則連續(xù)出棧兩次得到數(shù)字S1和S2，計(jì)算表達(dá)式S1OPS2并將結(jié)果入棧，繼續(xù)讀取后綴式。當(dāng)讀到結(jié)束符時(shí)停止讀操作，這時(shí)堆棧中只應(yīng)該有一個(gè)數(shù)據(jù)，即結(jié)果數(shù)據(jù)。,例如后綴式263+*的計(jì)算過(guò)程為2、6、3依次入棧，讀+號(hào)則令3和6依次出棧，計(jì)算6+3后將結(jié)果9入棧，讀*號(hào)則令9和2依次出棧，計(jì)算2*9后將結(jié)果18入棧。這時(shí)18就是最終結(jié)果。 【例2-3】假定表達(dá)式是由不超過(guò)四個(gè)實(shí)數(shù)進(jìn)行四則運(yùn)算構(gòu)成的算式，要編寫一個(gè)程序來(lái)求解該算式的結(jié)果。,中綴表達(dá)式變成等價(jià)的后

7、綴表達(dá)式,將中綴表達(dá)式變成等價(jià)的后綴表達(dá)式，表達(dá)式中操作數(shù)次序不變，運(yùn)算符次序發(fā)生變化，同時(shí)去掉了圓括號(hào)。轉(zhuǎn)換規(guī)則是：設(shè)立一個(gè)棧，存放運(yùn)算符，首先棧為空，編譯程序從左到右掃描中綴表達(dá)式，若遇到操作數(shù)，直接輸出，并輸出一個(gè)空格作為兩個(gè)操作數(shù)的分隔符；若遇到運(yùn)算符，則必須與棧頂比較，運(yùn)算符級(jí)別比棧頂級(jí)別高則進(jìn)棧，否則退出棧頂元素并輸出，然后輸出一個(gè)空格作分隔符；若遇到左括號(hào)，進(jìn)棧；若遇到右括號(hào)，則一直退棧輸出，直到退到左括號(hào)止。當(dāng)棧變成空時(shí)，輸出的結(jié)果即為后綴表達(dá)式。,將中綴表達(dá)式(1+2)*(8-2)/(7-4)變成等價(jià)的后綴表達(dá)式?，F(xiàn)在用棧來(lái)實(shí)現(xiàn)該運(yùn)算，棧的變化及輸出結(jié)果如下：,隊(duì)列定義,隊(duì)列

8、是只能在表的一端進(jìn)行插入、在另一端進(jìn)行刪除操作的線性表。允許刪除元素的一端稱為隊(duì)頭，允許插入元素的一端稱為隊(duì)尾。 顯然不論元素按何種順序進(jìn)入隊(duì)列，也必然按這種順序出隊(duì)列，所以隊(duì)列又稱為先進(jìn)先出（FIFO）表。隊(duì)列有兩個(gè)活動(dòng)端，所以設(shè)置了對(duì)頭和隊(duì)尾兩個(gè)位置指針。一般隊(duì)頭指針記作front，隊(duì)尾指針記作rear。,循環(huán)隊(duì)列隊(duì)列順序存儲(chǔ),順序存儲(chǔ)的隊(duì)列中，每次出隊(duì)列的元素必定是隊(duì)頭元素，因此如果采取與普通順序表同樣的操作方式，則每次出隊(duì)操作必然將整個(gè)隊(duì)列向前移動(dòng)，這使得效率大大降低。 因此在順序存儲(chǔ)的隊(duì)列中，出隊(duì)和入隊(duì)操作都不移動(dòng)元素而是移動(dòng)指針。,為方便起見，這里規(guī)定隊(duì)頭指針front指向隊(duì)頭元素

9、的前一個(gè)位置，隊(duì)尾指針rear指向隊(duì)尾元素所在位置。這樣，入隊(duì)和出隊(duì)操作的執(zhí)行步驟都是首先執(zhí)行指針移動(dòng)，再進(jìn)行元素讀寫。 對(duì)空隊(duì)列而言，可假定front和rear的值為-1,假溢出,隨著元素不斷入隊(duì)列、出隊(duì)列，rear和front指針會(huì)不斷向后移動(dòng)（如圖(b)所示），最終會(huì)指向數(shù)組的最大下標(biāo)位置（如圖(c)所示）。由于rear和front指針只能單方向移動(dòng)，這時(shí)元素?zé)o法入隊(duì)列，但是隊(duì)列中仍有大量空閑位置。這種情況稱為假溢出。,循環(huán)隊(duì)列,解決隊(duì)列假溢出的辦法是將存放隊(duì)列元素的數(shù)組首尾相接，形成循環(huán)隊(duì)列。循環(huán)隊(duì)列的基本操作方式為： 入隊(duì)列時(shí)先執(zhí)行rear=(rear+1)%M，再將新元素在rear

10、指示位置加入； 出隊(duì)列時(shí)先執(zhí)行front=(front+1)%M，再將下標(biāo)為front的元素取出。,為了將隊(duì)空和對(duì)滿的條件加以區(qū)分，一般不使用front指針?biāo)傅奈恢谩?隊(duì)空條件為front=rear 隊(duì)滿條件為(rear+1)%M=front,(a)循環(huán)隊(duì)列空 (b)非空循環(huán)隊(duì)列 (c)循環(huán)隊(duì)列滿 循環(huán)隊(duì)列示意圖,循環(huán)隊(duì)列描述如下：,#define MAXSIZE 100/隊(duì)列最大可分配空間數(shù)量 class SqQueue public: ElemType dataMAXSIZE;/ 存放元素的數(shù)組 int front; / 隊(duì)頭指針 int rear; / 隊(duì)尾指針 void EnQueu

11、e(ElemType x); /入隊(duì)操作 void DeQueue(ElemType front和rear指針取值均為所指數(shù)組單元的下標(biāo)。 由于隊(duì)頭指針?biāo)竼卧偸强盏?，length比實(shí)際能存儲(chǔ)的元素多一。,（1）入隊(duì)操作 若隊(duì)列不滿，則在隊(duì)尾插入元素x作為新的隊(duì)尾。 void SqQueue:EnQueue(ElemType x) if(rear+1)% MAXSIZE= front) cout隊(duì)列已滿; else rear = (rear+1)%MAXSIZE; datarear=x; ,常用算法,（2）出隊(duì)操作 若隊(duì)列不空，則刪除隊(duì)頭元素并用e取回該元素的值。 void SqQueue:

12、DeQueue(ElemType ,（3）取隊(duì)頭元素 若隊(duì)列不空，則用e取回隊(duì)頭元素的值。 void SqQueue:GetHead(ElemType ,鏈隊(duì)列隊(duì)列鏈?zhǔn)酱鎯?chǔ),鏈隊(duì)列實(shí)質(zhì)上就是只能在頭部刪除元素、只能在尾部插入元素的單鏈表。 隊(duì)頭指針front就是單鏈表的頭指針，隊(duì)尾指針rear則是指向單鏈表最后一個(gè)結(jié)點(diǎn)的指針。,鏈隊(duì)列的結(jié)點(diǎn)可定義如下： struct QNode ElemType data; struct QNode *next; ; 鏈隊(duì)列有兩個(gè)指針，因此可采用下面定義: class LinkQueue public: QNode *front;/ 隊(duì)頭指針 QNode *r

13、ear; / 隊(duì)尾指針 ( 下頁(yè)繼續(xù) ),( 接上頁(yè) ),LinkQueue() front = new QNode;/建立頭結(jié)點(diǎn) front-next=NULL; rear = front;/尾指針也指向頭結(jié)點(diǎn) int Length(); /求隊(duì)列長(zhǎng)度 void EnQueue(ElemType x); /入隊(duì)操作 void DeQueue (ElemType ,（1）求隊(duì)列的長(zhǎng)度 返回隊(duì)列的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度。 int LinkQueue:Length() QNode * p=front; int len=0; while(p!=rear) len+; p= p-next; return len; ,（2）入隊(duì)列操作 插入元素x為隊(duì)列新的隊(duì)尾元素。 void LinkQueue:EnQueue(ElemType x) QNode *s=new QNode;/建立新結(jié)點(diǎn)s s-data = x; s-next =NULL; rear -next = s;/在隊(duì)尾插入結(jié)點(diǎn)s rear = s;/修改隊(duì)尾指針 ,（3）出隊(duì)列操作 若隊(duì)列不空，則刪除隊(duì)頭元素，用e返回其值。 void LinkQueue:DeQueue (ElemType 刪除最后一個(gè)元素時(shí)，需要修改尾指針，使其指向頭