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

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

2、個(gè)棧式結(jié)構(gòu)的站臺(tái)，具體寫出這四輛列車開(kāi)出車站的所有可能的順序。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();實(shí)現(xiàn)此接口的方法有兩種實(shí)現(xiàn)此接口的方法有兩種: 順序棧順序棧鏈棧鏈棧7DATA：object sta

4、ckElem ; /棧元素?cái)?shù)組棧元素?cái)?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入棧？入棧？ 出棧？出棧？?？?？?？?？棧滿？棧滿？棧的長(zhǎng)度？棧的長(zhǎng)度？棧頂元素？棧頂元素？8public class SqStack implements ISt

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

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

7、ll;/ 棧為棧為空，返回空，返回null else return stackElem-top; / 棧非空棧非空, 修改棧頂指針，并返回棧頂元素修改棧頂指針，并返回棧頂元素 / 把項(xiàng)壓入棧頂 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第一個(gè)結(jié)點(diǎn)即為棧頂。第一個(gè)結(jié)點(diǎn)即為棧頂。n鏈?zhǔn)綏o(wú)棧滿問(wèn)題，空間可擴(kuò)充；鏈?zhǔn)綏o(wú)棧滿問(wèn)題，空間可擴(kuò)充；n插入插入（入棧）（入棧）與刪除與刪除（出棧）只能（出棧）只能在棧頂處執(zhí)行；在棧頂處執(zhí)行；n鏈?zhǔn)綏５臈ｍ斣阪滎^；鏈?zhǔn)綏５臈ｍ斣阪滎^；top棧底元素棧底元素當(dāng) top = NULL 時(shí)，表示空棧棧頂元素棧頂元素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; / 將一個(gè)已經(jīng)存在的棧置成空 public boolean isEmpty() return top = null; / 測(cè)試棧是否為空 public int length() / 求棧中的數(shù)據(jù)元素個(gè)數(shù)并由函數(shù)返回其值 Node p = top; / 初始化,p指向棧頂結(jié)點(diǎn),length為計(jì)數(shù)器 int length = 0; while (p != null) p = p.getNext();

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

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

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

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

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

15、oid clear(); /隊(duì)列直空隊(duì)列直空public boolean isEmpty(); /隊(duì)列判空隊(duì)列判空public int length(); /求隊(duì)列長(zhǎng)度求隊(duì)列長(zhǎng)度public Object peek();/取隊(duì)首元素取隊(duì)首元素public void offer(Object x) throws Exception;/入列（入隊(duì)）入列（入隊(duì)）public Object poll(); /出列（出隊(duì)）出列（出隊(duì)） 。實(shí)現(xiàn)此接口的方法有兩種實(shí)現(xiàn)此接口的方法有兩種: 順序隊(duì)列順序隊(duì)列鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列26front=rear空隊(duì)列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隊(duì)首元素？隊(duì)尾元素？隊(duì)空條件？隊(duì)滿條件？入隊(duì)操作？出隊(duì)操作？27 隊(duì)首元素？queueElemfront 隊(duì)尾元素？queueElemrear-1 隊(duì)空條件？ front=rear 隊(duì)滿條件？ rear=queueElem.length 入隊(duì)操作？ queueElemrear+=x; 出隊(duì)操作？ return queueEl

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

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

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

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

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

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

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

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

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