棧是一種特殊的列表，棧内的元素隻能通過列表的一端訪問，這一端稱為棧頂。就像咖啡廳内的一摞盤子是現實世界中常見的棧的例子。隻能從最上面取盤子，盤子洗淨後，也隻能摞在這一摞盤子的最上面。棧的基本操作有push()和pop()、peek()。所以棧又被稱為LIFO表。堆與棧是C/C 語言内存管理和編譯優化時使用的，在Python裡，遞歸層次太多，要改用堆棧，而不能用遞歸。

由于棧具有後入先出的特點，所以任何不在棧頂的元素都無法訪問。為了得到棧底的元素，必須先拿掉上面的元素。

入棧和出棧的過程

1. pop()方法雖然可以訪問棧頂的元素，但是調用該方法後，棧頂元素也從棧中被永久性地删除了。

2. peek()方法則隻返回棧頂元素，而不删除它。

為了記錄棧頂元素的位置，同時也為了标記哪裡可以加入新元素，我們使用變量top，當向棧内壓入元素時，該變量增大；從棧内彈出元素時，該變量減小。

簡單案例以及操作結果：

這裡使用python的list對象模拟棧的實現：

棧應用

• 檢查程序中成對的符号

用棧來檢查符号是否成對。做一個空棧，如果字符是開放符号('({[')則将其push棧中。如果符号是個閉合符号(')]}'),則當棧空時報錯，對應'()}'的錯誤。否則，将棧pop，如果彈出的符号不是對應的開放符号，則報錯，對應'(}'的錯誤。文件末尾，如果棧為空，則報錯，對應'({}'的錯誤。

• 進制轉換

十進制轉換二進制：把十進制轉成二進制一直分解至商數為0。從最底左邊數字開始讀，之後讀右邊的數字，從下讀到上。

• 後綴記法

使用一個棧，見到一個數時入棧，遇到一個運算符時就作用于從棧彈出的兩個元素，将結果彈入棧中。中綴到後綴的轉換：當讀到一個操作數的時候，放到輸出中。讀到操作符( ,-,*,/)時，如果棧為空，則壓入棧中，否則彈出棧元素放到輸出中直到發現優先級更低的元素為止。讀到'(',壓入棧中，讀到')',彈出棧元素并發到輸出中直到發現'('為止。

隊列其實就是一種列表，不同的是隊列隻能在隊尾插入元素，在隊首删除元素。隊列用于存儲按順序排列的數據，先進先出，這點和棧不一樣。

PS：說一下在Python2.X的版本中隊列模塊是queue，而Python3.X中的隊列模塊是queue，所以導入模塊的時候請注意自己的Python環境

• 一個線性的數據結構

• 隊列遵循FIFO的原則

• 隊列頭部為front，尾部為rear

隊列操作舉例

class queue.Queue(maxsize=0)

Queue提供了一個基本的FIFO容器，使用方法很簡單,maxsize是個整數，指明了隊列中能存放的數據個數的上限。一旦達到上限，插入會導緻阻塞，直到隊列中的數據被消費掉。如果maxsize小于或者等于0，隊列大小沒有限制。

class queue.LifoQueue(maxsize=0)

後進先出隊列與棧的類似，使用也很簡單

queue常用方法

講到這裡其實還有一種優先隊列，小編留一個懸念，希望時刻關注小編，定期更新，點關注不迷路