須彌零一

認(rèn)識數(shù)據(jù)結(jié)構(gòu)之【隊列和棧】

本系列前幾篇文章介紹了樹、數(shù)組、鏈表三種基本數(shù)據(jù)結(jié)構(gòu)，這篇文章講一個兩個很相近的數(shù)據(jù)結(jié)構(gòu)隊列和棧。錯過之前文章的朋友可以通過以下鏈接查閱。

認(rèn)識數(shù)據(jù)結(jié)構(gòu)系列往期文章：

?認(rèn)識數(shù)據(jù)結(jié)構(gòu)之【樹】?認(rèn)識數(shù)據(jù)結(jié)構(gòu)之【數(shù)組】?認(rèn)識數(shù)據(jù)結(jié)構(gòu)之【鏈表】

隊列

在平常我們生活中有一種常見的社會現(xiàn)象。當(dāng)我們在超市買完東西去結(jié)賬的時候，如果柜臺的人很多，那必然就會排起一條長龍。而且必須在前一個人完成結(jié)賬下一個人才能進(jìn)行結(jié)賬。而我們本次要講的隊列這種數(shù)據(jù)結(jié)構(gòu)也是具有這樣的特點(diǎn)。

隊列的定義

在上篇介紹鏈表的文章中，我介紹了線性表的一些特性，不知您是否還有印象。其實(shí)隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，隊列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊尾，進(jìn)行刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。

隊列的操作

隊列的數(shù)據(jù)元素稱為隊列元素。

?入隊：在隊列中插入一個隊列元素稱為入隊?出隊：從隊列中刪除一個隊列元素稱為出隊

隊列的特點(diǎn)

因為隊列只允許在一端插入，在另一端刪除，所以只有最早進(jìn)入隊列的元素才能最先從隊列中刪除，故隊列具有先進(jìn)先出（FIFO—first in first out）的特點(diǎn)。

隊列的消費(fèi)限流

在應(yīng)用中隊列一般用于消息處理，這種情況下通常會引入一些例如kfaka、RabitMQ這樣的消息中間件以達(dá)到消息生產(chǎn)者和消息消費(fèi)者解耦的目的。這里先不考慮這些中間件的一些復(fù)雜使用場景及功能，我們思考一種場景。

通常情況下就像超市收銀臺臺一樣，顧客購買完東西是要在收銀臺結(jié)賬的，我們系統(tǒng)中產(chǎn)生的消息構(gòu)成的隊列也是需要消費(fèi)的。那么當(dāng)消息隊列中有海量的消息怎么辦呢？我全部放過去我的下游服務(wù)器不就崩了？所以這里就需要引入限流這個概念。

一般的限流算法有：

?計數(shù)器限流?漏桶算法?令牌桶算法

注：關(guān)于各種限流算法后續(xù)有文章會單獨(dú)講解，請關(guān)注須彌零一公眾號第一時間獲取，此處不再展開。

棧

了解了隊列就比較好理解棧了。不知道您有沒有購買VC泡騰片的經(jīng)歷，或者見過常見VC泡騰片的那種類似的包裝的東東。沒見過也沒關(guān)系，就像下面這種：

這個圓柱形的東西用來理解棧是最合適不過的了。觀察一下這個東東，它是怎么把一片一片的泡騰片裝進(jìn)去的呢？當(dāng)然，這難不倒聰明的你，肯定是從口口一片一片的塞進(jìn)去的唄。對！沒錯。那我們要吃的時候當(dāng)然也是從這個開口直接取一個出來就好。但是，我如果就想吃從底部數(shù)的第一個呢？答案也很顯然，我只能一個一個把上面的取出來才能拿到最底部的那個。OK！這個棧的模型已經(jīng)出來了，您看懂了嗎？

棧的定義

棧（stack）又名堆棧，同隊列一樣，它也是一種運(yùn)算受限的線性表。棧是允許在同一端進(jìn)行插入和刪除操作的特殊線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動；棧中元素個數(shù)為零時稱為空棧。

棧的操作

棧中的數(shù)據(jù)元素稱為棧元素。

?PUSH：從棧頂插入棧元素一般稱為進(jìn)棧、入棧或者壓棧。?POP：從棧頂刪除棧元素則一般稱為退棧、出棧或者彈棧。

棧的特點(diǎn)

因為棧只有一個開口，即棧頂。所以最早入棧的元素到最后才能從棧中彈出，故棧具有先入后出（FILO—first in last out）的特點(diǎn)。

棧的應(yīng)用場景

我們使用的瀏覽器中就使用到了棧。我們從頁面A上跳轉(zhuǎn)到了頁面B，又從頁面B上跳轉(zhuǎn)到了頁面C。當(dāng)我們想返回到頁面B的時候就需要點(diǎn)兩次后退按鈕。這個功能正是使用了棧的先進(jìn)后出特點(diǎn)，完成了瀏覽歷史的保留并完成了瀏覽歷史的回退。

另外，游戲漢諾塔就是一個非常典型的應(yīng)用了棧原理的游戲，感興趣的話您可以玩玩看。

漢諾塔（Tower of Hanoi），又稱河內(nèi)塔，是一個源于印度古老傳說的益智玩具。大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

最后

本篇文章大體對比介紹了隊列和棧的基本特點(diǎn)，同樣沒有操作的實(shí)現(xiàn)。您可以結(jié)合前兩篇關(guān)于數(shù)組和鏈表的知識，自己手動通過數(shù)組或者鏈表來構(gòu)造一個隊列和棧，以及各自的獨(dú)有的操作加深一下理解。

大家下期見~(●ˇ?ˇ●)

---- END ----

往期文章：

?認(rèn)識數(shù)據(jù)結(jié)構(gòu)之【樹】?認(rèn)識數(shù)據(jù)結(jié)構(gòu)之【數(shù)組】?認(rèn)識數(shù)據(jù)結(jié)構(gòu)之【鏈表】

歡迎關(guān)注我的公眾號“須彌零一”，原創(chuàng)技術(shù)文章第一時間推送。