數(shù)據(jù)結(jié)構(gòu)堆棧和隊(duì)列31 2

1、第第3章章 堆棧和隊(duì)列堆棧和隊(duì)列 3.1 堆棧堆棧3.2 堆棧的應(yīng)用堆棧的應(yīng)用3.3 隊(duì)列隊(duì)列3.4 優(yōu)先級(jí)隊(duì)列優(yōu)先級(jí)隊(duì)列本章主要知識(shí)點(diǎn)：本章主要知識(shí)點(diǎn)： 堆棧的基本概念，堆棧的用途堆棧的基本概念，堆棧的用途 順序堆棧類的設(shè)計(jì)方法，鏈?zhǔn)蕉褩ｎ惖脑O(shè)計(jì)方法順序堆棧類的設(shè)計(jì)方法，鏈?zhǔn)蕉褩ｎ惖脑O(shè)計(jì)方法 隊(duì)列的基本概念，隊(duì)列的用途隊(duì)列的基本概念，隊(duì)列的用途 順序循環(huán)隊(duì)列的基本實(shí)現(xiàn)原理，順序循環(huán)隊(duì)列的隊(duì)空順序循環(huán)隊(duì)列的基本實(shí)現(xiàn)原理，順序循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿判斷方法，順序循環(huán)隊(duì)列類的設(shè)計(jì)方法和隊(duì)滿判斷方法，順序循環(huán)隊(duì)列類的設(shè)計(jì)方法 鏈?zhǔn)蕉褩ｎ惖脑O(shè)計(jì)方法鏈?zhǔn)蕉褩ｎ惖脑O(shè)計(jì)方法 優(yōu)先級(jí)隊(duì)列的概念，優(yōu)先級(jí)隊(duì)列的用途

2、，順序優(yōu)先級(jí)優(yōu)先級(jí)隊(duì)列的概念，優(yōu)先級(jí)隊(duì)列的用途，順序優(yōu)先級(jí) 隊(duì)列的入隊(duì)列和出隊(duì)列操作設(shè)計(jì)方法隊(duì)列的入隊(duì)列和出隊(duì)列操作設(shè)計(jì)方法 3.1 堆棧堆棧3.1.1 堆棧的基本概念堆棧的基本概念堆棧堆棧（棧）是一種特殊的線性表，堆棧的數(shù)（棧）是一種特殊的線性表，堆棧的數(shù)據(jù)元素以及數(shù)據(jù)元素間的邏輯關(guān)系和線性表完全據(jù)元素以及數(shù)據(jù)元素間的邏輯關(guān)系和線性表完全相同，其相同，其差別差別是線性表允許在任意位置進(jìn)行插入是線性表允許在任意位置進(jìn)行插入和刪除操作，而和刪除操作，而堆棧只允許在堆棧只允許在進(jìn)行插入進(jìn)行插入和刪除操作。和刪除操作。 是在是在表尾表尾進(jìn)行插入、刪除操作的線性表。進(jìn)行插入、刪除操作的線性表。表尾表尾

3、(即即 an-1 端端)稱為稱為棧頂棧頂 ; 表頭表頭(即即 a0 端端)稱為稱為棧底棧底例如：例如： 棧棧 = (a, a1 , a2 , .,an-1 )插入元素到棧頂?shù)牟僮?，稱為插入元素到棧頂?shù)牟僮鳎Q為入棧入棧。從棧頂刪除一個(gè)元素的操作，稱為從棧頂刪除一個(gè)元素的操作，稱為出棧出棧。a an-1n-1稱為棧頂元素稱為棧頂元素a a0 0稱為棧底元素稱為棧底元素插入和刪除都只能在表插入和刪除都只能在表的一端（棧頂）進(jìn)行！的一端（棧頂）進(jìn)行！后進(jìn)先出表（后進(jìn)先出表（LIFO）從輸入和輸出數(shù)據(jù)元素的位置關(guān)系看，堆棧的功能從輸入和輸出數(shù)據(jù)元素的位置關(guān)系看，堆棧的功能和一種火車調(diào)度裝置的功能類同。

4、和一種火車調(diào)度裝置的功能類同。注：堆棧可以完成比較復(fù)雜的數(shù)據(jù)元素特定序列的轉(zhuǎn)換注：堆?？梢酝瓿杀容^復(fù)雜的數(shù)據(jù)元素特定序列的轉(zhuǎn)換任務(wù)，但它不能完成任何輸入輸出序列的轉(zhuǎn)換任務(wù)。任務(wù)，但它不能完成任何輸入輸出序列的轉(zhuǎn)換任務(wù)。例例：一個(gè)棧的輸入序列為一個(gè)棧的輸入序列為1,2,3，若在，若在入棧的過程中允入棧的過程中允許出棧許出棧，則可能得到的出棧序列是什么？，則可能得到的出棧序列是什么？解：解：可以通過窮舉所有可能性來求解：可以通過窮舉所有可能性來求解： 1 1入入1 1出，出， 2 2入入2 2出，出，3 3入入3 3出，出， 即即123123； 1 1入入1 1出，出， 2 2、3 3入，入，3

5、3、2 2出，出， 即即132132； 1 1、2 2入，入，2 2出，出， 3 3入入3 3出，出， 即即231231； 1 1、2 2入，入，2 2、1 1出，出，3 3入入3 3出，出， 即即213213； 1 1、2 2、3 3入，入，3 3、2 2、1 1出，出， 即即321321；合計(jì)有合計(jì)有5 5種可能性。種可能性。例：一個(gè)棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實(shí)現(xiàn)嗎？12345的輸出呢？ 4351243512不可能實(shí)現(xiàn)，主要是其中的不可能實(shí)現(xiàn)，主要是其中的1212順序不能實(shí)現(xiàn)；順序不能實(shí)現(xiàn)； 1234512345的輸出可以實(shí)現(xiàn)，每壓入一

6、數(shù)便立即彈出即可。的輸出可以實(shí)現(xiàn)，每壓入一數(shù)便立即彈出即可。 例例設(shè)依次進(jìn)入一個(gè)棧的元素序列為設(shè)依次進(jìn)入一個(gè)棧的元素序列為c，a，b，d，則可得到則可得到出棧的元素序列是：出棧的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，bA）、）、D）可以，）可以， B）、）、C）不行。）不行。討論：有無通用的判別原則？討論：有無通用的判別原則？有！若輸入序列是有！若輸入序列是 ,P,Pj jPPk kPPi i (P(Pj jPPk kP 0); 3.1.4 鏈?zhǔn)蕉褩ｆ準(zhǔn)蕉褩ｆ準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)的堆棧稱作鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的堆棧稱作鏈?zhǔn)蕉褩ｆ準(zhǔn)蕉褩！? 鏈?zhǔn)蕉褩５拇鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)蕉褩５?/p>

7、存儲(chǔ)結(jié)構(gòu)和單鏈表相同，鏈?zhǔn)蕉褩Ｒ彩怯梢粋€(gè)個(gè)結(jié)點(diǎn)組成的，和單鏈表相同，鏈?zhǔn)蕉褩Ｒ彩怯梢粋€(gè)個(gè)結(jié)點(diǎn)組成的，每個(gè)結(jié)點(diǎn)由兩個(gè)域組成，一個(gè)是存放數(shù)據(jù)元素的數(shù)據(jù)元素每個(gè)結(jié)點(diǎn)由兩個(gè)域組成，一個(gè)是存放數(shù)據(jù)元素的數(shù)據(jù)元素域域element，另一個(gè)是存放指向下一個(gè)結(jié)點(diǎn)的對(duì)象引用（即，另一個(gè)是存放指向下一個(gè)結(jié)點(diǎn)的對(duì)象引用（即指針）域指針）域next。 以頭指針為棧頂，以頭指針為棧頂，在頭指針處在頭指針處插入或刪除插入或刪除.棧頂棧頂棧底棧底 a0 a1an-2an-1nextelementclass LinStack:Stack Node head; int size; public LinStack() head

8、= null; size = 0; 鏈?zhǔn)蕉褩ｎ惖脑O(shè)計(jì)鏈?zhǔn)蕉褩ｎ惖脑O(shè)計(jì)public void push(Object obj) head = new Node(obj, head); size+; .an-1headheadan-2a0棧頂入棧：入棧：public Object pop() if (size = 0) throw new Exception(堆棧已空！); Object obj = head.element; head = head.next; size-; return obj; .an-1headheadan-2a0出棧：出棧： public bool notEmpty()

9、return head != null; public Object getTop() return head.element; 堆棧是各種軟件系統(tǒng)中應(yīng)用最廣泛的數(shù)據(jù)結(jié)構(gòu)之一。堆棧是各種軟件系統(tǒng)中應(yīng)用最廣泛的數(shù)據(jù)結(jié)構(gòu)之一。括號(hào)匹配和表達(dá)式計(jì)算是編譯軟件中的基本問題，其括號(hào)匹配和表達(dá)式計(jì)算是編譯軟件中的基本問題，其軟件設(shè)計(jì)中都需要使用堆棧。軟件設(shè)計(jì)中都需要使用堆棧。3.2 堆棧的應(yīng)用堆棧的應(yīng)用3.2.1 括號(hào)匹配問題括號(hào)匹配問題假設(shè)一個(gè)算術(shù)表達(dá)式中包含圓括號(hào)、方括號(hào)和花括號(hào)三種類型假設(shè)一個(gè)算術(shù)表達(dá)式中包含圓括號(hào)、方括號(hào)和花括號(hào)三種類型的括號(hào)，編寫一個(gè)判別表達(dá)式中括號(hào)是否正確匹配的函數(shù)。的括號(hào)，編

10、寫一個(gè)判別表達(dá)式中括號(hào)是否正確匹配的函數(shù)。設(shè)計(jì)分析：算術(shù)表達(dá)式中右括號(hào)和左括號(hào)匹配的次序，正好符設(shè)計(jì)分析：算術(shù)表達(dá)式中右括號(hào)和左括號(hào)匹配的次序，正好符合后到的括號(hào)要最先被匹配的后進(jìn)先出的操作特點(diǎn)，因此可以合后到的括號(hào)要最先被匹配的后進(jìn)先出的操作特點(diǎn)，因此可以借助一個(gè)堆棧來進(jìn)行判斷。借助一個(gè)堆棧來進(jìn)行判斷。（12）34567順序掃描算術(shù)表達(dá)式，當(dāng)遇到三種類型的左括號(hào)時(shí)讓這些順序掃描算術(shù)表達(dá)式，當(dāng)遇到三種類型的左括號(hào)時(shí)讓這些括號(hào)進(jìn)棧；括號(hào)進(jìn)棧；當(dāng)掃描到某一種括號(hào)的右括號(hào)時(shí)，比較當(dāng)前棧頂括號(hào)是否當(dāng)掃描到某一種括號(hào)的右括號(hào)時(shí)，比較當(dāng)前棧頂括號(hào)是否與之匹配，若匹配則退棧繼續(xù)進(jìn)行判斷；與之匹配，若匹配則退

11、棧繼續(xù)進(jìn)行判斷；若當(dāng)前棧頂括號(hào)與當(dāng)前掃描的括號(hào)類型不相同，則左右括若當(dāng)前棧頂括號(hào)與當(dāng)前掃描的括號(hào)類型不相同，則左右括號(hào)配對(duì)次序不正確；號(hào)配對(duì)次序不正確；若字符串當(dāng)前為某種類型的右括號(hào)而堆棧為已空，則右括若字符串當(dāng)前為某種類型的右括號(hào)而堆棧為已空，則右括號(hào)多于左括號(hào)；號(hào)多于左括號(hào)；字符串循環(huán)掃描結(jié)束時(shí)，若堆棧非空，則說明左括號(hào)多于字符串循環(huán)掃描結(jié)束時(shí)，若堆棧非空，則說明左括號(hào)多于右括號(hào)；右括號(hào)；否則左右括號(hào)配對(duì)匹配正確。否則左右括號(hào)配對(duì)匹配正確。public static void expIsCorrect(String exp,int n) SeqStack myStack = new Seq

12、Stack();for(int i = 0; i -*/(#=12中綴表達(dá)式變換為后綴表達(dá)式的算法步驟：中綴表達(dá)式變換為后綴表達(dá)式的算法步驟：（1）設(shè)置一個(gè)堆棧，初始時(shí)將棧頂元素置為；）設(shè)置一個(gè)堆棧，初始時(shí)將棧頂元素置為；（2）順序讀入中綴表達(dá)式，當(dāng)讀到的單詞為操作數(shù)時(shí)就將其）順序讀入中綴表達(dá)式，當(dāng)讀到的單詞為操作數(shù)時(shí)就將其輸出，并接著讀下一個(gè)單詞；輸出，并接著讀下一個(gè)單詞；（3）x1為保存當(dāng)前棧頂運(yùn)算符的變量，為保存當(dāng)前棧頂運(yùn)算符的變量，x2為保存中綴表達(dá)式為保存中綴表達(dá)式中當(dāng)前讀到的運(yùn)算符的變量。中當(dāng)前讀到的運(yùn)算符的變量。若若x1的優(yōu)先級(jí)高于的優(yōu)先級(jí)高于x2的優(yōu)先級(jí)的優(yōu)先級(jí)，將將x1退棧并

13、作為后綴表達(dá)式的一個(gè)單詞輸出，然后接著比較退棧并作為后綴表達(dá)式的一個(gè)單詞輸出，然后接著比較新的棧頂運(yùn)算符新的棧頂運(yùn)算符x1與與x2的優(yōu)先級(jí)；的優(yōu)先級(jí)；若若x1的優(yōu)先級(jí)低于的優(yōu)先級(jí)低于x2的優(yōu)的優(yōu)先級(jí)先級(jí)，將，將x2的值進(jìn)棧，然后接著讀下一個(gè)單詞；的值進(jìn)棧，然后接著讀下一個(gè)單詞；若若x1的優(yōu)先的優(yōu)先級(jí)等于級(jí)等于x2的優(yōu)先級(jí)的優(yōu)先級(jí)，且，且x1為為“（” ,x2為為“）”時(shí)，將時(shí)，將“（”退棧，然后接著讀下一個(gè)單詞；退棧，然后接著讀下一個(gè)單詞；若若x1的優(yōu)先級(jí)等于的優(yōu)先級(jí)等于x2的優(yōu)先的優(yōu)先級(jí)級(jí)且且x1為為“” x2為為“”時(shí)，算法結(jié)束。時(shí)，算法結(jié)束。步驟中綴表達(dá)式堆棧后綴表達(dá)式1A+(B-C/D

14、)*E2+(B-C/D)*EA3(B-C/D)*E +A4B-C/D)*E + (A5-C/D)*E + (A B6C /D)*E + ( -A B7/D)*E + ( -A BC8D)*E + ( - / A BC中綴表達(dá)式到后綴表達(dá)式的變換過程：步驟中綴表達(dá)式堆棧后綴表達(dá)式9)*E + ( - /A BC D10)*E + ( -A BC D /11)*E + (A BC D /-12*E +A BC D /-13E + *A BC D /- 14 + *A BC D /- E15 +A BC D /- E *16A BC D /- E * + 設(shè)置一個(gè)堆棧存放操作數(shù)，從左到右依次掃描后綴表達(dá)設(shè)置一個(gè)堆棧存放操作數(shù)，從左到右依次掃描后綴表達(dá)式，式，每讀到一個(gè)操作數(shù)每讀到一個(gè)操作數(shù)就將其進(jìn)棧；就將其進(jìn)棧；每讀到一個(gè)運(yùn)算符每讀到一個(gè)運(yùn)算符就從就從棧頂取出兩個(gè)操作數(shù)施以該運(yùn)算符所代表的運(yùn)算操作，并把棧頂取出兩個(gè)操作數(shù)施以該運(yùn)算符所代表的運(yùn)算操作，并把該運(yùn)算結(jié)果作為一個(gè)新的操作數(shù)入棧；此過程一直進(jìn)行到后該運(yùn)算結(jié)果作為一個(gè)新的操作數(shù)入棧；此過程一直進(jìn)行到后綴表達(dá)式讀完，最后棧頂?shù)牟僮鲾?shù)就是該后綴表達(dá)式的運(yùn)算綴表達(dá)式讀完，最后棧頂?shù)牟僮鲾?shù)就是該后綴表達(dá)式的運(yùn)算結(jié)果。結(jié)果。求解后綴表達(dá)式的算法步驟：求解后綴表達(dá)式的算法步驟：后綴表