棧與隊(duì)列 編程初級(jí)教程

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

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

3、pe x)if( top stacksize-1) top+;datatop=x;else cout -1) result= datatop;top-; else cout -1) result= datatop;else coutdata=x;p-next=top;top=p;9（2）出棧操作若棧不空，則刪除棧頂元素，用result返回其值。void LinkStack:Pop(ElemType &result);SNode *p;if(top!=NULL)result = top-data;p=top;top=top-next;delete p;10舉例 : 后綴表達(dá)式求值假定表達(dá)式是由加

4、減乘除和數(shù)字構(gòu)成。最簡(jiǎn)單的表達(dá)式為下列形式： (操作數(shù)S1)(運(yùn)算符OP)(操作數(shù)S2) 三種不同的表示方法：前綴表示法 OPS1S2 例如6+3寫成+63中綴表示法 OPS1S2 例如6+3寫成63+后綴表示法 S1S2OP 例如6+3寫成63+11同時(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)去掉)12中綴

5、式雖然容易理解，但在求值的時(shí)候利用前綴式或后綴式更為簡(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ù)。13例如后綴式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é)果?！纠?-3】假定表達(dá)式是由不超過(guò)四個(gè)實(shí)數(shù)進(jìn)行四則運(yùn)算構(gòu)成的算式，要編寫一個(gè)程序來(lái)求

6、解該算式的結(jié)果。 14中綴表達(dá)式變成等價(jià)的后綴表達(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á)式。15步驟棧中元素 輸出結(jié)果 說(shuō)明1(（進(jìn)棧2(1輸出13( +1+進(jìn)棧4( +1 2輸出2

7、51 2 +退棧輸出，退棧到（止6*1 2 +*進(jìn)棧7* (1 2 +（進(jìn)棧8* ( (1 2 +（進(jìn)棧9* ( (1 2 + 8輸出810* ( ( -1 2 + 8 - 進(jìn)棧將中綴表達(dá)式(1+2)*(8-2)/(7-4)變成等價(jià)的后綴表達(dá)式?，F(xiàn)在用棧來(lái)實(shí)現(xiàn)該運(yùn)算，棧的變化及輸出結(jié)果如下：1611* ( ( -1 2 + 8 2輸出212* (1 2 + 8 2 -退棧輸出，退棧到（止13* ( /1 2 + 8 2 -/ 進(jìn)棧14* ( / (1 2 + 8 2 -（ 進(jìn)棧15* ( / (1 2 + 8 2 - 7輸出716* ( / ( -1 2 + 8 2 - 7- 進(jìn)棧17* (

8、/ ( -1 2 + 8 2 - 7 4輸出418* ( /1 2 + 8 2 - 7 4 -退棧輸出，退棧到（止19*1 2 + 8 2 - 7 4 - /退棧輸出，退棧到（止201 2 + 8 2 - 7 4 - / * *退棧并輸出17隊(duì)列定義 隊(duì)列是只能在表的一端進(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。 abcfrontrear入隊(duì)出隊(duì)隊(duì)

9、列示意圖18循環(huán)隊(duì)列隊(duì)列順序存儲(chǔ) 順序存儲(chǔ)的隊(duì)列中，每次出隊(duì)列的元素必定是隊(duì)頭元素，因此如果采取與普通順序表同樣的操作方式，則每次出隊(duì)操作必然將整個(gè)隊(duì)列向前移動(dòng)，這使得效率大大降低。因此在順序存儲(chǔ)的隊(duì)列中，出隊(duì)和入隊(duì)操作都不移動(dòng)元素而是移動(dòng)指針。 19為方便起見(jiàn)，這里規(guī)定隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針rear指向隊(duì)尾元素所在位置。這樣，入隊(duì)和出隊(duì)操作的執(zhí)行步驟都是首先執(zhí)行指針移動(dòng)，再進(jìn)行元素讀寫。對(duì)空隊(duì)列而言，可假定front和rear的值為-1 20假溢出ABCfrontrearfrontrear (a) ABC入隊(duì) (b) AB出隊(duì), DE入隊(duì) (c)隊(duì)列假溢出隊(duì)列假

10、溢出示意圖CDEfrontrear 隨著元素不斷入隊(duì)列、出隊(duì)列，rear和front指針會(huì)不斷向后移動(dòng)（如圖(b)所示），最終會(huì)指向數(shù)組的最大下標(biāo)位置（如圖(c)所示）。由于rear和front指針只能單方向移動(dòng)，這時(shí)元素?zé)o法入隊(duì)列，但是隊(duì)列中仍有大量空閑位置。這種情況稱為假溢出。 21循環(huán)隊(duì)列解決隊(duì)列假溢出的辦法是將存放隊(duì)列元素的數(shù)組首尾相接，形成循環(huán)隊(duì)列。循環(huán)隊(duì)列的基本操作方式為：入隊(duì)列時(shí)先執(zhí)行rear=(rear+1)%M，再將新元素在rear指示位置加入；出隊(duì)列時(shí)先執(zhí)行front=(front+1)%M，再將下標(biāo)為front的元素取出。 22為了將隊(duì)空和對(duì)滿的條件加以區(qū)分，一般不使用f

11、ront指針?biāo)傅奈恢?。?duì)空條件為front=rear隊(duì)滿條件為(rear+1)%M=front30124567frontrearABCD30124567frontrear30124567frontrearABCDFGE (a)循環(huán)隊(duì)列空 (b)非空循環(huán)隊(duì)列 (c)循環(huán)隊(duì)列滿 循環(huán)隊(duì)列示意圖 23循環(huán)隊(duì)列描述如下：#define MAXSIZE 100/隊(duì)列最大可分配空間數(shù)量class SqQueuepublic: ElemType dataMAXSIZE;/ 存放元素的數(shù)組 int front; / 隊(duì)頭指針 int rear; / 隊(duì)尾指針 void EnQueue(ElemType x)

12、; /入隊(duì)操作 void DeQueue(ElemType &e); /出隊(duì)操作 void GetHead(ElemType &e); /取隊(duì)頭元素;front和rear指針取值均為所指數(shù)組單元的下標(biāo)。由于隊(duì)頭指針?biāo)竼卧偸强盏?，length比實(shí)際能存儲(chǔ)的元素多一。 24（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; 常用算法 25（2）出隊(duì)操作 若隊(duì)列不空，則刪

13、除隊(duì)頭元素并用e取回該元素的值。void SqQueue:DeQueue(ElemType &e) if(rear=front) cout隊(duì)列已空;else front = (front +1)% MAXSIZE;e= datafront;26（3）取隊(duì)頭元素 若隊(duì)列不空，則用e取回隊(duì)頭元素的值。void SqQueue:GetHead(ElemType &e)if(rear=front) coutnext=NULL; rear = front;/尾指針也指向頭結(jié)點(diǎn) int Length(); /求隊(duì)列長(zhǎng)度void EnQueue(ElemType x); /入隊(duì)操作void DeQueue

14、(ElemType &e); /出隊(duì)操作void GetHead(ElemType &e); /求隊(duì)頭元素;30（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;31（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ì)尾指針32（3）出隊(duì)列操作若隊(duì)列不空，則刪除隊(duì)頭元素，用e返回其值。void LinkQueue:DeQueue (ElemType &e) QNode *p;if( front= rear) coutnext;e=p-data;front-next=p-next;if(rear=p) rear=front; delete p;刪除最后一個(gè)元素時(shí)，需要修改尾指針，使其指向頭結(jié)點(diǎn)33（4）取隊(duì)頭元素若隊(duì)列不空，則用e返回隊(duì)頭元素；void L