目錄
棧存儲結構詳解
進棧和出棧
棧的具體實現
棧的應用
什么是隊列（隊列存儲結構）
棧存儲結構詳解
同順序表和鏈表一樣，棧也是用來存儲邏輯關系為 "一對一" 數據的線性存儲結構，如圖 1 所示。
?
圖 1 棧存儲結構示意圖
從圖 1 我們看到，棧存儲結構與之前所學的線性存儲結構有所差異，這緣于棧對數據 "存" 和 "取" 的過程有特殊的要求：
- 棧只能從表的一端存取數據，另一端是封閉的，如圖 1 所示；
- 在棧中，無論是存數據還是取數據，都必須遵循"先進后出"的原則，即最先進棧的元素最后出棧。拿圖 1 的棧來說，從圖中數據的存儲狀態可判斷出，元素 1 是最先進的棧。因此，當需要從棧中取出元素 1 時，根據"先進后出"的原則，需提前將元素 3 和元素 2 從棧中取出，然后才能成功取出元素 1。
因此，我們可以給棧下一個定義，即棧是一種只能從表的一端存取數據且遵循 "先進后出" 原則的線性存儲結構。
通常，棧的開口端被稱為棧頂；相應地，封口端被稱為棧底。因此，棧頂元素指的就是距離棧頂最近的元素，拿圖 2 來說，棧頂元素為元素 4；同理，棧底元素指的是位于棧最底部的元素，圖 2 中的棧底元素為元素 1。
?
圖 2 棧頂和棧底
進棧和出棧
基于棧結構的特點，在實際應用中，通常只會對棧執行以下兩種操作：
- 向棧中添加元素，此過程被稱為"進棧"（入棧或壓棧）；
- 從棧中提取出指定元素，此過程被稱為"出棧"（或彈棧）；
棧的具體實現
棧是一種 "特殊" 的線性存儲結構，因此棧的具體實現有以下兩種方式：
- 順序棧：采用順序存儲結構可以模擬棧存儲數據的特點，從而實現棧存儲結構；
- 鏈棧：采用鏈式存儲結構實現棧結構；
兩種實現方式的區別，僅限于數據元素在實際物理空間上存放的相對位置，順序棧底層采用的是數組，鏈棧底層采用的是鏈表。有關順序棧和鏈棧的具體實現會在后續章節中作詳細講解。
棧的應用
基于棧結構對數據存取采用 "先進后出" 原則的特點，它可以用于實現很多功能。
例如，我們經常使用瀏覽器在各種網站上查找信息。假設先瀏覽的頁面 A，然后關閉了頁面 A 跳轉到頁面 B，隨后又關閉頁面 B 跳轉到了頁面 C。而此時，我們如果想重新回到頁面 A，有兩個選擇：
- 重新搜索找到頁面 A；
- 使用瀏覽器的"回退"功能。瀏覽器會先回退到頁面 B，而后再回退到頁面 A。
瀏覽器 "回退" 功能的實現，底層使用的就是棧存儲結構。當你關閉頁面 A 時，瀏覽器會將頁面 A 入棧；同樣，當你關閉頁面 B 時，瀏覽器也會將 B入棧。因此，當你執行回退操作時，才會首先看到的是頁面 B，然后是頁面 A，這是棧中數據依次出棧的效果。
不僅如此，棧存儲結構還可以幫我們檢測代碼中的括號匹配問題。多數編程語言都會用到括號（小括號、中括號和大括號），括號的錯誤使用（通常是丟右括號）會導致程序編譯錯誤，而很多開發工具中都有檢測代碼是否有編輯錯誤的功能，其中就包含檢測代碼中的括號匹配問題，此功能的底層實現使用的就是棧結構。
同時，棧結構還可以實現數值的進制轉換功能。例如，編寫程序實現從十進制數自動轉換成二進制數，就可以使用棧存儲結構來實現。
什么是隊列（隊列存儲結構）
隊列，和棧一樣，也是一種對數據的"存"和"取"有嚴格要求的線性存儲結構。
與棧結構不同的是，隊列的兩端都"開口"，要求數據只能從一端進，從另一端出，如圖 1 所示：
?
圖 1 隊列存儲結構
通常，稱進數據的一端為 "隊尾"，出數據的一端為 "隊頭"，數據元素進隊列的過程稱為 "入隊"，出隊列的過程稱為 "出隊"。
不僅如此，隊列中數據的進出要遵循 "先進先出" 的原則，即最先進隊列的數據元素，同樣要最先出隊列。拿圖 1 中的隊列來說，從數據在隊列中的存儲狀態可以分析出，元素 1 最先進隊，其次是元素 2，最后是元素 3。此時如果將元素 3 出隊，根據隊列 "先進先出" 的特點，元素 1 要先出隊列，元素 2 再出隊列，最后才輪到元素 3 出隊列。
棧和隊列不要混淆，棧結構是一端封口，特點是"先進后出"；而隊列的兩端全是開口，特點是"先進先出"。
因此，數據從表的一端進，從另一端出，且遵循 "先進先出" 原則的線性存儲結構就是隊列。
隊列存儲結構的實現有以下兩種方式：
- 順序隊列：在順序表的基礎上實現的隊列結構；
- 鏈隊列：在鏈表的基礎上實現的隊列結構；
兩者的區別僅是順序表和鏈表的區別，即在實際的物理空間中，
- 數據集中存儲的隊列是順序隊列
- 分散存儲的隊列是鏈隊列
實際生活中，隊列的應用隨處可見，比如排隊買 XXX、醫院的掛號系統等，采用的都是隊列的結構。
拿排隊買票來說，所有的人排成一隊，先到者排的就靠前，后到者只能從隊尾排隊等待，隊中的每個人都必須等到自己前面的所有人全部買票成功并從隊頭出隊后，才輪到自己買票。這就不是典型的隊列結構嗎？
?
?
