數(shù)據(jù)結(jié)構(gòu)003-棧和隊列

1、1 1 棧棧1.11.21.31.4、 棧的應(yīng)用棧的應(yīng)用 2 隊列隊列2.3、2.4、2.5、2.6、2 通常稱，棧和隊列是限定插入和刪除只能在表的“端點(diǎn)”進(jìn)行的線性表。 棧和隊列是兩種操作受限的線性表，是兩種常用的數(shù)據(jù)類型。 線性表線性表 棧棧 隊列隊列 Insert(i, x) Insert(n, x) Insert(n, x) 0in Delete(i) Delete(n-1) Delete(0) 0in-13線性表線性表可以對輸入序列求逆可以對輸入序列求逆出棧出棧Pop入棧入棧Pushtopbottoma0an-2an-14【思考題思考題】：設(shè)有編號為1，2，3，4的四輛列車，順序進(jìn)一

2、個棧式結(jié)構(gòu)的站臺，具體寫出這四輛列車開出車站的所有可能的順序。1. 1、2、3、4； 2. 1、2、4、3；3. 1、3、2、4； 4. 1、3、4、2；5. 1、4、3、2；6. 2、1、3、4；7. 2、1、4、3； 8. 2、3、4、1；9. 2、3、1、4 ； 10. 2、4、3、1；11. 3、2、1、4； 12. 3、2、4、1；13. 3、4、2、1； 14. 4、3、2、1。 5ADT Stack Data: . Operator: 棧初始化 入棧Pushpush( T x ); 出棧Poppop( ); 判斷棧是否空IsEmptyIsEmpty( ); 讀取棧頂元素peekp

3、eek ( ); 置空棧clearclear( ); 判斷棧是否滿IsFullIsFull( );6/棧接口，描述棧抽象數(shù)據(jù)類型棧接口，描述棧抽象數(shù)據(jù)類型public interface IStackpublic void clear();public boolean isEmpty();public int length();public Object peek();public void push(Object x) throws Exception;public Object pop();實現(xiàn)此接口的方法有兩種實現(xiàn)此接口的方法有兩種: 順序棧順序棧鏈棧鏈棧7DATA：object sta

4、ckElem ; /棧元素數(shù)組棧元素數(shù)組int top; /棧頂棧頂 (int curLen)int maxSize; /棧最大容量棧最大容量 (int stackElem.length)topstackElem0 1 2 3 4 5 6 7 8 9 maxSize-1bottom入棧入棧：stackElemtop+= x出棧：出棧：return stackElem-top 棧空：?？眨簍op= 0 棧滿：棧滿：top=maxSize入棧？入棧？ 出棧？出棧？?？眨織？?？棧滿？棧滿？棧的長度？棧的長度？棧頂元素？棧頂元素？8public class SqStack implements ISt

5、ack private Object stackElem; / 棧棧存儲空間存儲空間 private int top; / 非空棧中始終表示棧頂元素的下一個位置，當(dāng)棧為空時其值為非空棧中始終表示棧頂元素的下一個位置，當(dāng)棧為空時其值為0 public SqStack(int maxSize) / 構(gòu)造一個存儲空間容量為maxSize的棧 top = 0; / 初始化top為0 stackElem = new ObjectmaxSize;/ 為棧分配為棧分配maxSize個存儲單元個存儲單元 public void clear() top = 0; / 將一個已經(jīng)存在的棧置成空 public bo

6、olean isEmpty() return top = 0; / 測試棧是否為空 public int length() return top; / 求棧中的數(shù)據(jù)元素個數(shù)并由函數(shù)返回其值 public Object peek() / 查看棧頂對象而不移除它，返回棧頂對象 if (!isEmpty() return stackElemtop - 1; / 若棧不空，返回棧若棧不空，返回棧頂元素頂元素 else return null; / 若棧為空，返回 null 9/ 移除棧頂對象并作為此函數(shù)的值返回該對象 public Object pop() if (top = 0) return nu

7、ll;/ 棧為棧為空，返回空，返回null else return stackElem-top; / 棧非空棧非空, 修改棧頂指針，并返回棧頂元素修改棧頂指針，并返回棧頂元素 / 把項壓入棧頂 public void push(Object o) throws Exception if (top = stackElem.length) throw new Exception(“棧棧已已滿滿”); /棧滿，輸出棧滿，輸出異常異常 else stackElemtop+ = o; / 棧未滿，o賦給棧頂元素后，top增110/棧頂指針相遇棧頂指針相遇/棧頂指針退到棧底棧頂指針退到棧底b0 t0 t1

8、 b10 maxSize-1Vtopbottombottomtop11n不設(shè)頭結(jié)點(diǎn)不設(shè)頭結(jié)點(diǎn)；n第一個結(jié)點(diǎn)即為棧頂。第一個結(jié)點(diǎn)即為棧頂。n鏈?zhǔn)綏o棧滿問題，空間可擴(kuò)充；鏈?zhǔn)綏o棧滿問題，空間可擴(kuò)充；n插入插入（入棧）（入棧）與刪除與刪除（出棧）只能（出棧）只能在棧頂處執(zhí)行；在棧頂處執(zhí)行；n鏈?zhǔn)綏５臈ｍ斣阪滎^；鏈?zhǔn)綏５臈ｍ斣阪滎^；top棧底元素棧底元素當(dāng) top = NULL 時，表示空棧棧頂元素棧頂元素datanext12鏈?zhǔn)綏５娜霔：统鰲ｆ準(zhǔn)綏５娜霔：统鰲ublic class LinkStack implements IStack private Node top; 13public c

9、lass LinkStack implements IStack private Node top; / 棧頂元素的引用棧頂元素的引用 public void clear() top = null; / 將一個已經(jīng)存在的棧置成空 public boolean isEmpty() return top = null; / 測試棧是否為空 public int length() / 求棧中的數(shù)據(jù)元素個數(shù)并由函數(shù)返回其值 Node p = top; / 初始化,p指向棧頂結(jié)點(diǎn),length為計數(shù)器 int length = 0; while (p != null) p = p.getNext();

10、+length; return length; public Object peek() / 查看棧頂對象而不移除它，返回棧頂對象 if (!isEmpty() return top.getData();/ 返回棧頂元素返回棧頂元素 else return null; 。14public Object pop() / 移除棧頂對象并作為此函數(shù)的值返回該對象 if (!isEmpty() Node p = top;/ p指向棧頂結(jié)點(diǎn) top = top.getNext(); return p.getData(); else return null;public void push(Object

11、x) / 把項壓入棧頂 Node p = new Node(x); / 構(gòu)造一個新的結(jié)點(diǎn)構(gòu)造一個新的結(jié)點(diǎn) p.setNext(top); top = p;/ 改變棧頂結(jié)點(diǎn)。15 棧是嵌套調(diào)用機(jī)制的實現(xiàn)基礎(chǔ) 使用棧以非遞歸方式實現(xiàn)遞歸算法 16 【例例】將一個十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)將一個十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)如：18 18/2=9 + 0 9/2=4 + 1 4/2=2 + 0 2/2=1 + 0 18 10010 100000 ？001017【例例】：判斷表達(dá)式中圓括號是否匹配：判斷表達(dá)式中圓括號是否匹配18例例2：使用棧計算表達(dá)式的值：使用棧計算表達(dá)式的值中綴表達(dá)式1+2*(3-4)+519

12、（1）將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式）將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式1. 設(shè)立一個運(yùn)算符棧運(yùn)算符棧；2. 若若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式;3. 若若當(dāng)前字符為當(dāng)前字符為運(yùn)算符運(yùn)算符時，若運(yùn)算符棧為空或運(yùn)算符棧非空且時，若運(yùn)算符棧為空或運(yùn)算符棧非空且該運(yùn)算符優(yōu)先級該運(yùn)算符優(yōu)先級高于高于棧頂運(yùn)算符，則棧頂運(yùn)算符，則進(jìn)棧；進(jìn)棧；否則，否則，退出棧頂退出棧頂運(yùn)算符發(fā)送給后綴式；運(yùn)算符發(fā)送給后綴式；4. 若當(dāng)前字符是左括號“（”時，將其壓進(jìn)運(yùn)算符棧;5. 若當(dāng)前字符是右括號“）”時，反復(fù)將棧頂符號彈出反復(fù)將棧頂符號彈出，并送往后綴表達(dá)式，直到棧頂符號是左括號為止

13、，再將左括號出棧并丟棄。6. 若讀取完畢，則將棧中剩余的所有運(yùn)算符彈出并送往后綴表達(dá)式。2021（2）后綴表達(dá)式求值）后綴表達(dá)式求值 1) 設(shè)立一個操作數(shù)棧； 2) 從左到右依次讀入后綴表達(dá)式中的字符:若當(dāng)前字符是操作數(shù)，則壓入操作數(shù)棧。若當(dāng)前字符是運(yùn)算符，則從棧頂彈出兩個操作數(shù)參與運(yùn)算，并將運(yùn)算結(jié)果壓入操作數(shù)棧內(nèi)。2223 1 棧棧1.11.21.31.4、 棧的應(yīng)用棧的應(yīng)用 2 隊列隊列2.3、2.4、2.5、2.6、24定義：刪除操作只能在一端（隊首）進(jìn)行，而插入操作只能定義：刪除操作只能在一端（隊首）進(jìn)行，而插入操作只能在另一端（隊尾）進(jìn)行的線性表。在另一端（隊尾）進(jìn)行的線性表。概念：

14、隊首（概念：隊首（frontfront）、隊尾（）、隊尾（rearrear）、出列、入列）、出列、入列特點(diǎn)：按先進(jìn)先出（特點(diǎn)：按先進(jìn)先出（FIFOFIFO）的原則進(jìn)行操作。）的原則進(jìn)行操作。a0a1 an-2an-1與棧類似，隊列的封閉性非常好與棧類似，隊列的封閉性非常好棧能對輸入序列部分或全局起求逆作用，而隊列對輸棧能對輸入序列部分或全局起求逆作用，而隊列對輸入序列起緩沖作用，隊列的應(yīng)用非常廣泛入序列起緩沖作用，隊列的應(yīng)用非常廣泛出列出列入列入列隊首（隊首（front）隊隊尾尾 rear。25public interface IQueue /隊列隊列java接口描述接口描述 public v

15、oid clear(); /隊列直空隊列直空public boolean isEmpty(); /隊列判空隊列判空public int length(); /求隊列長度求隊列長度public Object peek();/取隊首元素取隊首元素public void offer(Object x) throws Exception;/入列（入隊）入列（入隊）public Object poll(); /出列（出隊）出列（出隊） 。實現(xiàn)此接口的方法有兩種實現(xiàn)此接口的方法有兩種: 順序隊列順序隊列鏈?zhǔn)疥犃墟準(zhǔn)疥犃?6front=rear空隊列front rearA A入列入列Afront rearB

16、入列入列A Bfront rearC, D入列入列A B C Dfront rearA出列出列B C Dfront rearB出列出列C Dfront rearE,F,G入列入列C D E F GC D E F Gfront rearH入列入列,溢出溢出。queueElem隊首元素？隊尾元素？隊空條件？隊滿條件？入隊操作？出隊操作？27 隊首元素？queueElemfront 隊尾元素？queueElemrear-1 隊空條件？ front=rear 隊滿條件？ rear=queueElem.length 入隊操作？ queueElemrear+=x; 出隊操作？ return queueEl

17、em front+;282901234567frontrear空隊列空隊列隊列初始化：隊列初始化：front = rear = 0;隊空條件：隊空條件：front = rear;隊滿條件：隊滿條件：(rear+1) % maxSize = frontmaxSize8。front = rear; 區(qū)分隊空或隊滿？區(qū)分隊空或隊滿？ 三種方法：少用一個元素空間、標(biāo)志變量、計數(shù)變量（參見教材）三種方法：少用一個元素空間、標(biāo)志變量、計數(shù)變量（參見教材）3001234567frontrearA入列入列隊列初始化：隊列初始化：front = rear = 0;隊空條件：隊空條件：front = rear;隊

18、滿條件：隊滿條件：(rear+1) % maxSize = frontAmaxSize8rear3101234567frontrearB B、C C入列入列隊列初始化：隊列初始化：front = rear = 0;隊空條件：隊空條件：front = rear;隊滿條件：隊滿條件：(rear+1) % maxSize = frontABmaxSize8Crearrear3201234567frontrearA A、B B出列出列隊列初始化：隊列初始化：front = rear = 0;隊空條件：隊空條件：front = rear;隊滿條件：隊滿條件：(rear+1) % maxSize = fr

19、ontABmaxSize8Cfrontfront3301234567rearD、E、F、G、H、I 入列入列隊列初始化：隊列初始化：front = rear = 0;隊空條件：隊空條件：front = rear;隊滿條件：隊滿條件：(rear+1) % maxSize = frontmaxSize8CfrontDEFG HIrear34front=(front+1) % length;rear=(rear+1) % length;35循環(huán)隊列的類定義循環(huán)隊列的類定義public class CircleSqQueue implements IQueue private Object queue

20、Elem; / 隊列存儲空間隊列存儲空間 private int front;/ 隊頭的引用，若隊列不空，指向隊列頭元素隊頭的引用，若隊列不空，指向隊列頭元素 private int rear;/ 隊尾的引用，若隊列不空，指向隊列尾元素的下一個位置隊尾的引用，若隊列不空，指向隊列尾元素的下一個位置 public CircleSqQueue(int maxSize) / 循環(huán)隊列類的構(gòu)造函數(shù) front = rear = 0;/ 隊頭、隊尾初始化為0 queueElem = new ObjectmaxSize; /為隊列分配為隊列分配maxSize個存儲單元個存儲單元 public void c

21、lear() front = rear = 0; / 將隊列置空 public boolean isEmpty() return front = rear; / 隊列判空 public int length() / 求隊列中的數(shù)據(jù)元素個數(shù)并由函數(shù)返回其值 return (rear - front + queueElem.length) % queueElem.length; public Object peek() / 查看隊列頭但不移除它，隊列空則返回 null if (front = rear) return null; / 隊列為空，返回隊列為空，返回null else return q

22、ueueElemfront; / 返回隊列頭返回隊列頭元素元素 36/ 把指定的元素插入隊列public void offer(Object o) throws Exception if (rear + 1) % queueElem.length = front) / 隊列滿隊列滿 throw new Exception(隊列已滿隊列已滿);/ 輸出異常輸出異常 else / 隊列未滿隊列未滿 queueElemrear = o; / rear加1后，o賦給棧頂元素 rear = (rear + 1) % queueElem.length; / 修改隊尾指針 / 移除隊列的頭并作為此函數(shù)的值返

23、回該對象，如果此隊列為空，則返回 nullpublic Object poll() if (front = rear) return null; / 隊列為空隊列為空 else Object t = queueElemfront;/ 取出隊列頭元素 front = (front + 1) % queueElem.length;/ 更改隊頭位置 return t;/ 返回隊列頭元素返回隊列頭元素 。37n鏈?zhǔn)疥犃信c單鏈表相似，但鏈?zhǔn)疥犃信c單鏈表相似，但不設(shè)頭結(jié)點(diǎn)不設(shè)頭結(jié)點(diǎn)；n第一個結(jié)點(diǎn)即為隊首，最后一個結(jié)點(diǎn)為隊尾。第一個結(jié)點(diǎn)即為隊首，最后一個結(jié)點(diǎn)為隊尾。n插入（入列）操作只能在隊尾進(jìn)行，刪除（出

24、列）操作只插入（入列）操作只能在隊尾進(jìn)行，刪除（出列）操作只能在隊首進(jìn)行。能在隊首進(jìn)行。front當(dāng) front = NULL 時，表示空隊列reardatanext隊首元素隊首元素隊尾元素隊尾元素。38public class LinkQueue implements IQueue /鏈?zhǔn)疥犃蓄愭準(zhǔn)疥犃蓄?private Node front, rear; 39public class LinkQueue implements IQueue private Node front;/ 隊頭的引用隊頭的引用 private Node rear;/ 隊尾的引用，指向隊尾元素隊尾的引用，指向隊尾元素

25、 public LinkQueue() front = rear = null; / 鏈隊列類的構(gòu)造函數(shù) public void clear() front = rear = null; / 隊列置空 public boolean isEmpty() return front = null; / 隊列判空 public int length() / 求隊列中的數(shù)據(jù)元素個數(shù)并由函數(shù)返回其值 Node p = front; int length = 0;/ 隊列的長度隊列的長度 while (p != null) p = p.getNext(); +length; return length; public Object peek() / 返回隊列頂對象，隊列為空，則返回 null if (front != null) return front.getData();/ 返回隊列元素返回隊列元素 e