數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列BPPT課件

1、第1頁2. 邏輯結(jié)構(gòu) 與同線性表相同，仍為一對一關(guān)系。3. 運(yùn)算規(guī)則 只能在棧頂運(yùn)算，且訪問結(jié)點(diǎn)時依照后進(jìn)先出后進(jìn)先出 （LIFOLIFO）或先進(jìn)后出或先進(jìn)后出（FILOFILO）的原則。的原則。4.出棧順序：1. 定義 限定只能在表的一端進(jìn)行插入和刪除運(yùn)算的 線性表（只能在棧頂操作）上次課內(nèi)容回顧第1頁/共34頁第2頁討論：有無通用的判別原則？有。在可能的輸出序列中，不存在這樣的輸入序列有。在可能的輸出序列中，不存在這樣的輸入序列i i，j j，k k，能同時滿足，能同時滿足入棧入棧順序順序i i，j j，k k 和和 出棧出棧順序順序k k ，i i， j j。例例4 4 一個棧的輸入序列

2、為一個棧的輸入序列為1234512345，若在入棧的過，若在入棧的過程中允許出棧，則可能得到的出棧序列程中允許出棧，則可能得到的出棧序列有多少種，有多少種，分別是什么分別是什么？211nnCn 第2頁/共34頁第3頁例1：回文游戲 設(shè)計思路：用棧暫存回文例2：數(shù)制轉(zhuǎn)換（十轉(zhuǎn)N） 設(shè)計思路：用棧暫存低位值例3 ：括號匹配的檢驗(yàn) 設(shè)計思路：用棧暫存左括號例4：表達(dá)式求值 設(shè)計思路：用棧暫存運(yùn)算符 簡化程序設(shè)計問題簡化程序設(shè)計問題第3頁/共34頁第4頁v回文游戲：順讀與逆讀字符串一樣（不含空格）dadtop1.讀入字符串2.壓入棧3.原串字符與出棧字符依次比較 若不等，非回文 若直到?？斩枷嗟?，則是

3、回文有沒有更簡潔的辦法呢？(讀入字符串，壓入n/2個字符,n為字符個數(shù))v多進(jìn)制輸出：字符串：“madam I madam”“上海自來水來自海上”例 把十進(jìn)制數(shù)159轉(zhuǎn)換成八進(jìn)制數(shù)(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top732第4頁/共34頁第5頁v多進(jìn)制輸出：例 把十進(jìn)制數(shù)159轉(zhuǎn)換成八進(jìn)制數(shù)(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top732public class Test public static void main(String args) int i=

4、159; String binStr=Integer.toBinaryString(i); String otcStr=Integer.toOctalString(i); String hexStr=Integer.toHexString(i); System.out.println(binStr); 第5頁/共34頁第6頁v多進(jìn)制輸出：import java.util.*;class T public static void main(String args) System.out.println(toOctal(159); public static String toOctal(int

5、a) String str = ; Stack s = new Stack(); while(a!=0) s.push(a%8); a=a/8; while(!s.empty() str += s.pop(); return str; 例 把十進(jìn)制數(shù)159轉(zhuǎn)換成八進(jìn)制數(shù)第6頁/共34頁第7頁例如：3*（7 2 ） (1) 要正確求值，首先了解算術(shù)四則運(yùn)算的規(guī)則： a. 從左算到右 b. 先乘除，后加減 c. 先括號內(nèi)，后括號外 由此，通常此表達(dá)式的計算順序?yàn)椋?3*（7 2 ）= 3 * 5 = 15v 表達(dá)式求值( 這是棧應(yīng)用的典型例子 ) 這里，這里，表達(dá)式求值的算法是表達(dá)式求值的算法是

6、“算符優(yōu)先法算符優(yōu)先法”。第7頁/共34頁第8頁表達(dá)式表示法 算術(shù)表達(dá)式中最常見的表示法形式有 中綴、前綴和 后綴表示法。中綴表示法是書寫表達(dá)式的常見方式，而前綴和后綴表示法主要用于計算機(jī)科學(xué)領(lǐng)域。中綴表示法 Syntax: operand1 operator operand2Example: (A+B)*C-D/(E+F)前綴表示法 -波蘭表示法（Polish notation，PN）Syntax : operator operand1 operand2Example : -*+ABC/D+EF后綴表示法 -逆波蘭表示法（Reverse Polish Notation，RPN）Syntax

7、: operand1 operand2 operatorExample : AB+C*DEF+/- 無操作符優(yōu)先級問題，求值簡單第8頁/共34頁第9頁1. 中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換 要把表達(dá)式從中綴表達(dá)式的形式轉(zhuǎn)換成用后綴表示法表示的等價表達(dá)式，必須了解操作符的優(yōu)先級和結(jié)合性。 優(yōu)先級或者說操作符的強(qiáng)度決定求值順序；優(yōu)先級高的操作符比優(yōu)先級低的操作符先求值。 如果所有操作符優(yōu)先級一樣，那么求值順序就取決于它們的 結(jié)合性。操作符的結(jié)合性定義了相同優(yōu)先級操作符組合的順序（從右至左或從左至右）。 Left associativity : A+B+C = (A+B)+CRight associat

8、ivity : ABC = A(BC) 常用表達(dá)式求值方法1. 中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式2. 計算后綴表達(dá)式第9頁/共34頁第10頁轉(zhuǎn)換算法：1. 讀入運(yùn)算對象（數(shù)據(jù)），直接輸出2. 遇到( 運(yùn)算符進(jìn)棧3. 遇到) 運(yùn)算符，則棧內(nèi)的最上一個( 以上的所有運(yùn)算符退棧，(也退棧4. 讀入運(yùn)算符，進(jìn)入運(yùn)算棧 4.1 后進(jìn)棧的運(yùn)算符 先進(jìn)棧的運(yùn)算符，運(yùn)算符進(jìn)棧 (優(yōu)先級比較) 4.2 后進(jìn)棧的運(yùn)算符 = 先進(jìn)棧的運(yùn)算符，將棧內(nèi)的運(yùn)算符退棧輸出，再進(jìn)棧第10頁/共34頁第11頁31*(5-22)+70第11頁/共34頁第12頁后綴表達(dá)式求值 對后綴表達(dá)式求值比直接對中綴表達(dá)式求值簡單。在后綴表達(dá)式中，

9、不需要括號，而且操作符的優(yōu)先級也不再起作用了?？梢杂萌缦滤惴▽缶Y表達(dá)式求值： 初始化一個空堆棧 從左到右讀入后綴表達(dá)式 如果字符是一個操作數(shù)，把它壓入堆棧。 如果字符是個操作符，彈出兩個操作數(shù)，執(zhí)行操作，然后把結(jié)果壓入堆棧。 到后綴表達(dá)式末尾，從堆棧中彈出結(jié)果。若后綴表達(dá)式格式正確，那么堆棧應(yīng)該為空。第12頁/共34頁第13頁31*(5-22)+70參看Class1.java代碼第13頁/共34頁第14頁1. 順序棧的一般定義/堆棧接口public interface Stack public int getSize(); public boolean isEmpty(); public v

10、oid push(Object e); public Object pop() throws StackEmptyException; public Object peek() throws StackEmptyException;二. 基本操作的程序?qū)崿F(xiàn)第14頁/共34頁第15頁1. 順序棧的一般定義public class StackArray implements Stack private final int LEN=8; / private Object elements; / private int top; public StackArray() top=-1; elements

11、=new ObjectLEN; public int getSize() return top+1; public boolean isEmpty() return top =elements.length) expandSpace(); elements+top =e; 二. 基本操作的程序?qū)崿F(xiàn)第15頁/共34頁第16頁 private void expandSpace() Object a=new Objectelements.length*2; for(int i=0; ielements.length; i+) ai=elementsi; elements=a; public Obje

12、ct pop() throws StackEmptyException if(getSize() 1) throw new StackEmptyException(“錯誤，堆?？铡?; Object obj= elementstop; elementstop- =null; return obj; public Object peek() throws StackEmptyException if(getSize() 1) throw new StackEmptyException(“錯誤，堆?？铡?; return elementstop; 第16頁/共34頁第17頁l入棧算法l 出棧算法

13、.棧底toptopxptop .棧底topq鏈?；静僮鱌67 Stack的鏈?zhǔn)酱鎯?shí)現(xiàn)初始化、判斷?？?、棧滿、入棧、出棧、取棧頂元素、銷毀。SLNode p= new SLNode(x,top); top= p; size+;棧非空，則Object obj= top.getData() ; top= top.getNext() ; size-;第17頁/共34頁第18頁補(bǔ)充1：若入棧動作使地址向高端增長，稱為“向上生成”的棧；若入棧動作使地址向低端增長，稱為“向下生成”的棧；top=0123450棧空 對于向上生成的棧對于向上生成的棧入棧入?？谠E：堆棧指針口訣：堆棧指針top先壓后加先壓后加

14、（vtop+=xvtop+=x）；）；出棧出?？谠E：堆棧指針口訣：堆棧指針top先減后彈先減后彈（y=v-topy=v-top) ) 。 對于向下生成的棧對于向下生成的棧若約定若約定top指向棧頂元素的后一個位置指向棧頂元素的后一個位置入棧入棧口訣：堆棧指針口訣：堆棧指針top先壓后減先壓后減（vvtoptop-=x=x）；）；出棧出?？谠E：堆棧指針口訣：堆棧指針top先加后彈先加后彈（y=vy=v+toptop) 。top=6123450棧空第18頁/共34頁第19頁第三章 棧和隊(duì)列3.2 隊(duì)（Queue） 1. 隊(duì)的基本理論 定義、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、基本運(yùn)算規(guī)則、隊(duì)的應(yīng)用2. 基本操作的

15、程序?qū)崿F(xiàn)方法第19頁/共34頁第20頁 3.2 隊(duì)列 隊(duì)列的定義及特點(diǎn) 定義：隊(duì)列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表 隊(duì)尾(rear)允許插入的一端 隊(duì)頭(front)允許刪除的一端 隊(duì)列特點(diǎn)：先進(jìn)先出(FIFO)a1 a2 a3.an 入隊(duì)出隊(duì)隊(duì)頭front隊(duì)尾rear隊(duì)列Q=(a1,a2,an)第20頁/共34頁第21頁ADT Queue 數(shù)據(jù)對象數(shù)據(jù)對象：D=ai|aiElemSet, i=1,2,n,n0 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：R1=| ai-1,ai D,i=2,n 基本操作基本操作： getSize(); /返回隊(duì)列大小，即元素個數(shù) isEmpty() ; /對

16、為空返回true,否則返回false enqueue(e); /數(shù)據(jù)元素e入對 dequeue(); /對頭元素出對 peek(); /獲取對頭元素，但不出對/ADT Queue隊(duì)的抽象數(shù)據(jù)類型定義第21頁/共34頁第22頁 隊(duì)列的順序存儲結(jié)構(gòu) 實(shí)現(xiàn)：用一維數(shù)組實(shí)現(xiàn)sqMfront=-1rear=-1123450隊(duì)空123450frontJ1,J1,J3入隊(duì)J1J2J3rearrear123450J4,J5,J6入隊(duì)J4J5J6front設(shè)兩個指針front,rear,約定：rear指示隊(duì)尾元素；front指示隊(duì)頭元素前一位置初值front=rear=-1 空隊(duì)列條件：front=rear入隊(duì)

17、列：sq+rear=x;出隊(duì)列：x=sq+front;rearrearfrontrear123450J1,J2,J3出隊(duì)J1J2J3frontfrontfront隊(duì)列會滿嗎？這樣操作有沒有問題？第22頁/共34頁第23頁 存在問題設(shè)數(shù)組容量為M，則： 當(dāng)front=-1,rear=M-1時，再有元素入隊(duì)發(fā)生溢出真溢出 當(dāng)front-1,rear=M-1時，再有元素入隊(duì)發(fā)生溢出假溢出0M-11frontrear.v解決方案l隊(duì)首固定，每次出隊(duì)剩余元素向下移動浪費(fèi)時間l循環(huán)隊(duì)列u基本思想：把隊(duì)列設(shè)想成環(huán)形，讓sq0接在sqM-1之后，若rear+1=M,則令rear=0; 在順序隊(duì)中，當(dāng)尾指針已經(jīng)

18、到了數(shù)組的上界，不能再有入隊(duì)操作，在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫但其實(shí)數(shù)組中還有空位置，這就叫“假溢出假溢出”。u實(shí)現(xiàn)：利用“求?！边\(yùn)算u入隊(duì)： rear=(rear+1)%M; sqrear=x;u出隊(duì)： front=(front+1)%M; x=sqfront;u隊(duì)滿、隊(duì)空判定條件？第23頁/共34頁第24頁012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始狀態(tài)J4,J5,J6出隊(duì)J7,J8,J9入隊(duì)隊(duì)空：front=rear隊(duì)滿：front=rear真

19、溢出假溢出第24頁/共34頁第25頁解決方案有三： 加設(shè)標(biāo)志位，讓刪除動作使其為1,插入動作使其為0,則可識別當(dāng)前front=rear人為浪費(fèi)一個單元，令隊(duì)滿特征為隊(duì)滿特征為front=(rear+1)%N；使用一個計數(shù)器記錄隊(duì)列中元素個數(shù)（即隊(duì)列長度）； 選用空閑單元法：空閑單元法：即即front和和rear之一指向?qū)嵲?，另一指向之一指向?qū)嵲兀硪恢赶蚩臻e元素?？臻e元素。 隊(duì)空條件 : front = rear (初始化時：front = rear )隊(duì)滿條件：front = (rear+1) % N (N=maxsize)隊(duì)列長度：L=（Nrearfront）% N rearJ2 J3

20、J1 J4 J5front問2： 在具有n個單元的循環(huán)隊(duì)列中，隊(duì)滿時共有多少個元素？問1：左圖中隊(duì)列長度L=？ 左圖中隊(duì)列容量maxsize N=？n -156第25頁/共34頁第26頁J2 J3J1 J4 J5rearfrontfrontfrontfrontJ6 J5J7J8 J9例1： 一循環(huán)隊(duì)列如下圖所示，若先刪除4個元素，接著再插入4個元素，請問隊(duì)頭和隊(duì)尾指針分別指向哪個位置? front解：由圖可知，隊(duì)頭和隊(duì)尾指針的初態(tài)分別為front=1和rear=6。frontrear刪除4個元素后front=5；再插入4個元素后，r=(6+4)%6=4 frontu入隊(duì)： rear=(rear

21、+1)%M; u出隊(duì)： front=(front+1)%M; 第26頁/共34頁第27頁例2 ：數(shù)組數(shù)組nn用來表示一個循環(huán)隊(duì)列，用來表示一個循環(huán)隊(duì)列，f f 為當(dāng)前為當(dāng)前隊(duì)列頭元素的隊(duì)列頭元素的前一前一位置，位置，r r 為隊(duì)尾元素的位置。假定為隊(duì)尾元素的位置。假定隊(duì)列中元素的個數(shù)小于隊(duì)列中元素的個數(shù)小于n n，計算隊(duì)列中元素的公式為，計算隊(duì)列中元素的公式為: :（） rf （）（nfr）% n （） nrf （） （nrf）% n4種公式哪種合理？當(dāng) r f 時（A）合理；當(dāng) r f 時（C）合理；分析 ：綜合2種情況，以（D）的表達(dá)最為合理例3：在一個循環(huán)隊(duì)列中，若約定隊(duì)首指針指向隊(duì)首元

22、素的前一個位置。那么，從循環(huán)隊(duì)列中刪除一個元素時，其操作是 先 ，后 。 移動隊(duì)首指針取出元素rear123450J4,J5,J6入隊(duì)J4J5J6front第27頁/共34頁第28頁基本運(yùn)算如下： 置空隊(duì) 分配空間，頭尾指針賦值，計數(shù)賦0 入隊(duì) 順序表插入，調(diào)整頭尾指針 計數(shù)賦 出隊(duì) 順序表刪除，調(diào)整頭尾指針 計數(shù)賦 判隊(duì)空 隊(duì)列中數(shù)據(jù)數(shù)目為0。 使用計數(shù)器的循環(huán)隊(duì)列的類型定義：Java實(shí)現(xiàn)使用計數(shù)器的循環(huán)隊(duì)列.txt第28頁/共34頁第29頁結(jié)點(diǎn)接口Public interface Nodepublic Object getData( );/獲取結(jié)點(diǎn)數(shù)據(jù)域Public void setData(Object object);/設(shè)置結(jié)點(diǎn)數(shù)據(jù)域Public class SLNode implements Node private Object element; private SLNode next; public SLNode this(null,null); public SLNode(Object ele, SLnode next) this.element=ele; this.next=next; public SLNode getNext( )