2.2堆棧4小節(jié)共講義

1、堆棧計算機如何進(jìn)行表達(dá)式求值？例 算術(shù)表達(dá)式5+6/2-3*4。正確理解：5+6/2-3*4 = 5+3-3*4 = 8-3*4 = 8-12 = -4由兩類對象的：運算數(shù)，如2、3、4運算符號，如+、-、*、/不同運算符號優(yōu)先級不一樣后綴表達(dá)式中綴表達(dá)式：運算符號位于兩個運算數(shù)之間。如 ，a b c d e后綴表達(dá)式：運算符號位于兩個運算數(shù)之后。如， a b c d e 例 6 2 3 4 2 = ?后綴表達(dá)式求值策略：從左向右“掃描”，逐個處理運算數(shù)和運算符號遇到運算數(shù)怎么辦？如何“記住”目前還不未參與運算的數(shù)？遇到運算符號怎么辦？對應(yīng)的運算數(shù)是什么？啟示：需要有種方法，能順序運算數(shù)，并在

2、需要時“倒序”輸出！例 6 2 3 4 2 = ?toptop對象: ( 運算符 )對象: 2 (運算數(shù) )toptop對象: (運算符)Pop: 8T( N ) = O ( N )對象: (運算符)對象: 4 (運算數(shù) )對象: ( 運算符 )對象: 3 (運算數(shù) )對象: 6 (運算數(shù) )對象: 2 ( 運算數(shù) )8堆棧的抽象數(shù)據(jù)類型描述堆棧（Stack）：具有一定操作約束的線性表只在一端（棧頂，Top）做、刪除數(shù)據(jù)：入棧（Push）刪除數(shù)據(jù)：出棧（Pop）先出：Last InOut（LIFO）堆棧的抽象數(shù)據(jù)類型描述類型名稱: 堆棧（Stack）數(shù)據(jù)對象集：一個有0個或多個元素的有窮線性表

3、。操作集：長度為MaxSize的堆棧S Stack，堆棧元素item ElementType 1、Stack CreateStack(MaxSize )： 生成空堆棧，其最大長度為MaxSize；MaxSize )：判斷堆棧S是否已滿；2、IsFull( Stack S,3、void Push( Stack S, ElementType item )：將元素item壓入堆棧；4、IsEmpty ( Stack S )：判斷堆棧S是否為空；5、ElementType Pop( Stack S )：刪除并返回棧頂元素；ABCDCreatStack( );Push(S,A);Push(S,B);Pu

4、sh(S,C);ADCB x=Pop(S);x=Pop(S);x=Pop(S);IsEmpty (S)TopTopTopTopABAC BATopTopTopTop5435261C BAB AAPush 和 Pop 可以穿插交替進(jìn)行；按照操作系列Push(S,A), Push(S,B),Push(S,C),Pop(S),Pop(S),Pop(S)堆棧輸出是？CBA而Push(S,A), Pop(S),Push(S,B),Push(S,C),Pop(S),Pop(S)堆棧輸出是?ACB例 如果三個字符按ABC順序壓入堆棧ABC的所有排列都可能是出棧的序列嗎？可以產(chǎn)生CAB這樣的序列嗎？棧的順序?qū)?/p>

5、現(xiàn)棧的順序結(jié)構(gòu)通常由一個一維數(shù)組和一個棧頂元素位置的變量組成。#define MaxSize ElementType DataMaxSize; Top;(1)入棧 Stack; B PtrSTopAvoid Push( Stack *PtrS, ElementType item )if ( PtrS-Top = MaxSize-1 ) prf(“堆棧滿”); return;else PtrS-Data+(PtrS-Top) = item; return;(2)出棧TopPtrSBAElementType Pop( Stack *PtrS )if ( PtrS-Top = -1 ) prf(“堆

6、?？铡?;return ERROR;/* ERROR是ElementType的特殊值，標(biāo)志錯誤*/ elsereturn ( PtrS-Data(PtrS-Top)- );例 請用一個數(shù)組實現(xiàn)兩個堆棧，要求最大地利用數(shù)組空間，使數(shù)組只要有空間入棧操作就可以成功。【分析】 一種比較聰明的方法是使這兩個棧分別從數(shù)組的兩頭開始向中間生長；當(dāng)兩個棧的棧頂指針相遇時，表示兩個棧都滿了。#define MaxSize ElementType DataMaxSize;Top1;Top2;/* 堆棧的棧頂指針 */* 堆棧的棧頂指針 */ S;S.Top1 = -1;S.Top2 = MaxSize;Elem

7、entType Pop( struct DStack *PtrS,Tag ) /* Tag作為區(qū)分兩個堆棧的標(biāo)志，取值為1和2 */if ( Tag = 1 ) /* 對第一個堆棧操作 */if ( PtrS-Top1 = -1 ) /*堆棧1空 */prf(“堆棧1空”);return NULL; else return PtrS-Data(PtrS-Top1)-; else /* 對第二個堆棧操作 */if ( PtrS-Top2 = MaxSize ) /*堆棧2空 */prf(“堆棧2空”); return NULL; else return PtrS-Data(PtrS-Top2)+

8、;void Push( struct DStack *PtrS, ElementType item,Tag ) /* Tag作為區(qū)分兩個堆棧的標(biāo)志，取值為1和2 */if ( PtrS-Top2 PtrS-Top1 = 1) /*堆棧滿*/prf(“堆棧滿”);return ;if ( Tag = 1 ) /* 對第一個堆棧操作 */PtrS-Data+(PtrS-Top1) = item; else/* 對第二個堆棧操作 */ PtrS-Data-(PtrS-Top2) = item;堆棧的鏈?zhǔn)綄崿F(xiàn)棧的鏈?zhǔn)浇Y(jié)構(gòu)實際上就是一個單鏈表，叫做鏈棧。和刪除操作只能在鏈棧的棧頂進(jìn)行。棧頂指針Top應(yīng)該

9、在鏈表的哪一頭？typedef struct NodeElementType Data;struct Node *Next; LinkStack; LinkStack *Top;堆棧初始化（建立空棧）判斷堆棧S是否為空SLinkStack *CreateStack() /* 構(gòu)建一個堆棧的頭結(jié)點，返回指針 */ LinkStack *S;S = malloc( sizeof(struct Node ); S-Next = NULL;return S;IsEmpty( LinkStack *S )/*判斷堆棧S是否為空，若為空函數(shù)返回整數(shù) 1，否則返回0 */return ( S-Next =

10、NULL );12/23ElementType Pop( LinkStack *S ) /* 刪除并返回堆棧S的棧頂元素 */ struct Node *Cell; ElementType TopElem;if( IsEmpty( S ) ) prf(“堆?？铡?; return NULL; else Cell = S-Next;S-Next =Cell-Next; TopElem =Cell -Element; free(Cell);return TopElem;void Push( ElementType item, LinkStack *S ) /* 將元素item壓入堆棧S */ st

11、ruct Node *TmpCell;TmpCell = malloc( sizeof( struct Node ) );TmpCell-Element = item; TmpCell-Next = S-Next; S-Next = TmpCell;堆棧應(yīng)用：表達(dá)式求值回憶：應(yīng)用堆棧實現(xiàn)后綴表達(dá)式求值的基本過程：從左到右讀入后綴表達(dá)式的各項（運算符或運算數(shù)）；對象分割求值字符序列的后綴表達(dá)式對象序列的后綴表達(dá)式結(jié)果值GetOp利用堆棧1.2 1.3 + 2 4.2 * -1.2 1.3 + 2 4.2 *-5.9運算數(shù)：入棧；運算符：從堆棧出適當(dāng)數(shù)量的運算數(shù)，計算并結(jié)果入棧；最后，堆棧頂上的元

12、素就是表達(dá)式的結(jié)果值。中綴表達(dá)式求值基本策略：將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，然后求值如何將中綴表達(dá)式轉(zhuǎn)換為后綴？觀察一個簡單例子： 2+9/3-5運算數(shù)相對順序不變運算符號順序發(fā)生改變2 9 3 / + 5 -堆棧！需要“等待中”的運算符號要將當(dāng)前運算符號與“等待中”的最后一個運算符號比較有括號怎么辦？例 a ( b c ) d =?cd輸出:abtopT( N ) = O ( N )16/23輸入對象: a (操作數(shù))輸入對象: (乘法)輸入對象: ( (左括號)輸入對象: b (操作數(shù))輸入對象: (加法)輸入對象: c (操作數(shù))輸入對象: ) (右括號)輸入對象: (除法)輸入對象:

13、d (操作數(shù))a b c d 中綴表達(dá)式求值對象分割字符序列的中綴表達(dá)式對象序列的中綴表達(dá)式GetOp利用堆棧轉(zhuǎn)換求值對象序列的后綴表達(dá)式結(jié)果值利用堆棧對象分割(1.2 +1.3 2) * 4.2(1.2 +1.3 2)*4.2GetOp利用堆棧轉(zhuǎn)換求值2.11.2 1.3 + 2 - 4.2*利用堆棧中綴表達(dá)式如何轉(zhuǎn)換為后綴表達(dá)式從頭到尾中綴表達(dá)式的每個對象，對不同對象按不同的情況處理。 運算數(shù)：直接輸出； 左括號：壓入堆棧； 右括號：將棧頂?shù)倪\算符彈出并輸出，直到遇到左括號（出棧，不輸出）； 運算符：若優(yōu)先級大于棧頂運算符時，則把它壓棧；若優(yōu)先級小于等于棧頂運算符時，將棧頂運算符彈出并輸出；再比較新的棧頂運算符，直到該運算符大于棧頂運算符優(yōu)先級為止，然后將該運算符壓棧； 若各對象處理完畢，則把堆棧中存留的運算符一并輸出。中綴轉(zhuǎn)換為后綴示例： （ 2*（9+6/3-5）+4）步驟待處理表達(dá)式堆棧狀態(tài)（底頂）輸出狀態(tài)12*（9+6/3-5）+42*（9+6/3-5）+423（9+6/3-5）+4*249+6/3-5）+4*（25+6/3-5）+4*（2 966/3-5）+4*（