第3章 數(shù)據(jù)結(jié)構(gòu)的棧和隊(duì)列

1、Data Structure limin_limin_ 2012.11.112012.11.11 Data Structure 棧棧 隊(duì)列隊(duì)列 棧和隊(duì)列的應(yīng)用實(shí)例棧和隊(duì)列的應(yīng)用實(shí)例 Data Structure an a1 a2 . 棧底棧底 棧頂棧頂 . 出棧出棧 進(jìn)棧進(jìn)棧 棧棧s=(a1,a2,an) Data Structure 棧：棧：后進(jìn)先出后進(jìn)先出的線性表（的線性表（LIFO）。）。 棧的基本運(yùn)算棧的基本運(yùn)算 InitStack ( S ); StackEmpty ( S ); StackFull ( S ); Push ( S , x ); Pop ( S ); StackTop

2、 ( S ); Data Structure 順序棧：棧的順序存儲結(jié)構(gòu)。順序棧：棧的順序存儲結(jié)構(gòu)。 順序棧的類型定義：順序棧的類型定義：P33頁頁 基本定義：基本定義： 空棧：空棧：Stop top = StackSize -1 下溢：?？諘r(shí)退棧下溢：?？諘r(shí)退棧 上溢：棧滿時(shí)入棧上溢：棧滿時(shí)入棧 順序棧六種基本運(yùn)算的實(shí)現(xiàn)：順序棧六種基本運(yùn)算的實(shí)現(xiàn)：P33-P34頁頁 Data Structure 鏈棧：棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)。鏈棧：棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)。 鏈棧的類型定義：鏈棧的類型定義：P35頁頁 鏈棧六種基本運(yùn)算的實(shí)現(xiàn)：鏈棧六種基本運(yùn)算的實(shí)現(xiàn)：P36頁頁 注：由于鏈棧的存儲空間是動態(tài)分配的，我們不考慮

3、內(nèi)存注：由于鏈棧的存儲空間是動態(tài)分配的，我們不考慮內(nèi)存 不夠用的情況，所以鏈棧沒有上溢，不存在棧滿的情況。不夠用的情況，所以鏈棧沒有上溢，不存在棧滿的情況。 棧頂指針 a1anan-1 Data Structure a1 a2 a3.an 入隊(duì)入隊(duì) 出隊(duì)出隊(duì) frontrear 隊(duì)列隊(duì)列Q=(a1,a2,an) Data Structure 隊(duì)列的定義：隊(duì)列的定義：P37頁頁 隊(duì)列：先進(jìn)先出（隊(duì)列：先進(jìn)先出（FIFO）的線性表。）的線性表。 隊(duì)列有六種基本操作隊(duì)列有六種基本操作 InitQueue ( Q ); QueueEmpty ( Q ); QueueFull ( Q ); EnQueu

4、e ( Q , x ); DeQueue ( Q ); QueueFront ( Q ); Data Structure 順序隊(duì)列：隊(duì)列的順序存儲結(jié)構(gòu)。順序隊(duì)列：隊(duì)列的順序存儲結(jié)構(gòu)。 基本概念：基本概念： 隊(duì)頭指針：隊(duì)頭指針：front（指向隊(duì)頭元素）（指向隊(duì)頭元素） 隊(duì)尾指針：隊(duì)尾指針：rear （指向隊(duì)尾元素的下一個(gè)位置指向隊(duì)尾元素的下一個(gè)位置） 上溢上溢 & 下溢下溢 & 假上溢假上溢 循環(huán)隊(duì)列：存儲在循環(huán)向量中的隊(duì)列。循環(huán)隊(duì)列：存儲在循環(huán)向量中的隊(duì)列。 順序隊(duì)列和循環(huán)隊(duì)列的操作示意圖：順序隊(duì)列和循環(huán)隊(duì)列的操作示意圖：P38頁頁 Data Structure 0 1 2 3 4 5 re

5、ar front J5 J6 J7 0 1 2 3 4 5 rear front J4 J9 J8 J4,J5,J6出隊(duì)出隊(duì) J7,J8,J9入隊(duì)入隊(duì) 隊(duì)空：隊(duì)空：front=rearfront=rear 隊(duì)滿：隊(duì)滿：front=rearfront=rear J5 J6 0 1 2 3 4 5 rear front 初始狀態(tài) J4 Data Structure 循環(huán)隊(duì)列的類型定義：循環(huán)隊(duì)列的類型定義：P39頁頁 循環(huán)隊(duì)列的上溢判定方法循環(huán)隊(duì)列的上溢判定方法 1、設(shè)布爾變量記錄、設(shè)布爾變量記錄 2、少用一個(gè)元素空間、少用一個(gè)元素空間 3、設(shè)計(jì)數(shù)器、設(shè)計(jì)數(shù)器 循環(huán)隊(duì)列的六種基本操作的具體實(shí)現(xiàn)：循環(huán)

6、隊(duì)列的六種基本操作的具體實(shí)現(xiàn)：P39-P40頁頁 Data Structure 鏈隊(duì)列：隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)。鏈隊(duì)列：隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)。 鏈隊(duì)列的類型定義：鏈隊(duì)列的類型定義：P41頁頁 鏈隊(duì)列的五種基本操作的具體實(shí)現(xiàn)：鏈隊(duì)列的五種基本操作的具體實(shí)現(xiàn)：P41-P42頁頁 注：鏈隊(duì)列和鏈棧類似，不存在上溢的情況，原因在于我注：鏈隊(duì)列和鏈棧類似，不存在上溢的情況，原因在于我 們假定內(nèi)在是足夠大的。們假定內(nèi)在是足夠大的。 Data Structure 1、數(shù)制轉(zhuǎn)換、數(shù)制轉(zhuǎn)換 2、棧與遞歸、棧與遞歸 3、舞伴問題、舞伴問題 Data Structure 前提：表達(dá)式中只有兩種括號，圓括號和方括號 假設(shè)：

7、在表達(dá)式中括號嵌套的順序任意 比如：（）或（ ）等 為正確的格式！ 比如（ ）或（ ）或 （）) 為不正確的格式！ 要求：撰寫一算法驗(yàn)證輸入的括號序列是否是正確的 解決： 檢驗(yàn)括號是否匹配的方法可用“期待的急迫程度” 這個(gè)概念來描述。 Data Structure 例如：考慮下列括號序列： ( ) 1 2 3 4 5 6 7 8 每遇到一個(gè)括號就可能出現(xiàn)以下幾種情況: 1、來了個(gè)左括號 2、來了個(gè)右括號 右括號是所“期待”的 右括號不是所“期待”的 3、還剩余括號，直到結(jié)束也沒有到來所“期待”的括 弧 用棧來考慮用棧來考慮 如何實(shí)現(xiàn)！如何實(shí)現(xiàn)！ Data Structure 算法的設(shè)計(jì)思想：

8、1）凡出現(xiàn)左括弧，則進(jìn)棧； 2）凡出現(xiàn)右括弧，首先檢查棧是否空 若?？?，則表明該“右括弧”多余， 否則和棧頂元素比較， 若相匹配，則“左括弧出棧” ， 否則表明不匹配。 3）表達(dá)式檢驗(yàn)結(jié)束時(shí)， 若?？眨瑒t表明表達(dá)式中匹配正確， 否則表明“左括弧”有余。 Data Structure 為了解決計(jì)算機(jī)與打印機(jī)之間速度不匹配問題，通常設(shè)置為了解決計(jì)算機(jī)與打印機(jī)之間速度不匹配問題，通常設(shè)置 一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩 沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū) 的邏輯結(jié)構(gòu)

9、應(yīng)該是（的邏輯結(jié)構(gòu)應(yīng)該是（ ）。）。 A. 棧棧 B. 隊(duì)列隊(duì)列 C. 樹樹 D. 圖圖 B Data Structure 某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行 出隊(duì)操作。若元素出隊(duì)操作。若元素a、b、c、d、e依次入此隊(duì)列后再進(jìn)行依次入此隊(duì)列后再進(jìn)行 出隊(duì)操作，則不可能得到的出隊(duì)序列是出隊(duì)操作，則不可能得到的出隊(duì)序列是 （ ）。）。 A. bacde B. dbace C. dbcae D. ecbad C Data Structure 設(shè)棧設(shè)棧S和隊(duì)列和隊(duì)列Q的初始狀態(tài)均為空，元素的初始狀態(tài)均為空，元素abcdefg依次進(jìn)入依

10、次進(jìn)入 棧棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且，且7個(gè)元素出隊(duì)個(gè)元素出隊(duì) 的順序是的順序是bdcfeag，則棧，則棧S的容量至少是（的容量至少是（ ）。）。 A. 1 B. 2 C. 3 D. 4 C Data Structure 一個(gè)棧的入棧序列為A，B，C，D，E，則棧的不可能的 出棧序列是 。 A. A，B，C，D，E B. E，D，C，B，A C. D，E，C，B，A D. D，C，E，A，B D Data Structure 若進(jìn)棧序列為a，b，c，則通過出棧操作可能得到的a，b， c的不同排列個(gè)數(shù)為 。 A. 4 B. 5 C. 6 D. 7 B Data Structure 若元素a、b、c、d、e、f 依次進(jìn)棧，允許進(jìn)棧、退棧操作 交替進(jìn)行。但不允許連續(xù)三次進(jìn)行退棧工作，則不可能得 到的出棧序列是 （ ）。 A. dcebfa B. cbdaef C. bcaefd D. afedcb D Data Structure 元