第三章 棧和隊列

1、第三章 棧和隊列從數(shù)據(jù)結(jié)構(gòu)的角度看: 它們和線性表相同從數(shù)據(jù)類型的角度看: 它們和線性表不同 線性表 棧 隊列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) ( 1 i n+1) Delete(L, i) Delete(S, n) Delete(Q, 1) ( 1 i n)3.1 棧的類型定義 ADT Stack 數(shù)據(jù)對象：D ai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：R1 | ai-1, aiD, i=2,.,n 約定an 端為棧頂，a1 端為棧底。 基本操作： InitStack(&S) 操作結(jié)果：構(gòu)造

2、一個空棧S。 DestroyStack(&S) 初始條件：棧S已存在。 操作結(jié)果：棧S被銷毀。 ClearStack(&S) 初始條件：棧S已存在。 操作結(jié)果：將S清為空棧。 StackEmpty(S) 初始條件：棧S已存在。 操作結(jié)果：若棧S為空棧，則返回TRUE，否則FALE。 StackLength(S) 初始條件：棧S已存在。 操作結(jié)果：返回S的元素個數(shù)，即棧的長度。 GetTop(S, &e) 初始條件：棧S已存在且非空。 操作結(jié)果：用e返回S的棧頂元素。 Push(&S, e) 初始條件：棧S已存在。 操作結(jié)果：插入元素e為新的棧頂元素。 Pop(&S, &e) 初始條件：棧S已存

3、在且非空。 操作結(jié)果：刪除S的棧頂元素，并用e返回其值。 ADT Stack3.2 棧的應(yīng)用舉例 例一、 數(shù)制轉(zhuǎn)換 十進制數(shù)N和其他d進制數(shù)的轉(zhuǎn)換是計算機實現(xiàn)計算的基本問題，其解決方法很多，其中一個簡單算法基于下列原理： N = (N div d)d + N mod d (其中：div 為整除運算，mod 為求余運算）例如：（1348)10 = (2504)8 ，其運算過程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 假設(shè)現(xiàn)要編制一個滿足下列要求的程序：對于輸入的任意一個非負十進制整數(shù)，打印輸出與其等值的八進制數(shù)。由于上述計算過程

4、是從低位到高位順序產(chǎn)生八進制數(shù)的各個數(shù)位，而打印輸出，一般來說應(yīng)從高位到低位進行，恰好和計算過程相反。因此，若將計算過程中得到的八進制數(shù)的各位順序進棧，則按出棧序列打印輸出的即為與輸入對應(yīng)的八進制數(shù)。void conversion () / 對于輸入的任意一個非負十進制整數(shù)，打印輸出 / 與其等值的八進制數(shù) InitStack(S); / 構(gòu)造空棧 scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion 這是利用棧的后進先出特性

5、的最簡單的例子。在這個例子中，棧操作的序列是直線式的，即先一味地入棧，然后一味地出棧。也許，有的讀者會提出疑問：用數(shù)組直接實現(xiàn)不也很簡單嗎？仔細分析上述算法不難看出，棧的引入簡化了程序設(shè)計的問題，劃分了不同的關(guān)注層次，使思考范圍縮小了。而用數(shù)組不僅掩蓋了問題的本質(zhì)，還要分散精力去考慮數(shù)組下標增減等細節(jié)問題。 例二、 括號匹配的檢驗 假設(shè)表達式中允許包含兩種括號：圓括號和方括號，其嵌套的順序隨意，即（）或（ ）等為正確的格式，（ ）或（ ）或 ( )均為不正確的格式。檢驗括號是否匹配的方法可用期待的急迫程度這個概念來描述。例如考慮下列括號序列： ( ) 1 2 3 4 5 6 7 8分析可能出現(xiàn)

6、的不匹配的情況:1) 到來的右括弧非是所“期待”的;2) 到來的是“不速之客”;3) 直到結(jié)束，也沒有到來所“期待”的。status matching(string& exp) / 檢驗表達式中所含括弧是否正確嵌套，若是，則返回 / OK，否則返回ERROR int state = 1; while (i=length(exp) & state) swith of expi case 左括弧: Push(S,expi); i+; break; case ): if (NOT StackEmpty(S) & GetTop(S) = () Pop(S,e); i+; else state = 0

7、break; if ( state & StackEmpty(S) ) return OK else return ERROR; 例三、行編輯程序問題一個簡單的行編輯程序的功能是：接受用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。每接受一個字符即存入用戶數(shù)據(jù)區(qū)”不恰當。較好的做法是，設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶輸入出差錯，并在發(fā)現(xiàn)有誤時可以及時更正。例如，可用一個退格符“#”表示前一個字符無效；可用一個退行符“”，表示當前行中的字符均無效。例如，假設(shè)從終端接受了這樣兩行字符： whli#ilr#e（s#*s) outchaputchar(*

8、s=#+);則實際有效的是下列兩行： while (*s) putchar(*s+);void LineEdit() / 利用字符棧S，從終端接收一行并傳送至調(diào)用過程 / 的數(shù)據(jù)區(qū)。 InitStack(S); /構(gòu)造空棧S ch = getchar(); /從終端接收第一個字符 while (ch != EOF) /EOF為全文結(jié)束符 while (ch != EOF & ch != n) switch (ch) case # : Pop(S, c); break; / 僅當棧非空時退棧 case : ClearStack(S); break; / 重置S為空棧 default : Push

9、(S, ch); break; / 有效字符進棧，未考慮棧滿情形 ch = getchar(); / 從終端接收下一個字符 將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)； ClearStack(S); / 重置S為空棧 if (ch != EOF) ch = getchar(); DestroyStack(S);例四、 迷宮求解求迷宮中從入口到出口的所有路徑是一個經(jīng)典的程序設(shè)計問題。由于計算機解迷宮時，通常用的是“窮舉求解”的方法，即從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，顯

10、然需要用一個后進先出的結(jié)構(gòu)來保存從入口到當前位置的路徑。因此，在求迷宮通路的算法中應(yīng)用“?！币簿褪亲匀欢坏氖铝恕＜僭O(shè)迷宮如下圖所示:#$#$#$#Q# 假設(shè)“當前位置”指的是“在搜索過程中某一時刻所在圖中某個方塊位置”，則求迷宮中一條路徑的算法的基本思想是：若當前位置可通，則納入當前路徑，并繼續(xù)朝“下一位置”探索，即切換“下一位置”為“當前位置”，如此重復(fù)直至到達出口；若當前位置“不可通”，則應(yīng)順著“來向”退回到“前一通道塊”，然后朝著除“來向”之外的其他方向繼續(xù)探索；若該通道塊的四周四個方塊均“不可通”，則應(yīng)從“當前路徑”上刪除該通道塊。所謂“下一位置”指的是“當前位置”四周四個方向（東、

11、南、西、北）上相鄰的方塊。假設(shè)以棧S記錄“當前路徑”，則棧頂中存放的是“當前路徑上最后一個通道塊”。由此，“納入路徑”的操作即為“當前位置入?！?；“從當前路徑上刪除前一通道塊”的操作即為“出?！薄?求迷宮中一條從入口到出口的路徑的算法可簡單描述如下： 設(shè)定當前位置的初值為入口位置； do 若當前位置可通， 則將當前位置插入棧頂； / 納入路徑 若該位置是出口位置，則結(jié)束； / 求得路徑存放在棧中 否則切換當前位置的東鄰方塊為新的當前位置； 否則 若棧不空且棧頂位置尚有其他方向未被探索， 則設(shè)定新的當前位置為: 沿順時針方向旋轉(zhuǎn) 找到的棧頂位置的下一相鄰塊； 若棧不空但棧頂位置的四周均不可通，

12、則 刪去棧頂位置； / 從路徑中刪去該通道塊 若棧不空，則重新測試新的棧頂位置， 直至找到一個可通的相鄰塊或出棧至?？眨?while (棧不空）； 在此，尚需說明一點的是，所謂當前位置可通，指的是未曾走到過的通道塊，即要求該方塊位置不僅是通道塊，而且既不在當前路徑上（否則所求路徑就不是簡單路徑），也不是曾經(jīng)納入過路徑后又從路徑上刪除的通道塊（否則只能在死胡同內(nèi)轉(zhuǎn)圈）。 typedef struct int ord; / 通道塊在路徑上的“序號” PosType seat; / 通道塊在迷宮中的“坐標位置” int di; / 從此通道塊走向下一通道塊的“方向” SElemType; / 棧的元

13、素類型Status MazePath ( MazeType maze, PosType start, PosType end ) / 若迷宮maze中從入口 start到出口 end的通道， / 則求得一條存放在棧中（從棧底到棧頂），并返回 / TRUE；否則返回FALSE InitStack(S); curpos = start; / 設(shè)定“當前位置”為“入口位置” curstep = 1; / 探索第一步 do if (Pass (curpos) / 當前位置可以通過，即是未曾走到過的通道塊 FootPrint (curpos); / 留下足跡 e = ( curstep, curpos,

14、 1 ); Push (S,e); / 加入路徑 if ( curpos = end ) return (TRUE); / 到達終點（出口） curpos = NextPos ( curpos, 1 ); / 下一位置是當前位置的東鄰 curstep+; / 探索下一步 else / 當前位置不能通過 if (!StackEmpty(S) Pop (S,e); while (e.di=4 & !StackEmpty(S) MarkPrint (e.seat); Pop (S,e); / 留下不能通過的標記，并退回一步 / while if (e.di4) e.di+; Push ( S, e)

15、; / 換下一個方向探索 curpos = NextPos (curpos, e.di ); / 設(shè)定當前位置是該新方向上的相鄰塊 / if / if / else while ( !StackEmpty(S) ); return (FALSE); / MazePath 例五、 表達式求值限于二元運算符的表達式定義: 表達式 := (操作數(shù)) + (運算符) + (操作數(shù)) 操作數(shù) := 簡單變量 | 表達式 簡單變量 : = 標識符 | 無符號整數(shù)在計算機中，表達式可以有三種不同的標識方法設(shè) Exp = S1 + OP + S2則稱 OP + S1 + S2 為表達式的前綴表示法 稱 S1

16、+ OP + S2 為表達式的中綴表示法 稱 S1 + S2 + OP 為表達式的后綴表示法 可見，它以運算符所在不同位置命名的。例如: Exp = a b + (c - d / e) f前綴式: + a b - c / d e f中綴式: a b + c - d / e f后綴式: a b c d e / - f +結(jié)論:1) 操作數(shù)之間的相對次序不變;2) 運算符的相對次序不同;3) 中綴式丟失了括弧信息，致使運算的次序不確定;4) 前綴式的運算規(guī)則為:連續(xù)出現(xiàn)的兩個操作數(shù)和在它們之前且緊靠它們的運算符構(gòu)成一個最小表達式;5) 后綴式的運算規(guī)則為:l 運算符在式中出現(xiàn)的順序恰為表達式的運算

17、順序;l 每個運算符和在它之前出現(xiàn)且緊靠它的兩個操作數(shù)構(gòu)成一個最小表達式;l 如何從后綴式求值？ 先找運算符，后找操作數(shù)l 如何從原表達式求得后綴式？分析 “原表達式” 和 “后綴式”中的運算符:原表達式: a + b c - d / e f 后綴式: a b c + d e / f - 運算符 # ( + - / * 優(yōu)先數(shù) -1 0 1 1 2 2 3每個運算符的運算次序要由它之后的一個運算符來定，若當前運算符的優(yōu)先數(shù)小，則暫不進行; 否則立即進行。表達式求值的規(guī)則:1) 設(shè)立運算符棧和操作數(shù)棧;2) 設(shè)表達式的結(jié)束符為“#”,予設(shè)運算符棧的棧底為“#”3) 若當前字符是操作數(shù)，則進操作數(shù)

18、棧;4) 若當前運算符的優(yōu)先數(shù)高于棧頂運算符，則進棧;5) 否則，退出棧頂運算符作相應(yīng)運算;6) “(”對它之前后的運算符起隔離作用，“)”可視為自相應(yīng)左括弧開始的表達式的結(jié)束符。算法描述如下:OperandType EvaluateExpression() / 算術(shù)表達式求值的算符優(yōu)先算法。設(shè)OPTR和OPND / 分別為運算符棧和運算數(shù)棧，OP為運算符集合。 InitStack (OPTR); Push (OPTR, #); initStack (OPND); c = getchar(); while (c!= # | GetTop(OPTR)!= #) if (!In(c, OP) Pu

19、sh(OPND, c); c = getchar(); / 不是運算符則進棧 else switch (precede(GetTop(OPTR), c) case # / 退棧并將運算結(jié)果入棧 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch / while return GetTop(OPND); / EvaluateExpression 例六、實現(xiàn)遞歸在高級語言編制的程序中，調(diào)用函數(shù)與被調(diào)用函數(shù)之間的鏈接和信息交換必須通過棧例進行。當在一個函數(shù)的運行期

20、間調(diào)用另一個函數(shù)時，在運行該被調(diào)用函數(shù)之前，需先完成三件事:1) 將所有的實在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存;2) 為被調(diào)用函數(shù)的局部變量分配存儲區(qū);3) 將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成:1) 保存被調(diào)函數(shù)的計算結(jié)果;2) 釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū);3) 依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。 多個函數(shù)嵌套調(diào)用的規(guī)則是:后調(diào)用先返回此時的內(nèi)存管理實行“棧式管理”遞歸過程指向過程中占用的數(shù)據(jù)區(qū)，稱之為遞歸工作棧每一層的遞歸參數(shù)合成一個記錄，稱之為遞歸工作記錄棧頂記錄指示當前層的執(zhí)行情況，稱之為當前活動記錄棧頂指針， 稱之為當前環(huán)境指針例如:v

21、oid hanoi (int n, char x, char y, char z) / 將塔座x上按直徑由小到大且至上而下編號為1至n / 的n個圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。1 2 if (n=1)3 move(x, 1, z); / 將編號為的圓盤從x移到z4 else 5 hanoi(n-1, x, z, y); / 將x上編號為至n-1的圓 / 盤移到y(tǒng), z作輔助塔6 move(x, n, z); / 將編號為n的圓盤從x移到z7 hanoi(n-1, y, x, z); / 將y上編號為至n-1的圓盤 / 移到z, x作輔助塔8 9 3.3 棧類型的實現(xiàn)順序棧 類似于線

22、性表的順序映象實現(xiàn)，指向表尾的指針可以作為棧頂指針。鏈棧利用鏈表實現(xiàn)棧，注意鏈表中指針的方向是從棧頂?shù)綏５住? include LinkList.htemplate class stack private :List stackList; public : / constructor stack(void); / access methodBOOL stackEmpty(void);int stackLength(void);ElemType* getTop(void); / modification methodvoid Push( ElemType* item);ElemType* Pop

23、(void);void clearStack(void);templatevoid stack:Push(ElemType* item) stackList.insFirst(item);templateElemType* stack: Pop(void) if stackList.listEmpty( ) return NULL; else return stackList.delFirst( )3.4 隊列的類型定義 ADT Queue 數(shù)據(jù)對象：Dai | aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：R1 | ai-1, ai D, i=2,.,n 約定其中a1 端為隊列

24、頭， an 端為隊列尾。 基本操作： InitQueue(&Q) 操作結(jié)果：構(gòu)造一個空隊列Q。 DestroyQueue(&Q) 初始條件：隊列Q已存在。 操作結(jié)果：隊列Q被銷毀，不再存在。 ClearQueue(&Q) 初始條件：隊列Q已存在。 操作結(jié)果：將Q清為空隊列。 QueueEmpty(Q) 初始條件：隊列Q已存在。操作結(jié)果：若Q為空隊列，則返回TRUE， 否則返回FALSE。 QueueLength(Q) 初始條件：隊列Q已存在。 操作結(jié)果：返回Q的元素個數(shù)，即隊列的長度。 GetHead(Q, &e) 初始條件：Q為非空隊列。 操作結(jié)果：用e返回Q的隊頭元素。 EnQueue(&

25、Q, e) 初始條件：隊列Q已存在。 操作結(jié)果：插入元素e為Q的新的隊尾元素。 DeQueue(&Q, &e) 初始條件：Q為非空隊列。 操作結(jié)果：刪除Q的隊頭元素，并用e返回其值。 ADT Queue3.5 隊列類型的實現(xiàn) 鏈隊列鏈式映象# include LinkList.htemplate class Queue private :List queueList; public : / constructorQueue(void):queueList( );Queue(void) / access methodBOOL queueEmpty(void) return queueList.l

26、istEmpty( ) int queueLength(void) return queueList.listSize( ) ElemType* getHead(void); / modification methodvoid enQueue( ElemType* pitem);ElemType* deQueue(void);void clearQueue(void);templatevoid Queue:enQueue( ElemType* pitem) queueList.addTail(pitem);templateElemType* Queue: deQueue(void) if qu

27、eueList.listEmpty( ) return NULL; else return queueList.delFirst( ) 循環(huán)隊列順序映象const int MaxQSize = 100;templateclass Queue private :int front, rear, curSize, maxSize;ElemType* qList; public : / constructorQueue(void);Queue(void) / access methodBOOL queueEmpty(void);BOOL queueFULL(void);int queueLength

28、(void);ElemType* getHead(void); / modification methodvoid enQueue( ElemType* item);ElemType* deQueue(void);void clearQueue(void);3.6 隊列應(yīng)用舉例排隊問題的系統(tǒng)仿真一、需求分析和規(guī)格說明編制一個事件驅(qū)動仿真程序以模擬理發(fā)館內(nèi)一天的活動，要求輸出在一天的營業(yè)時間內(nèi)，到達的顧客人數(shù)、顧客在館內(nèi)的平均逗留時間和排隊等候理發(fā)的平均人數(shù)以及在營業(yè)時間內(nèi)空椅子的平均數(shù)。假設(shè)理發(fā)館內(nèi)設(shè)有N把理發(fā)椅，一天內(nèi)連續(xù)營業(yè)T小時。在T小時內(nèi)顧客到達的時間及顧客理發(fā)所需時間均隨機生成，過了

29、營業(yè)時間，不再有顧客進門，但仍需繼續(xù)為已進入店內(nèi)的顧客理發(fā)，直至最后一名顧客離開為止。二、概要設(shè)計 1. 主程序為: void BarberShop_Simulation( int chairNum, int CloseTime) / 理發(fā)店業(yè)務(wù)模擬，統(tǒng)計一天內(nèi)顧客在店內(nèi)逗留的平均時間 / 和顧客在等待理發(fā)時排隊的平均長度以及空椅子的平均數(shù) OpenForDay; / 初始化 while MoreEvent do EventDrived(OccurTime, EventType); / 事件驅(qū)動 switch (EventType) case A : CustomerArrived; brea

30、k; / 處理到達事件 case D : CustomerDeparture; break; / 處理離開事件 default : Invalid; / switch / while CloseForDay; / 計算平均逗留時間和排隊的平均長度 / BarberShop_Simulation 2. 數(shù)據(jù)類型為:ADT Event (事件) 數(shù)據(jù)對象: D = 事件的發(fā)生時刻，事件類型 數(shù)據(jù)關(guān)系: R = 基本操作: Initiate(&E,oT, eT); 操作結(jié)果: 產(chǎn)生一個發(fā)生時間為oT, 事件類型為eT 的事件E; GetOccurTime(ev); 初始條件: 事件ev已存在， 操作

31、結(jié)果: 返回該事件的發(fā)生時間; GetEventType(ev); 初始條件: 事件ev已存在; 操作結(jié)果: 返回該事件的類型;ADT customer(顧客) 數(shù)據(jù)對象: D = 進門時刻，理發(fā)所需時間; 數(shù)據(jù)關(guān)系: R = 基本操作: Initiate(&P,aT, cT); 操作結(jié)果: 產(chǎn)生一個進門時刻為aT, 理發(fā)時間為cT 的顧客P; GetArrivalTime(Ps); 初始條件: 顧客Ps已存在， 操作結(jié)果: 返回該顧客的進門時刻; GetCutTime(Ps); 初始條件: 顧客Ps已存在; 操作結(jié)果: 返回該顧客的理發(fā)時間;ADT OrderedList(有序表) 數(shù)據(jù)對象

32、: 是上述定義的事件的集合 數(shù)據(jù)關(guān)系: 按事件的發(fā)生時刻自小至大有序 基本操作: 在線性表的操作的基礎(chǔ)上添加一個有序表的插入 Insert(&OL, x) 初始條件: 有序表OL已存在; 操作結(jié)果: 在有序表中插入x, 并保持表的有序性;ADT (數(shù)據(jù)元素為上述定義的顧客的)隊列三、詳細設(shè)計class Event private: int occurTime; char eventType; public: Event(int oT, char tp):occurTime(oT), eventType(tp) int evTime(void) return occurTime char evT

33、ype(void) return eventType class Customer private: int arrivalTime; int cutTime; public: Customer(int aT, char cT): arrivalTime(oT), cutTime(ct) int avTime(void) return arrivalTime int cuTime(void) return cutTime templateclass orderedList : public List public:orderedList(void); / 構(gòu)造函數(shù)，初始化一個空表int locate(ElemType* pitem); / 在有序表中查詢數(shù)據(jù)元素pitem, 若存在，則移 / 動當前指針指向該結(jié)點并返回1，否則移動當前 / 指針指向第一個大于它的結(jié)點并返回0void insert( ElemType* item); / 插入數(shù)據(jù)元素item, 并保持表的有序性templatevo