1、第第3章章 堆棧和隊列堆棧和隊列 3.1 堆棧堆棧3.2 堆棧的應用堆棧的應用3.3 隊列隊列3.4 優先級隊列優先級隊列本章主要知識點：本章主要知識點： 堆棧的基本概念，堆棧的用途堆棧的基本概念，堆棧的用途 順序堆棧類的設計方法，鏈式堆棧類的設計方法順序堆棧類的設計方法，鏈式堆棧類的設計方法 隊列的基本概念，隊列的用途隊列的基本概念，隊列的用途 順序循環隊列的基本實現原理，順序循環隊列的隊空順序循環隊列的基本實現原理，順序循環隊列的隊空和隊滿判斷方法，順序循環隊列類的設計方法和隊滿判斷方法，順序循環隊列類的設計方法 鏈式堆棧類的設計方法鏈式堆棧類的設計方法 優先級隊列的概念，優先級隊列的用途

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

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

4、和一種火車調度裝置的功能類同。注：堆?？梢酝瓿杀容^復雜的數據元素特定序列的轉換注：堆?？梢酝瓿杀容^復雜的數據元素特定序列的轉換任務，但它不能完成任何輸入輸出序列的轉換任務。任務，但它不能完成任何輸入輸出序列的轉換任務。例例：一個棧的輸入序列為一個棧的輸入序列為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；合計有合計有5 5種可能性。種可能性。例：一個棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實現嗎？12345的輸出呢？ 4351243512不可能實現，主要是其中的不可能實現，主要是其中的1212順序不能實現；順序不能實現； 1234512345的輸出可以實現，每壓入一

6、數便立即彈出即可。的輸出可以實現，每壓入一數便立即彈出即可。 例例設依次進入一個棧的元素序列為設依次進入一個棧的元素序列為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 鏈式堆棧鏈式堆棧鏈式存儲結構的堆棧稱作鏈式存儲結構的堆棧稱作鏈式堆棧鏈式堆棧。1 鏈式堆棧的存儲結構鏈式堆棧的

7、存儲結構和單鏈表相同，鏈式堆棧也是由一個個結點組成的，和單鏈表相同，鏈式堆棧也是由一個個結點組成的，每個結點由兩個域組成，一個是存放數據元素的數據元素每個結點由兩個域組成，一個是存放數據元素的數據元素域域element，另一個是存放指向下一個結點的對象引用（即，另一個是存放指向下一個結點的對象引用（即指針）域指針）域next。 以頭指針為棧頂，以頭指針為棧頂，在頭指針處在頭指針處插入或刪除插入或刪除.棧頂棧頂棧底棧底 a0 a1an-2an-1nextelementclass LinStack:Stack Node head; int size; public LinStack() head

8、= null; size = 0; 鏈式堆棧類的設計鏈式堆棧類的設計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; 堆棧是各種軟件系統中應用最廣泛的數據結構之一。堆棧是各種軟件系統中應用最廣泛的數據結構之一。括號匹配和表達式計算是編譯軟件中的基本問題，其括號匹配和表達式計算是編譯軟件中的基本問題，其軟件設計中都需要使用堆棧。軟件設計中都需要使用堆棧。3.2 堆棧的應用堆棧的應用3.2.1 括號匹配問題括號匹配問題假設一個算術表達式中包含圓括號、方括號和花括號三種類型假設一個算術表達式中包含圓括號、方括號和花括號三種類型的括號，編寫一個判別表達式中括號是否正確匹配的函數。的括號，編

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

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

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

13、作為后綴表達式的一個單詞輸出，然后接著比較退棧并作為后綴表達式的一個單詞輸出，然后接著比較新的棧頂運算符新的棧頂運算符x1與與x2的優先級；的優先級；若若x1的優先級低于的優先級低于x2的優的優先級先級，將，將x2的值進棧，然后接著讀下一個單詞；的值進棧，然后接著讀下一個單詞；若若x1的優先的優先級等于級等于x2的優先級的優先級，且，且x1為為“（” ,x2為為“）”時，將時，將“（”退棧，然后接著讀下一個單詞；退棧，然后接著讀下一個單詞；若若x1的優先級等于的優先級等于x2的優先的優先級級且且x1為為“” x2為為“”時，算法結束。時，算法結束。步驟中綴表達式堆棧后綴表達式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中綴表達式到后綴表達式的變換過程：步驟中綴表達式堆棧后綴表達式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 * + 設置一個堆棧存放操作數，從左到右依次掃描后綴表達設置一個堆棧存放操作數，從左到右依次掃描后綴表達式，式，每讀到一個操作數每讀到一個操作數就將其進棧；就將其進棧；每讀到一個運算符每讀到一個運算符就從就從棧頂取出兩個操作數施以該運算符所代表的運算操作，并把棧頂取出兩個操作數施以該運算符所代表的運算操作，并把該運算結果作為一個新的操作數入棧；此過程一直進行到后該運算結果作為一個新的操作數入棧；此過程一直進行到后綴表達式讀完，最后棧頂的操作數就是該后綴表達式的運算綴表達式讀完，最后棧頂的操作數就是該后綴表達式的運算結果。結果。求解后綴表達式的算法步驟：求解后綴表達式的算法步驟：后綴表