【導讀：數據是二十一世紀的石油，蘊含巨大價值，這是·情報通·大數據技術系列第[148]篇文章，歡迎閱讀收藏】
1 基本概念
棧 (Stack) 是一種後進先出 (last in first off ， LIFO) 的數據結構，而隊列 (Queue) 則是一種先進先出 (fisrt in first out ， FIFO) 的結構。
2 術語解釋
對於棧而言，允許進行插入，刪除操作的一端被稱為 棧頂（ top ） , 另一端則被稱為 棧底（ bottom ） 。
如果一個棧不包含任何元素，那麼這個棧就被稱為 空棧 。
從棧頂插入一個元素被稱為 入棧（ push ） ，將一個元素從棧頂刪除被稱為 出棧（ pop ）
對於隊列而言，只允許在表的 前端 (front) 進行刪除操作，只允許在表的 後端（ rear ） 進行插入操作，進行插入操作的端稱為 隊尾 ，進行刪除的端稱為
對頭 。如果隊列中不包含任何元素，該隊列就被稱為 空隊列 。
對於一個隊列來說，每個元素總是從隊列的 rear 端進入隊列，然後等待該與元素之前的所有元素出對之後，當前元素才能出對。
3 詳細說明
3.1 棧的順序存儲結構及實現
順序存儲結構的棧簡稱為順序棧，它利用一組地址連續的存儲單元依次存放從棧底到棧頂的數據元素。棧底位置固定不變，它的棧頂可以直接通過順序棧底層數組的數組元素 arr[size-1] 來訪問。
順序棧中數據元素的物理關係和邏輯關係是一致的，先進棧的元素位於棧底，棧底元素的存儲位置相對也比較小。
進棧
對於順序棧的進棧操作而言，只需將新的數據元素存入棧內，然後讓記錄棧內元素個數的變量加 1 ，程序即可再次通過 arr[size-1] 重新訪問新的棧頂元素。進棧操作示意圖如下：
由於順序棧底層通常會採用數組來保存數據元素，因此可能出現的情況是：當程序試圖讓一個數據元素進棧時，底層數據已滿，那麼就必須擴充底層數組的長度來容納新進棧的數據元素。
出棧
對於順序棧的出棧操作而言，需要將棧頂元素彈出棧，程序要做兩件事。
讓記錄棧內元素個數的變量減 1.
釋放數組對棧頂元素的引用。
出棧操作示意圖如下圖 :
對於刪除操作來說，只要讓記錄棧內元素個數的 size 減 1 ，程序即可通過 arr[size-1] 訪問到新的棧頂元素。但不要忘記釋放原來棧頂的數組引用，否則會引起內存洩漏。
棧比普通線性表的功能更弱，棧時一種被限制過的線性表，只能從棧頂插入，刪除數據元素。
3.2 棧的鏈式存儲結構及實現
程序可以採用單鏈表來保存棧中所有元素，這種鏈式結構的棧也被稱為棧鏈。對於棧鏈而言，棧頂元素不斷地改變，程序只要使用一個 top 引用來記錄當前的棧頂元素即可。 top 引用變量永遠引用棧頂元素，再使用一個 size 變量記錄當前棧中包含多少個元素即可。
3.3 隊列的順序存儲結構及實現
系統採用一組地址連續的存儲單元依次存放隊列從 rear 端到 front 端的所有數據元素，程序只需 (front 和 rear 兩個整型變量來記錄隊列 front 端的元素索引、 rear 端的元素索引。
3.4 隊列的鏈式存儲結構及實現
使用鏈式結構保存線性表，也可以採用鏈式結構來存儲隊列的各元素，採用鏈式存儲結構的隊列也被稱為鏈隊列。
對於鏈隊列而言，由於程序需要從 rear 端添加元素，然後從 front 端移除元素，因此考慮對鏈隊列增加 front,rear 兩個引用變量，使他們分別執行鏈隊列的頭，尾兩個節點。
閱讀更多 情報通 的文章
