數據結構（Python Java）（微課版） 課件 第3章 棧和隊列

數據結構與算法設計3.1棧棧的定義與基本操作棧的順序存儲結構與實現(xiàn)棧的鏈式存儲結構與實現(xiàn)順序棧和鏈棧的比較棧的應用案例棧的定義與基本操作棧的定義棧：限定僅在一端進行插入和刪除操作的線性表（a1,…,an-1,an）棧頂（top）：允許插入和刪除的一端稱為棧頂棧底（bottom）：另一端稱為棧底插入位置：1~n+1刪除位置：1~n線性表插入位置：n+1刪除位置：n棧棧底棧頂棧的定義與基本操作棧的操作插入：入棧、進棧、壓棧刪除：出棧、彈棧a插入刪除bc此時執(zhí)行出棧操作，哪個元素可以出棧呢？棧的操作特性：后進先出（LastInFirstOut，LIFO）空棧：不含任何數據元素的棧

如何判空棧

initStack()：初始化操作。設置一個空棧isEmpty()：判棧空函數。若為空，則返回true，否則返回false。getTop()：讀棧頂元函數。若棧不空，函數值為棧頂元素，否則為空元素NULLpush(x)：進棧操作。將元素x插入棧中，使x成為棧的棧頂元素pop()：出棧函數。若棧不空，函數值為棧頂元素，且從棧中刪除當前棧頂元素，否則函數值為空元素NULLclearStack()：棧置空操作。不論棧是否為空棧，置為空棧棧的定義與基本操作棧的基本操作棧的定義與基本操作棧的抽象數據類型定義ADTStackDataModelOperationendADT棧中元素具有相同類型及后進先出特性，相鄰元素具有前驅和后繼關系initStack：棧的初始化clearStack：清空棧內元素push：入棧pop：出棧getTop：取棧頂元素isEmpty：判空利用一組地址連續(xù)的存儲單元依次存放從棧底到棧頂的數據元素a1a2……an順序棧Sai……0n棧底棧頂top棧的順序存儲結構與實現(xiàn)順序棧用數組的一端作為棧底設變量top存儲棧頂元素所在的下標組織形式與單鏈表類似，鏈表的尾部是棧底，鏈表的頭部是棧頂FtopdatanextEDANULL棧頂棧底棧的鏈式存儲結構與實現(xiàn)鏈棧順序棧和鏈棧的比較順序棧和鏈棧的基本算法的時間復雜度均為O(1)空間復雜度比較Java中，初始時順序棧需要確定棧的長度，所以存在存儲元素個數的限制和浪費存儲空間的問題。鏈棧沒有棧滿的問題，只有當內存沒有可用存儲空間時才會出現(xiàn)棧滿，但是每個元素都需要指針域，從而存在結構性開銷。把所有的余數按出現(xiàn)的逆序排列起來（先出現(xiàn)的余數排在后面，后出現(xiàn)的余數排在前面）十進制數轉換成二進制數棧的應用351784210110001余數結果：100011表達式求值棧的應用對算術表達式求值：

1+2*4-9/3遵循先乘除后加減、先左后右及先括號內，后括號外的四則運算法則，其計算順序應為：1+2*4-9/3└─┘└─┘①②└──┘③└───┘④采用“運算符優(yōu)先數法”對每種運算符賦于一個優(yōu)先數，如：運算符：*/+-#優(yōu)先數：22110其中

#是表達式結束符表達式求值時，設立兩個棧運算符棧(OPTR)操作數棧(OPND)分別存放表達式中的運算符和操作數

步驟OPTR棧OPND棧輸入字符主要操作──────────────────────────────────────────

1 # 1+2*4-9/3# PUSH(OPND,'1')2 # 1+2*4-9/3#PUSH(OPTR,'+')3 #+ 12*4-9/3# PUSH(OPND,'2')4 #+ 12*4-9/3# PUSH(OPTR,'*')5 #+* 124-9/3# PUSH(OPND,'4')6 #+* 124-9/3# OPERATE('2','*','4')7 #+ 18-9/3# OPERATE('1','+','8')8 # 9-9/3# PUSH(OPTR,'-')9 #- 99/3# PUSH(OPND,'9')10 #- 99/3# PUSH(OPTR,'/')11 #-/ 993# PUSH(OPND,'3')12 #-/ 993# OPERATE('9','/','3')13 #- 93# OPERATE('9','-','3')14 # 6# RETURN(TOP(OPND))表達式求值棧的應用小結3.1棧棧的定義與基本操作棧的順序存儲結構與實現(xiàn)棧的鏈式存儲結構與實現(xiàn)順序棧和鏈棧的比較棧的應用案例數據結構與算法設計3.2隊列隊列的定義與基本操作隊列的順序存儲結構與實現(xiàn)隊列的鏈式存儲結構與實現(xiàn)循環(huán)隊列與鏈隊列的比較隊列的應用案例隊列的定義隊列的定義與基本操作只能在表的一端進行插入，在表的另一端進行刪除的線性表（a1,a2,…,an-1,an）a1

a2

…

an棧a1

a2

…

an隊列隊頭隊尾隊尾：允許插入的一端，相應地，位于隊尾的元素稱為隊尾元素隊頭：允許刪除的一端，相應地，位于隊頭的元素稱為隊頭元素隊列的操作隊列的定義與基本操作隊列的操作特性：先進先出（FirstInFirstOut，F(xiàn)IFO）a插入：入隊、進隊入隊bc例：有三個元素按a、b、c的次序依次入隊，且每個元素只允許進一次隊，則出隊序列是什么？答：出隊序列只有一種情況：abc出隊刪除：出隊空隊列：不含任何數據元素的隊列

任何時候執(zhí)行出隊操作，一定是哪個元素呢？隊列的基本操作隊列的定義與基本操作initQueue()：初始化。設置一個空隊列qisEmpty()：判斷隊列是否為空。若隊列q為空，函數值為true，否則為false

size()：求隊列長度。函數值為隊列q中當前所含元素的個數getHead()：讀隊頭元素。若隊列q不為空，函數值為隊頭元素，否則為空元素enQueue(x)：入隊。將元素x插入隊列q的尾部，使x成為新的隊尾元素delQueue()：出隊。若隊列q不為空，函數值為隊頭元素，且從隊列q中刪除當前隊頭元素，否則函數值為空元素順序隊列隊列的順序存儲結構與實現(xiàn)隊列的順序存儲結構隊尾：設變量rear存儲隊尾元素所在的下標隊頭：用數組的一端作為隊頭，從下標0處開始存放01234a1a2a3a4rear例：a1a2a3a4

依次入隊順序隊列隊列的順序存儲結構與實現(xiàn)例：a1

出隊01234a1a2a3a4rear01234a2a3a4rear隊頭元素出隊后，后面的元素都需要前移，時間性能較差如何改進出隊操作的時間性能？01234a2a3a4rear設置隊頭、隊尾兩個位置變量約定：隊頭front指向隊頭元素的前一個位置，隊尾rear指向隊尾元素fronta1入隊、出隊時間性能均是O(1)順序隊列隊列的順序存儲結構與實現(xiàn)順序隊列隊列的順序存儲結構與實現(xiàn)隊列的移動有什么特點？01234a2a3a4front整個隊列向數組下標較大方向移動單向移動性隊列的單向移動性會產生什么問題？a5假溢出：數組空間發(fā)生上溢，但數組的低端還有空閑空間rear循環(huán)隊列隊列的順序存儲結構與實現(xiàn)如何解決假溢出呢？01234a3a4rearfront如何使數組下標循環(huán)呢？a5a6循環(huán)隊列：隊列采用順序存儲，并且數組是頭尾相接的循環(huán)結構循環(huán)隊列隊列的順序存儲結構與實現(xiàn)01234a3rearfront如何判斷循環(huán)隊列的隊空？隊空的判定條件：front==rear循環(huán)隊列隊列的順序存儲結構與實現(xiàn)a6a2a4a5rearfront如何判斷循環(huán)隊列隊滿？隊空的判定條件：front==rear隊滿的判定條件：front==rearx01234循環(huán)隊列隊列的順序存儲結構與實現(xiàn)如何確定不同的隊空、隊滿的判定條件？隊空的判定條件：front==rear隊滿的判定條件：front==rear數組中有一個空閑單元01234a6a2a4a5rearfront01234a1a2a4a5rearfront(rear+1)%QUEUE_SIZE=front鏈隊列隊列的鏈式存儲是單鏈表，同時帶有頭指針和尾指針頭指針指向隊頭結點尾指針指向隊尾結點隊列的鏈式存儲結構頭結點^…...head隊頭隊尾tail設隊首、隊尾指針head和tail,head指向隊頭，tail指向隊尾循環(huán)隊列與鏈隊列的比較循環(huán)隊列和鏈隊列基本算法的時間復雜度均為O(1)空間復雜度比較初始時循環(huán)隊列必須確定一個固定的長度，所以存在存儲元素個數的限制和浪費存儲空間的問題。鏈隊列沒有溢出問題，只有當內存沒有可用存儲空間時才會出現(xiàn)溢出，但是每個元素都需要指針域，存在結構性開銷。隊列的應用案例舞伴配對問題在某舞會上，男士和女士進入舞廳時，各自排成一隊。舞會開始時，依次從男隊和女隊的隊頭各出一人配成舞伴。若兩隊初始人數不相同，則較長的那一隊中未配對者等待下一輪。在算法中，假設男士和女士的記錄存放在一個數組中，然后依次掃描該數組的各元素，并根據性別來決定是進入男隊還是女隊。當這兩個隊列構造完成后，依次使兩隊當前的隊頭元素出隊來配成舞伴，直至某隊列變空為止。此時，若某隊仍有等待者，算法輸出此隊列中等