棧與隊列 編程初級教程

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

2、E; /存儲元素的數(shù)組 int top; /棧頂指針，存儲棧頂元素的下標 SqStack() top=-1; /構(gòu)造函數(shù) void Push(ElemType x);/入棧操作 void Pop(ElemType &result);/出棧操作 void GetTop(ElemType &result);/取棧頂元素;一般將數(shù)組的0下標單元作為棧底，將棧頂元素的下標存儲在棧頂指針top中，它隨著元素進棧出棧而變化。top為-1表示空棧，top等于stacksize-1則表示棧滿。 哈羅小說網(wǎng)4（1）進棧操作若棧不滿，則在棧頂插入元素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舉例 : 后綴表達式求值假定表達式是由加

4、減乘除和數(shù)字構(gòu)成。最簡單的表達式為下列形式： (操作數(shù)S1)(運算符OP)(操作數(shù)S2) 三種不同的表示方法：前綴表示法 OPS1S2 例如6+3寫成+63中綴表示法 OPS1S2 例如6+3寫成63+后綴表示法 S1S2OP 例如6+3寫成63+11同時，任何表達式都可分解為下列形式： (子表達式E1)(運算符OP)(子表達式E2)它的后綴表示法應寫成：(E1的后綴表示)(E2的后綴表示)OP只要不斷對子表達式進一步分解，總能將子表達式分解為最簡單形式，因此任何四則運算表達式都可寫成前綴式或后綴式。例如： 2*(6+3) 2(6+3)* 263+*。 (注意：轉(zhuǎn)化為后綴式后括號去掉)12中綴

5、式雖然容易理解，但在求值的時候利用前綴式或后綴式更為簡單。用后綴式求值的算法為：首先設立一個堆棧，依此讀取后綴式中的字符，若字符是數(shù)字，則進棧并繼續(xù)讀取，若字符是運算符（記為OP），則連續(xù)出棧兩次得到數(shù)字S1和S2，計算表達式S1OPS2并將結(jié)果入棧，繼續(xù)讀取后綴式。當讀到結(jié)束符時停止讀操作，這時堆棧中只應該有一個數(shù)據(jù)，即結(jié)果數(shù)據(jù)。13例如后綴式263+*的計算過程為2、6、3依次入棧，讀+號則令3和6依次出棧，計算6+3后將結(jié)果9入棧，讀*號則令9和2依次出棧，計算2*9后將結(jié)果18入棧。這時18就是最終結(jié)果。【例2-3】假定表達式是由不超過四個實數(shù)進行四則運算構(gòu)成的算式，要編寫一個程序來求

6、解該算式的結(jié)果。 14中綴表達式變成等價的后綴表達式將中綴表達式變成等價的后綴表達式，表達式中操作數(shù)次序不變，運算符次序發(fā)生變化，同時去掉了圓括號。轉(zhuǎn)換規(guī)則是：設立一個棧，存放運算符，首先棧為空，編譯程序從左到右掃描中綴表達式，若遇到操作數(shù)，直接輸出，并輸出一個空格作為兩個操作數(shù)的分隔符；若遇到運算符，則必須與棧頂比較，運算符級別比棧頂級別高則進棧，否則退出棧頂元素并輸出，然后輸出一個空格作分隔符；若遇到左括號，進棧；若遇到右括號，則一直退棧輸出，直到退到左括號止。當棧變成空時，輸出的結(jié)果即為后綴表達式。15步驟棧中元素 輸出結(jié)果 說明1(（進棧2(1輸出13( +1+進棧4( +1 2輸出2

7、51 2 +退棧輸出，退棧到（止6*1 2 +*進棧7* (1 2 +（進棧8* ( (1 2 +（進棧9* ( (1 2 + 8輸出810* ( ( -1 2 + 8 - 進棧將中綴表達式(1+2)*(8-2)/(7-4)變成等價的后綴表達式?，F(xiàn)在用棧來實現(xiàn)該運算，棧的變化及輸出結(jié)果如下：1611* ( ( -1 2 + 8 2輸出212* (1 2 + 8 2 -退棧輸出，退棧到（止13* ( /1 2 + 8 2 -/ 進棧14* ( / (1 2 + 8 2 -（ 進棧15* ( / (1 2 + 8 2 - 7輸出716* ( / ( -1 2 + 8 2 - 7- 進棧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隊列定義 隊列是只能在表的一端進行插入、在另一端進行刪除操作的線性表。允許刪除元素的一端稱為隊頭，允許插入元素的一端稱為隊尾。顯然不論元素按何種順序進入隊列，也必然按這種順序出隊列，所以隊列又稱為先進先出（FIFO）表。隊列有兩個活動端，所以設置了對頭和隊尾兩個位置指針。一般隊頭指針記作front，隊尾指針記作rear。 abcfrontrear入隊出隊隊

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

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

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

12、; /入隊操作 void DeQueue(ElemType &e); /出隊操作 void GetHead(ElemType &e); /取隊頭元素;front和rear指針取值均為所指數(shù)組單元的下標。由于隊頭指針所指單元總是空的，length比實際能存儲的元素多一。 24（1）入隊操作若隊列不滿，則在隊尾插入元素x作為新的隊尾。void SqQueue:EnQueue(ElemType x) if(rear+1)% MAXSIZE= front) cout隊列已滿;else rear = (rear+1)%MAXSIZE;datarear=x; 常用算法 25（2）出隊操作 若隊列不空，則刪

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

14、(ElemType &e); /出隊操作void GetHead(ElemType &e); /求隊頭元素;30（1）求隊列的長度返回隊列的元素個數(shù)，即隊列的長度。 int LinkQueue:Length() QNode * p=front;int len=0;while(p!=rear)len+;p= p-next;return len;31（2）入隊列操作 插入元素x為隊列新的隊尾元素。void LinkQueue:EnQueue(ElemType x) QNode *s=new QNode;/建立新結(jié)點s s-data = x; s-next =NULL; rear -next = s;/在隊尾插入結(jié)點s rear = s;/修改隊尾指針32（3）出隊列操作若隊列不空，則刪除隊頭元素，用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;刪除最后一個元素時，需要修改尾指針，使其指向頭結(jié)點33（4）取隊頭元素若隊列不空，則用e返回隊頭元素；void L