第3章 棧和隊(duì)列

第3章棧和隊(duì)列本章講解棧和隊(duì)列。要求理解棧和隊(duì)列概念；掌握棧和隊(duì)列的存儲(chǔ)結(jié)構(gòu)；掌握棧和隊(duì)列的基本操作；靈活應(yīng)用棧和隊(duì)列。重慶的麻辣燙，成都的串串香。串串香吃起美味，背后的付出卻艱辛，要把菜品一個(gè)一個(gè)串到一根竹簽上，吃貨才能一個(gè)一個(gè)吃出來(lái)。一把一把接著下鍋，先下鍋的先吃到。串起來(lái)是進(jìn)棧，吃出去是出棧；下鍋是進(jìn)隊(duì)列，出鍋是出隊(duì)列。提綱3.1?；靖拍?.2順序棧3.3鏈棧3.4棧應(yīng)用3.5隊(duì)列基本概念3.6順序隊(duì)列3.7鏈隊(duì)列3.8循環(huán)隊(duì)列和優(yōu)先隊(duì)列3.9隊(duì)列應(yīng)用3.10棧和隊(duì)列學(xué)習(xí)總結(jié)3.1棧基本概念棧是特殊的線性表，它只允許在線性表的一端操作。如圖3.1所示，裝乒乓球、網(wǎng)球、羽毛球的盒子皆屬于棧類型。能夠操作的這一端叫棧頂，不能操作的另一端叫棧底。顯然，棧有“先進(jìn)后出”或“后進(jìn)先出”的特點(diǎn)。3.1棧基本概念棧的抽象數(shù)據(jù)接口IStack3.2順序棧以順序存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)的棧稱為順序棧。3.2.1順序棧存儲(chǔ)結(jié)構(gòu)順序棧存儲(chǔ)結(jié)構(gòu)采用順序存儲(chǔ)方式，同順序表存儲(chǔ)結(jié)構(gòu)，故順序棧也可以用一維數(shù)組存儲(chǔ)如圖3.2所示，棧頂設(shè)置1個(gè)指針top指向棧頂元素（有的參考書(shū)將top指向棧頂元素的下1個(gè)位置，不影響理解）。3.2.1順序棧存儲(chǔ)結(jié)構(gòu)舉例：1個(gè)經(jīng)驗(yàn)豐富的探險(xiǎn)隊(duì)隊(duì)長(zhǎng)帶領(lǐng)若干隊(duì)員進(jìn)入1個(gè)狹長(zhǎng)的溶洞，要求后面隊(duì)員手拉手緊跟著，不能單獨(dú)走以免走散。隊(duì)長(zhǎng)最先進(jìn)洞，一路做返回記號(hào)，出洞卻最后出來(lái)。在這個(gè)例子中，溶洞看作棧，隊(duì)長(zhǎng)和隊(duì)員看作元素，這是個(gè)順序棧。3.2.2順序?；静僮黜樞驐ｎ怱qStack3.2.2順序棧基本操作長(zhǎng)度為5的順序棧的基本操作如圖3.3所示。3.2.2順序棧基本操作1.棧判空和棧判滿順序棧棧判空和棧判滿操作就是判斷棧是否為空和是否已滿。出棧時(shí)要判斷棧是否為空，入棧時(shí)要判斷棧是否為滿，否則操作無(wú)效，增加開(kāi)銷。那么又如何實(shí)現(xiàn)的呢？我們來(lái)看看算法3.1。3.2.2順序?；静僮鳌舅惴?.1】判斷順序棧是否為空和是否已滿。思路:由圖3.3的（1）和（3）易知，根據(jù)top的值可以判斷棧空和棧滿。代碼見(jiàn)算法3.13.2.2順序?；静僮?.入棧順序棧入棧操作是指向棧中添加元素，在棧沒(méi)有滿的情況下。那么又如何實(shí)現(xiàn)的呢？我們來(lái)看看算法3.2。3.2.2順序棧基本操作【算法3.2】順序棧入棧。思路:由圖3.3的（2）易知，在棧未滿的情況下先將top加1，再將入棧元素賦值給top處元素。代碼見(jiàn)算法3.23.2.2順序?；静僮?.出棧順序棧出棧操作是指棧頂元素出棧，在棧沒(méi)有空的情況下。那么又如何實(shí)現(xiàn)的呢？我們來(lái)看看算法3.3。3.2.2順序棧基本操作【算法3.3】順序棧出棧。思路:由圖3.3的（4）易知，先將出棧元素賦值給返回變量，再top減1。代碼見(jiàn)算法3.33.2.2順序棧基本操作4.取棧頂元素順序棧取棧頂元素操作是指訪問(wèn)棧頂元素但棧頂元素不出棧，在棧沒(méi)有空的情況下。那么又如何實(shí)現(xiàn)的呢？我們來(lái)看看算法3.4。3.2.2順序?；静僮鳌舅惴?.4】順序棧取棧頂元素。思路:

由圖3.3的易知，取棧頂元素只需訪問(wèn)top指針指向的元素，將其輸出。代碼見(jiàn)算法3.43.3鏈棧以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)的棧稱為鏈棧。3.3.1鏈棧存儲(chǔ)結(jié)構(gòu)鏈棧存儲(chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)方式，同鏈表存儲(chǔ)結(jié)構(gòu)。如圖3.4所示，用帶頭節(jié)點(diǎn)的單鏈表表示鏈棧，鏈棧的棧頂指針top指向單鏈表的首節(jié)點(diǎn)，單鏈表的尾節(jié)點(diǎn)為棧底節(jié)點(diǎn)。3.3.2鏈?；静僮麈湕９?jié)點(diǎn)類LinkNode描述鏈棧類LinkStack描述3.3.2鏈?；静僮?.棧判空鏈棧棧判空同順序棧棧判空，而鏈棧同鏈表一樣不存在溢出，除非內(nèi)存耗盡。因此鏈棧出棧時(shí)要判斷棧是否為空而入棧時(shí)不需要判斷是否為滿。3.3.2鏈?；静僮鳌舅惴?.5】判斷鏈棧是否為空。思路:由圖3.4易知，鏈棧為空同鏈表為空，此時(shí)只有頭節(jié)點(diǎn)，top指針也指向頭節(jié)點(diǎn)。代碼見(jiàn)算法3.53.3.2鏈?；静僮?.入棧鏈棧入棧操作類似單鏈表插入節(jié)點(diǎn)操作，但只能在頭節(jié)點(diǎn)之后即棧頂處插入。3.3.2鏈?；静僮鳌舅惴?.6】鏈棧入棧。思路:由圖3.4易知，插入的節(jié)點(diǎn)插入到頭節(jié)點(diǎn)之后；top指針指向插入節(jié)點(diǎn)。代碼見(jiàn)算法3.63.3.2鏈?；静僮?.出棧鏈棧出棧操作類似單鏈表刪除節(jié)點(diǎn)操作，在棧沒(méi)有空的情況下，但只能刪除首節(jié)點(diǎn)即棧頂節(jié)點(diǎn)。3.3.2鏈?；静僮鳌舅惴?.7】鏈棧出棧。思路:由圖3.4易知，若鏈棧非空則刪除首節(jié)點(diǎn)；若刪除后鏈棧為空則將top指針指向頭節(jié)點(diǎn)，否則將其指向下一個(gè)節(jié)點(diǎn)；返回刪除節(jié)點(diǎn)的data值。若鏈棧為空則返回空。代碼見(jiàn)算法3.73.3.2鏈?；静僮?.取棧頂元素鏈棧取棧頂元素操作同順序棧取棧頂元素操作，在棧沒(méi)有空的情況下。那么又如何實(shí)現(xiàn)的呢？我們來(lái)看看算法3.8。3.3.2鏈?；静僮鳌舅惴?.8】鏈棧取棧頂元素。思路:若鏈棧不為空則返top指針指向的節(jié)點(diǎn)的data值，否則返回空。代碼見(jiàn)算法3.83.4棧應(yīng)用

3.4棧應(yīng)用【進(jìn)一步思考】若1個(gè)十進(jìn)制數(shù)有小數(shù)，小數(shù)部分轉(zhuǎn)換為二進(jìn)制還需用到棧嗎？答：不需要，因?yàn)樾?shù)部分產(chǎn)生的二進(jìn)制數(shù)與產(chǎn)生順序相同，產(chǎn)生1個(gè)輸出1個(gè)即可。3.4棧應(yīng)用【例3.2】利用棧進(jìn)行括號(hào)匹配檢查，對(duì)2個(gè)測(cè)試用例"{{}}()(hello){({world}{})}"和"{{}}()(hello){({world}(})}"進(jìn)行測(cè)試，并分析算法的時(shí)空復(fù)雜度。思路：（1）從頭遍歷字符串，每個(gè)字符處理如下；（2）若遇左括號(hào)將其入棧；（3）若遇右括號(hào)：棧不為空時(shí)將其與棧頂元素比較：匹配則出棧，不匹配則返回false，棧為空時(shí)返回false；（4）字符指針移到下1位，重復(fù)（2）、（3），直到遍歷完字符串；（5）若棧為空則返回true，否則返回false。代碼見(jiàn)應(yīng)用3.23.4棧應(yīng)用【進(jìn)一步思考】用遞歸算法可否實(shí)現(xiàn)括號(hào)匹配檢查，為什么？答：可以，因?yàn)樵搯?wèn)題可以把大規(guī)模問(wèn)題分解為若干個(gè)相似小規(guī)模問(wèn)題。3.4棧應(yīng)用

3.4棧應(yīng)用【進(jìn)一步思考】漢諾塔問(wèn)題可以用遞歸算法實(shí)現(xiàn)嗎？答：可以，見(jiàn)后面遞歸章節(jié)內(nèi)容。3.5隊(duì)列基本概念隊(duì)列也是特殊的線性表，它限制在一端插入，另一端刪除。如圖3.6所示，現(xiàn)實(shí)中的隊(duì)列例子很多如排隊(duì)購(gòu)物、打飯、上公交、做核酸等皆屬于隊(duì)列類型。插入的那端叫隊(duì)尾，刪除的那端叫隊(duì)頭。顯然，隊(duì)列有“先進(jìn)先出”或“后進(jìn)后出”的特點(diǎn)。3.5隊(duì)列基本概念隊(duì)列的抽象數(shù)據(jù)接口IQueue描述3.6順序隊(duì)列以順序存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)的隊(duì)列稱為順序隊(duì)列。3.6.1順序隊(duì)列存儲(chǔ)結(jié)構(gòu)順序隊(duì)列存儲(chǔ)結(jié)構(gòu)采用順序存儲(chǔ)方式，同順序表存儲(chǔ)結(jié)構(gòu)，故順序隊(duì)列也可以用一維數(shù)組存儲(chǔ)。如圖3.7所示，隊(duì)頭設(shè)置1個(gè)指針front指向隊(duì)首元素，隊(duì)尾設(shè)置1個(gè)指針rear指向隊(duì)尾元素的下1個(gè)元素（有的參考書(shū)將front和rear指向向前的1個(gè)位置，不影響理解）。3.6.1順序隊(duì)列存儲(chǔ)結(jié)構(gòu)舉例：2個(gè)老師帶若干個(gè)小朋友出去旅游，無(wú)論走到哪里，為了保證安全，小朋友們排成隊(duì)列，2個(gè)老師一前一后監(jiān)管。在這個(gè)例子中，老師和小朋友組成的隊(duì)列類似順序隊(duì)列，2個(gè)老師分別看作隊(duì)頭指針和隊(duì)尾指針。3.6.2順序隊(duì)列基本操作順序隊(duì)列類SqQueue的描述3.6.2順序隊(duì)列基本操作長(zhǎng)度為5的順序隊(duì)列的基本操作如圖3.8所示。3.6.2順序隊(duì)列基本操作1.隊(duì)列判空和隊(duì)列判滿順序隊(duì)列判空和判滿操作就是判斷隊(duì)列是否為空和是否已滿。出隊(duì)時(shí)要判斷隊(duì)列是否為空，入隊(duì)時(shí)要判斷隊(duì)列是否為滿，否則操作無(wú)效，增加開(kāi)銷。3.6.2順序隊(duì)列基本操作【算法3.9】判斷順序隊(duì)列是否為空和是否已滿。思路:由圖3.8的（1）和（4）易知，根據(jù)front和rear關(guān)系值可以判斷隊(duì)列空和隊(duì)列滿。代碼見(jiàn)算法3.93.6.2順序隊(duì)列基本操作2.入隊(duì)順序隊(duì)列入隊(duì)操作是指向隊(duì)列中插入元素，在隊(duì)列沒(méi)有滿的情況下。3.6.2順序隊(duì)列基本操作【算法3.10】順序隊(duì)列入隊(duì)。思路:由圖3.8的（2）、（3）、（4）易知，在隊(duì)列未滿情況下入隊(duì)時(shí)front指針不動(dòng)，先賦值到rear處，再將rear指針向后移動(dòng)1位。代碼見(jiàn)算法3.103.6.2順序隊(duì)列基本操作3.出隊(duì)順序隊(duì)列出隊(duì)操作是指隊(duì)頭元素出隊(duì)列，在隊(duì)列沒(méi)有空的情況下。3.6.2順序隊(duì)列基本操作【算法3.11】順序隊(duì)列出隊(duì)。思路:由圖3.8的（5）易知，在隊(duì)列不空的情況下出隊(duì)時(shí)front指針處元素保存，front指針向后移動(dòng)1位，返回保存元素即出隊(duì)元素。代碼見(jiàn)算法3.113.6.2順序隊(duì)列基本操作4.取隊(duì)頭元素和取隊(duì)尾元素順序隊(duì)列取隊(duì)頭元素操作是指訪問(wèn)隊(duì)列的首元素，取隊(duì)尾元素操作是指訪問(wèn)隊(duì)列的尾元素。3.6.2順序隊(duì)列基本操作【算法3.12】順序隊(duì)列取隊(duì)頭元素和取隊(duì)尾元素。思路:由圖3.8易知，取隊(duì)頭元素可以訪問(wèn)front指針指向的元素；取隊(duì)尾元素可以訪問(wèn)rear-1處的元素。代碼見(jiàn)算法3.123.7鏈隊(duì)列以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)的隊(duì)列稱為鏈隊(duì)列。3.7.1鏈隊(duì)列存儲(chǔ)結(jié)構(gòu)鏈隊(duì)列存儲(chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)方式，同鏈表存儲(chǔ)結(jié)構(gòu)。如圖3.9所示，front指針指向隊(duì)頭節(jié)點(diǎn)，rear指針指向隊(duì)尾節(jié)點(diǎn)。3.7.2鏈隊(duì)列基本操作鏈隊(duì)列類LinkQueue的描述3.7.2鏈隊(duì)列基本操作長(zhǎng)度為3的鏈隊(duì)列的基本操作如圖3.10所示。3.7.2鏈隊(duì)列基本操作隊(duì)列判空鏈隊(duì)列判空操作就是判斷隊(duì)列是否為空。出隊(duì)時(shí)要判斷鏈隊(duì)列是否為空，否則操作無(wú)效，增加開(kāi)銷。3.7.2鏈隊(duì)列基本操作【算法3.13】判斷鏈隊(duì)列是否為空。思路:由圖3.10的（1）易知，鏈隊(duì)列為空時(shí)front和rear指針都指向頭節(jié)點(diǎn)。代碼見(jiàn)算法3.133.7.2鏈隊(duì)列基本操作2.入隊(duì)鏈隊(duì)列入隊(duì)操作是指在隊(duì)列中插入節(jié)點(diǎn)。3.7.2鏈隊(duì)列基本操作【算法3.14】鏈隊(duì)列入隊(duì)。思路:由圖3.10的（2）、（3）易知，鏈隊(duì)列入隊(duì)時(shí)，若隊(duì)列非空則尾插法1個(gè)節(jié)點(diǎn)，再將rear指向尾節(jié)點(diǎn)；若隊(duì)列為空則頭節(jié)點(diǎn)后插入，再將front和rear都指向插入之后的首節(jié)點(diǎn)。代碼見(jiàn)算法3.143.7.2鏈隊(duì)列基本操作3.出隊(duì)鏈隊(duì)列出隊(duì)操作是指從隊(duì)列中刪除節(jié)點(diǎn)。3.7.2鏈隊(duì)列基本操作【算法3.15】鏈隊(duì)列出隊(duì)。思路:由圖3.10的（4）易知，鏈隊(duì)列出隊(duì)時(shí)，若隊(duì)列為空則返回null；若隊(duì)列非空：（1）只有1個(gè)節(jié)點(diǎn)情形：head的next置為null；front和rear都指向head。（2）不止1個(gè)節(jié)點(diǎn)情形：刪除首節(jié)點(diǎn)；front指針指向下1個(gè)節(jié)點(diǎn)。代碼見(jiàn)算法3.153.7.2鏈隊(duì)列基本操作4.取隊(duì)頭元素和取隊(duì)尾元素鏈隊(duì)列取隊(duì)頭元素操作是指訪問(wèn)隊(duì)列的首節(jié)點(diǎn)，取隊(duì)尾元素操作是指訪問(wèn)隊(duì)列的尾節(jié)點(diǎn)。3.7.2鏈隊(duì)列基本操作【算法3.16】鏈隊(duì)列取隊(duì)頭元素和取隊(duì)尾元素。思路:由圖3.10易知，若隊(duì)列非空，取隊(duì)頭元素可以訪問(wèn)front指針指向的節(jié)點(diǎn)；取隊(duì)尾元素可以訪問(wèn)rear指針指向的節(jié)點(diǎn)。若隊(duì)列為空則返回空。代碼見(jiàn)算法3.163.8循環(huán)隊(duì)列和優(yōu)先隊(duì)列循環(huán)隊(duì)列和優(yōu)先隊(duì)列都是特殊的隊(duì)列，它們?cè)趹?yīng)用中能夠解決特殊問(wèn)題。3.8.1循環(huán)隊(duì)列

3.8.1循環(huán)隊(duì)列2.解決方案將順序隊(duì)列的首尾相連構(gòu)成1個(gè)環(huán)，進(jìn)行隊(duì)列操作時(shí)front和rear指針在這個(gè)環(huán)上移動(dòng)，這樣的隊(duì)列稱為循環(huán)隊(duì)列或環(huán)形隊(duì)列。循環(huán)隊(duì)列可以把空余的空間利用起來(lái)，這樣就解決了順序隊(duì)列的假溢出問(wèn)題。如圖3.11所示。3.8.1循環(huán)隊(duì)列

3.8.1循環(huán)隊(duì)列3.類描述和基本操作循環(huán)隊(duì)列類CircleSqQueue和基本操作描述3.8.2優(yōu)先隊(duì)列問(wèn)題的提出隊(duì)列“先進(jìn)先出”的特點(diǎn)決定了不能適應(yīng)一些場(chǎng)景。舉例：到醫(yī)院看病，依次排隊(duì)看病，但此時(shí)有病危病人送來(lái)，醫(yī)生就得優(yōu)先看他，但對(duì)于絕大多數(shù)人來(lái)講還是先來(lái)先服務(wù)的隊(duì)列模式。再舉例：按照高考成績(jī)從高到低錄取排成隊(duì)列，顯然每1個(gè)成績(jī)?cè)陉?duì)列中的位置也就確定了，無(wú)論成績(jī)有沒(méi)有增刪。在這些例子中，都允許有插隊(duì)現(xiàn)象，不然用前面介紹的隊(duì)列模式不能滿足實(shí)際需要。3.8.2優(yōu)先隊(duì)列2.解決方案將隊(duì)列中的每個(gè)元素設(shè)置優(yōu)先級(jí)，隊(duì)頭元素優(yōu)先級(jí)最高，隊(duì)尾元素優(yōu)先級(jí)最低，即優(yōu)先級(jí)高的先出隊(duì)，這樣的隊(duì)列稱為優(yōu)先隊(duì)列。利用優(yōu)先隊(duì)列讓插隊(duì)現(xiàn)象變得合理合情。優(yōu)先隊(duì)列的存儲(chǔ)結(jié)構(gòu)可以是順序存儲(chǔ)結(jié)構(gòu)，也可以是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3.8.2優(yōu)先隊(duì)列3.類描述和基本操作優(yōu)先隊(duì)列節(jié)點(diǎn)類PriorityNode描述采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)先隊(duì)列類PriorityQueue和基本操作描述3.8.2優(yōu)先隊(duì)列從上面的節(jié)點(diǎn)類和操作描述可以看出，優(yōu)先隊(duì)列與普通隊(duì)列相似，主要不同的是：（1）優(yōu)先隊(duì)列節(jié)點(diǎn)多了1個(gè)優(yōu)先級(jí)屬性；（2）進(jìn)隊(duì)操作時(shí)，首先要根據(jù)進(jìn)隊(duì)元素的優(yōu)先級(jí)找到其插入位

置，再將其插入隊(duì)列中。3.9隊(duì)列應(yīng)用【例3.4】打印楊輝三角形。輸入：n，代表行數(shù)；輸出：n行楊輝三角形。思路：（1）初始化1個(gè)空鏈隊(duì)列，并將2個(gè)1入隊(duì)列；（2）外層循環(huán)控制n行；（3）內(nèi)層循環(huán)計(jì)算并打印列數(shù)字；（4）內(nèi)外層循環(huán)之間入隊(duì)1個(gè)0進(jìn)行重置計(jì)算。代碼見(jiàn)應(yīng)用3.43.9隊(duì)列應(yīng)用【進(jìn)一步思考】請(qǐng)寫(xiě)出實(shí)現(xiàn)例3.4算法用棧結(jié)構(gòu)實(shí)現(xiàn)的思路。答：棧結(jié)構(gòu)實(shí)現(xiàn)思路：處理進(jìn)棧、出棧、計(jì)算及保存之間的邏輯關(guān)系。3.9隊(duì)列應(yīng)用【例3.5】利用優(yōu)先隊(duì)列實(shí)現(xiàn)對(duì)操作系統(tǒng)進(jìn)程調(diào)度：優(yōu)先級(jí)高的進(jìn)程先獲得CPU，相同優(yōu)先級(jí)的進(jìn)程先到先獲得CPU。思路：（1）初始化1個(gè)空優(yōu)先隊(duì)列；（2）將若干進(jìn)程入隊(duì)；（3）進(jìn)程出隊(duì)，直到隊(duì)列空。代碼見(jiàn)應(yīng)用3.53.9隊(duì)列應(yīng)用【進(jìn)一步思考】?jī)?yōu)先隊(duì)列在Java語(yǔ)言中對(duì)應(yīng)的類是什么，其內(nèi)部本質(zhì)上在做什么？答：優(yōu)先隊(duì)列在Java語(yǔ)言中對(duì)應(yīng)的類是java.util.PriorityQueue<E>