數據結構–棧和隊列基礎知識

• 2020 年 9 月 1 日
• 筆記
• 基本數據結構與常用算法、設計模式

一 概述

棧和隊列，嚴格意義上來說，也屬於線性表，因為它們也都用於存儲邏輯關係為 “一對一” 的數據，但由於它們比較特殊，因此將其單獨作為一篇文章，做重點講解。既然棧和隊列都屬於線性表，根據線性表分為順序表和鏈表的特點，棧也可分為順序棧和鏈表，隊列也分為順序隊列和鏈隊列，這些內容都會在本章做詳細講解。

使用棧結構存儲數據，講究「先進後出」，即最先進棧的數據，最後出棧；使用隊列存儲數據，講究 “先進先出”，即最先進隊列的數據，也最先出隊列。

二 棧

2.1 棧的基本概念

同順序表和鏈表一樣，棧也是用來存儲邏輯關係為 “一對一” 數據的線性存儲結構，如下圖所示。 

  
從上圖我們看到，棧存儲結構與之前所了解的線性存儲結構有所差異，這緣於棧對數據 “存” 和 “取” 的過程有特殊的要求：

1. 棧只能從表的一端存取數據，另一端是封閉的；
2. 在棧中，無論是存數據還是取數據，都必須遵循”先進後出”的原則，即最先進棧的元素最後出棧。拿圖 1 的棧來說，從圖中數據的存儲狀態可判斷出，元素 1 是最先進的棧。因此，當需要從棧中取出元素 1 時，根據”先進後出”的原則，需提前將元素 3 和元素 2 從棧中取出，然後才能成功取出元素 1。

因此，我們可以給棧下一個定義，即棧是一種只能從表的一端存取數據且遵循 “先進後出” 原則的線性存儲結構。通常，棧的開口端被稱為棧頂；相應地，封口端被稱為棧底。因此，棧頂元素指的就是距離棧頂最近的元素，拿下圖中的棧頂元素為元素 4；同理，棧底元素指的是位於棧最底部的元素，下 中的棧底元素為元素 1。

2.2 進棧和出棧

基於棧結構的特點，在實際應用中，通常只會對棧執行以下兩種操作：

• 向棧中添加元素，此過程被稱為”進棧”（入棧或壓棧）；
• 從棧中提取出指定元素，此過程被稱為”出棧”（或彈棧）；

2.3 棧的具體實現

棧是一種 “特殊” 的線性存儲結構，因此棧的具體實現有以下兩種方式：

1. 順序棧：採用順序存儲結構可以模擬棧存儲數據的特點，從而實現棧存儲結構。使用順序表模擬棧存儲結構常用的實現思路，即在順序表中設定一個實時指向棧頂元素的變量（一般命名為 top），top 初始值為 -1，表示棧中沒有存儲任何數據元素，及棧是”空棧”。一旦有數據元素進棧，則 top 就做 +1 操作；反之，如果數據元素出棧，top 就做 -1 操作。
2. 鏈棧：採用鏈式存儲結構實現棧結構。通常我們將鏈表的頭部作為棧頂，尾部作為棧底，如下圖所示。將鏈表頭部作為棧頂的一端，可以避免在實現數據 “入棧” 和 “出棧” 操作時做大量遍歷鏈表的耗時操作。因此，鏈棧實際上就是一個只能採用頭插法插入或刪除數據的鏈表。

   
   

兩種實現方式的區別，僅限於數據元素在實際物理空間上存放的相對位置，順序棧底層採用的是數組，鏈棧底層採用的是鏈表。有關順序棧和鏈棧的具體實現會在後續章節中作詳細講解。

2.4 棧的應用

基於棧結構對數據存取採用 “先進後出” 原則的特點，它可以用於實現很多功能。
例如，我們經常使用瀏覽器在各種網站上查找信息。假設先瀏覽的頁面 A，然後關閉了頁面 A 跳轉到頁面 B，隨後又關閉頁面 B 跳轉到了頁面 C。而此時，我們如果想重新回到頁面 A，有兩個選擇：

• 重新搜索找到頁面 A；
• 使用瀏覽器的”回退”功能。瀏覽器會先回退到頁面 B，而後再回退到頁面 A。

瀏覽器 “回退” 功能的實現，底層使用的就是棧存儲結構。當你關閉頁面 A 時，瀏覽器會將頁面 A 入棧；同樣，當你關閉頁面 B 時，瀏覽器也會將 B入棧。因此，當你執行回退操作時，才會首先看到的是頁面 B，然後是頁面 A，這是棧中數據依次出棧的效果。
不僅如此，棧存儲結構還可以幫我們檢測代碼中的括號匹配問題。多數編程語言都會用到括號（小括號、中括號和大括號），括號的錯誤使用（通常是丟右括號）會導致程序編譯錯誤，而很多開發工具中都有檢測代碼是否有編輯錯誤的功能，其中就包含檢測代碼中的括號匹配問題，此功能的底層實現使用的就是棧結構。
同時，棧結構還可以實現數值的進制轉換功能。例如，編寫程序實現從十進制數自動轉換成二進制數，就可以使用棧存儲結構來實現。
以上也僅是棧應用領域的冰山一角，這裡不再過多舉例。在後續的學習中，我們會大量使用到棧結構。

3 隊列

3.1 隊列的基本概念

隊列，和棧一樣，也是一種對數據的”存”和”取”有嚴格要求的線性存儲結構。與棧結構不同的是，隊列的兩端都”開口”，要求數據只能從一端進，從另一端出，如下圖所示：

通常，稱進數據的一端為 “隊尾”，出數據的一端為 “隊頭”，數據元素進隊列的過程稱為 “入隊”，出隊列的過程稱為 “出隊”。

不僅如此，隊列中數據的進出要遵循 “先進先出” 的原則，即最先進隊列的數據元素，同樣要最先出隊列。拿圖 1 中的隊列來說，從數據在隊列中的存儲狀態可以分析出，元素 1 最先進隊，其次是元素 2，最後是元素 3。此時如果將元素 3 出隊，根據隊列 “先進先出” 的特點，元素 1 要先出隊列，元素 2 再出隊列，最後才輪到元素 3 出隊列。

棧和隊列不要混淆，棧結構是一端封口，特點是”先進後出”；而隊列的兩端全是開口，特點是”先進先出”。數據從表的一端進，從另一端出，且遵循 “先進先出” 原則的線性存儲結構就是隊列。
3.2 隊列的實現

隊列存儲結構的實現有以下兩種方式：

1. 順序隊列：在順序表的基礎上實現的隊列結構。由於順序隊列的底層使用的是數組，因此需預先申請一塊足夠大的內存空間初始化順序隊列。除此之外，為了滿足順序隊列中數據從隊尾進，隊頭出且先進先出的要求，我們還需要定義兩個指針（top 和 rear）分別用於指向順序隊列中的隊頭元素和隊尾元素，如下圖所示：

   

   由於順序隊列初始狀態沒有存儲任何元素，因此 top 指針和 rear 指針重合，且由於順序隊列底層實現靠的是數組，因此 top 和 rear 實際上是兩個變量，它的值分別是隊頭元素和隊尾元素所在數組位置的下標。當有數據元素進隊列時，對應的實現操作是將其存儲在指針 rear 指向的數組位置，然後 rear+1；當需要隊頭元素出隊時，僅需做 top+1 操作。

2. 鏈隊列：在鏈表的基礎上實現的隊列結構。鏈式隊列的實現思想同順序隊列類似，只需創建兩個指針（命名為 top 和 rear）分別指向鏈表中隊列的隊頭元素和隊尾元素，如下圖所示。

兩者的區別僅是順序表和鏈表的區別，即在實際的物理空間中，數據集中存儲的隊列是順序隊列，分散存儲的隊列是鏈隊列。

3.3 隊列的應用

實際生活中，隊列的應用隨處可見，比如排隊買 XXX、醫院的挂號系統等，採用的都是隊列的結構。
拿排隊買票來說，所有的人排成一隊，先到者排的就靠前，後到者只能從隊尾排隊等待，隊中的每個人都必須等到自己前面的所有人全部買票成功並從隊頭出隊後，才輪到自己買票。這就不是典型的隊列結構嗎？