第三章棧和隊列

從數據結構角度看，棧和隊列也是線性表。

棧和隊列的基本操作是線性表操作的子集，它們是操作受限的線性表。

3.1 棧 stack

限定僅在表尾進行插入和刪除操作的線性表。

表尾端 --> 棧頂 top

表頭端 --> 棧底 bottom

后進先出 LIFO??last in first out

插入元素 --> 入棧

刪除元素 --> 出棧

?

順序棧

非空棧中的棧頂指針始終在棧頂元素的下一個位置。

3.2 棧的應用舉例

3.2.1 數制轉換

3.2.2 括號匹配檢驗

可用“期待的緊迫程度”這個概念來描述。

在算法中設置一個棧；

1、每讀入一個括號，若是右括號，則或者使置于棧頂的最急迫的期待得以消解，或者是不合法的情況；

2、若是左括號，則作為一個新的更急迫的期待壓入棧中，自然使原有的在棧中的所有未消解的期待的緊迫性都降了一級；

算法開始和結束時，棧都應該是空的。

?

3.2.3 行編輯程序

遇#退棧

遇@清棧

遇換行輸出棧

?

3.2.4 迷宮求解

棧中所存信息為，坐標+步數+搜尋方向

墻-1

可走0

當前判斷的位置與棧頂元素有關

?

3.2.5 表達式求值

表達式求值算法：

使用兩個工作棧：1、運算符棧，2、操作數棧。

基本思想：

1、首先置操作數棧為空棧，表達式起始符“#”為運算符棧的棧底元素；

2、依次讀入表達式的每個字符，若是操作數則進操作數棧，若是運算符，則和運算符棧的棧頂運算符比較優先權后作相應操作，直至整個表達式求值完畢。棧頂高則計算，棧頂低則壓棧。

符號 + - * / （ ）

棧頂

+ ?> ?+ - )

- ?> ?+ - )

* ?> ?* / + - )

/ ?> ?* / + - )

( ?< all ?= )

?

3.3 棧與遞歸的實現

棧：函數調用

調用函數和被調用函數之間的鏈接及信息交換需通過棧來進行

?

遞歸函數

函數中有直接或間接調用自身函數的語句

條件：1、降階；2、有出口。

編譯軟件開辟的棧空間是有限的，當遞歸調用時，嵌套的層次往往很多，可能發生棧溢出的現象。

?

3.4 隊列

隊列 queue：先進先出（First In First Out，FIFO）的線性表。

在表的一端進行插入，而在另一端刪除元素。

隊尾 rear：允許插入的一端

隊頭 front：允許刪除的一端

?

典型例子：操作系統中的作業排隊

雙端隊列：限定插入和刪除操作在表的兩端進行的線性表。

兩端插入，一端刪除；

兩端刪除，一端插入；

從插入端刪除（棧底相連的棧）。

?

順序隊列（循環隊列）：

初始化建空隊列時，令front=rear=0

插入隊尾，尾指針增1

刪除隊頭，頭指針增1

在非空隊列中，頭指針始終指向隊列頭元素，而尾指針始終指向隊列尾的下一個位置

?

循環隊列：

1、另設一個標志位以區別隊列是空還是滿；

2、少用一個元素空間，約定以“隊列頭指針在隊列尾指針的下一位置”作為隊列呈滿的標志。

頭尾指針對存儲空間MAX_QSIZE求余，形成循環隊列。

?

如果用戶的應用程序中設有循環隊列，則必須為它設定一個最大隊列長度；

若用戶無法預估所用隊列的最大長度，則采用鏈隊列。

?