面試指北：算法與數(shù)據(jù)結(jié)構(gòu)（四）棧與隊(duì)列

上次聊到數(shù)組與鏈表，它們都是線性表，數(shù)組與鏈表的本質(zhì)區(qū)別是內(nèi)存是否連續(xù)，進(jìn)而得出結(jié)論：數(shù)組可以在 O(1) 時間復(fù)雜度進(jìn)行隨機(jī)訪問，但是對內(nèi)存要求嚴(yán)苛；鏈表訪問元素時間復(fù)雜度為 O(n)，但是對內(nèi)存要求低。

今天來介紹另外兩個線性表中的數(shù)據(jù)結(jié)構(gòu)：棧和隊(duì)列。

棧 Stack

棧是一種線性表，只有前后關(guān)系，但是相對于數(shù)組和鏈表來說，其元素的操作是受限的。棧只允許在一端進(jìn)行元素的插入、刪除操作，往棧中放入元素我們稱之為壓棧操作，從棧中取出元素我們稱之為出棧。我們可以把棧看作是一個一端開口的羽毛球筒，我們壓棧、出棧操作數(shù)據(jù)的過程，就是我們從筒中放入、取出羽毛球的過程。當(dāng)然，棧是一種抽象的數(shù)據(jù)結(jié)構(gòu)，我們在實(shí)現(xiàn)它時，既可以使用數(shù)組，也可以使用鏈表。

接下來我們看一下棧的使用情景。

瀏覽器網(wǎng)頁前進(jìn)后退

我們經(jīng)常會使用瀏覽器瀏覽網(wǎng)頁，網(wǎng)頁中有很多超鏈接可以跳轉(zhuǎn)到下一個頁面。而有時我們希望能夠返回上一個頁面繼續(xù)瀏覽，再返回上一個頁面之后，我們還可能再回到剛才的子頁面。

使用兩個棧就可以實(shí)現(xiàn)這種能夠隨意前進(jìn)后退的網(wǎng)頁瀏覽了。

我們把一開始打開的網(wǎng)頁壓棧放入棧 a，如果此時點(diǎn)擊網(wǎng)頁中的鏈接查看下一個頁面，那我們把子頁面繼續(xù)放入棧 a。當(dāng)我們返回時，把子頁面從 a 中出棧，放入棧 b。這個時候我們關(guān)閉頁面，繼續(xù)從 a 中出棧放入棧 b 即可。如果我們點(diǎn)擊前進(jìn)按鈕，則去棧 b 中出棧即可。也就是說，如果我們把依次打開過的網(wǎng)頁放入棧 a 維護(hù)，回退的界面放入棧 b 維護(hù)。點(diǎn)擊后退按鈕時，查詢棧 a，有頁面則出棧，放入棧 b，沒有則無法后退；點(diǎn)擊前進(jìn)按鈕時，查詢棧 b，有頁面則出棧，沒有則無法前進(jìn)。

函數(shù)調(diào)用棧

基本每一個編程語言中，都存在函數(shù)的概念。一個函數(shù)可以調(diào)用另外一個函數(shù)，那么函數(shù)之間的調(diào)用是如何實(shí)現(xiàn)的呢？也是用棧。

以 Java 為例，我們編寫 Java 代碼之后，是編譯為 class 字節(jié)碼，然后交給 Java 虛擬機(jī)執(zhí)行。在 Java 虛擬機(jī)中，是使用一個棧來完成函數(shù)調(diào)用的，每一個函數(shù)在棧中所占有的空間稱為棧幀。Java 入口函數(shù)為 main 函數(shù)，執(zhí)行時先將 main 函數(shù)入棧，此時棧幀中會保存該函數(shù)的局部變量、操作數(shù)棧、動態(tài)連接、方法返回地址等內(nèi)容。當(dāng) main 函數(shù)調(diào)用一個子函數(shù) add 時，虛擬機(jī)會繼續(xù)將 add 函數(shù)相關(guān)內(nèi)容壓入棧頂，add 函數(shù)執(zhí)行完畢后會出棧，此時 main 函數(shù)處于棧頂，會繼續(xù)執(zhí)行 main 函數(shù)。

這個例子我們可以看到，對于基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的理解，可以幫助我們了解平時常用語言、框架的實(shí)現(xiàn)細(xì)節(jié)，對于我們深入學(xué)習(xí)計(jì)算機(jī)知識很有幫助。除了以上兩個例子之外，棧還可以用來做表達(dá)式求值、括號匹配等，感興趣的話可以自行了解。

隊(duì)列 Queue

隊(duì)列和棧一樣，也是一種操作受限的線性表數(shù)據(jù)結(jié)構(gòu)。棧只能在一端進(jìn)行插入和刪除操作，隊(duì)列則是在一端進(jìn)行刪除操作，稱為出隊(duì)，在另一端進(jìn)行插入操作，稱為入隊(duì)。

和棧一樣，隊(duì)列也可以使用數(shù)組或者鏈表來實(shí)現(xiàn)。當(dāng)我們使用數(shù)組來實(shí)現(xiàn)時，需要維護(hù)兩個變量 head、tail 標(biāo)識隊(duì)列的頭部和尾部。入隊(duì)時，元素放入數(shù)組現(xiàn)有元素的末尾，tail 往后移動一位。出隊(duì)時，首個元素刪除，head 往后移動一位。此時會出現(xiàn)這樣一種情形：當(dāng)我們經(jīng)過不斷的入隊(duì)和出隊(duì)之后，head、tail 會不斷的往后漂移，當(dāng) tail 到達(dá)數(shù)組尾部時，沒辦法再進(jìn)行入隊(duì)操作，但是很可能 head 之前還有空間。這就導(dǎo)致空間浪費(fèi)。此時我們可以通過每次出隊(duì)都把所有數(shù)據(jù)往前搬移一位，也可以通過 tail 到達(dá)數(shù)組末尾時，搬移所有數(shù)據(jù)到數(shù)組頭部解決問題，但是頻繁的搬移操作會浪費(fèi)性能。

由此導(dǎo)致了循環(huán)隊(duì)列的產(chǎn)生。循環(huán)隊(duì)列的關(guān)鍵是，把數(shù)組看成一個環(huán)狀結(jié)構(gòu)。head、tail 到達(dá)數(shù)組末尾時，仍可以回到頭部的位置。此時使用 tail 尾部這個詞就不太合適，改用 rear 后部更好。如下圖，入隊(duì)出隊(duì)的過程，就是操作 head、rear 位置的過程。在這個環(huán)中，我們可以不斷的轉(zhuǎn)圈修改其位置，而不會出現(xiàn)上述局面，也就把我們從頻繁搬移數(shù)據(jù)中解綁，減少性能消耗。

但是我們的底層實(shí)現(xiàn)還是數(shù)組，這里的關(guān)鍵問題有兩個：

1.如何在 rear 到達(dá)數(shù)組尾部時，處理 rear 的位置？2.如何判斷隊(duì)空和隊(duì)滿？

對于第一個問題我們可以使用求余操作來解決問題。普通隊(duì)列我們是直接 rear++ 操作位置，現(xiàn)在我們改成 rear = (rear + 1) % array.length - 1 來操作即可。當(dāng)然 head 也是如此。

對于第二個問題，普通隊(duì)列我們通過 head == 0 && tail == array.length 來判斷隊(duì)滿，head == tail 來判斷隊(duì)空。循環(huán)隊(duì)列還是使用 head == tail 判斷隊(duì)空，隊(duì)滿的條件就要改成 (tail + 1) % array.length == head。

另外一種隊(duì)列是阻塞隊(duì)列。阻塞隊(duì)列就是在隊(duì)列基礎(chǔ)上增加了阻塞操作。當(dāng)隊(duì)空的時候，從隊(duì)列取出數(shù)據(jù)時會阻塞；當(dāng)隊(duì)滿時，在隊(duì)列中插入數(shù)據(jù)會阻塞。可以發(fā)現(xiàn)，阻塞隊(duì)列跟我們常說的 生產(chǎn)者-消費(fèi)者模型 邏輯基本一致。

還有一種比較常用的隊(duì)列是優(yōu)先隊(duì)列，即優(yōu)先級更高的元素優(yōu)先出隊(duì)，該隊(duì)列的實(shí)現(xiàn)涉及到完全二叉樹、大頂堆、小頂堆相關(guān)知識，我們后續(xù)會涉及到。

總結(jié)

我們可以看到棧和隊(duì)列是一種抽象的數(shù)據(jù)結(jié)構(gòu)，定義一種操作規(guī)則，然后應(yīng)用到對應(yīng)的場景之中。這兩種數(shù)據(jù)結(jié)構(gòu)的操作規(guī)則和其應(yīng)用場景是契合的。我們在學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)時，了解其優(yōu)點(diǎn)和缺點(diǎn)，進(jìn)而了解其應(yīng)用場景是十分重要的。沒有最好的數(shù)據(jù)結(jié)構(gòu)和算法，只有在某種場景下更加適合的數(shù)據(jù)結(jié)構(gòu)與算法。