引導
????????今天我們開始學習棧與隊列的內容，我覺得棧并不難，所以篇幅也就不會那么多了。在虛擬空間中，棧是用戶空間中的一種數據結構，它主要用于保存局部變量。那么問題來了，為什么用棧來保存局部變量，不用別的數據結構呢？堆，數組，鏈表不可以嗎？
棧
????????我們知道棧的特點就是先進后出，后進先出。其實，我們可以這樣定義，滿足先進后出，后進先出操作特性的就是棧。因此棧沒有固定的存儲形式，比如數據是需要存儲地址連續，鏈表存儲地址可以不連續。棧可以用數組或鏈表都可以實現，只要它滿足先進后出，后進先出操作特性即可。
????????因此棧就是一個操作受限（只能從一端壓棧，出棧）的線性表。
棧的復雜度
????????棧的操作只有入棧和出棧，并且只涉及到棧頂的元素。所以它的復雜度都為O(1)。如圖：
棧的應用
????????特定的數據結構是對特定場景的抽象。那么有些問題用棧來處理肯定會比較方便。
棧在表達式中的使用
????????在《程序語言設計基礎》中有關于表達式知識點：比如一個3+5*8-6的表達式，你會怎么設計，讓計算機去識別，計算呢？記得以前寫過類似的程序，現在想想還有很多的優化空間。
????????在表達式中，有中綴表達式，前綴表達式，后綴表達式3種。它們的分析方式也不相同。有興趣的可以去了解一下我的另一篇文章【獻給過去的自己】棧實現計算器(C語言)-CSDN博客。
棧在函數調用中的應用
????????正如我們在開頭引入的話題，為什么局部變量要保存在棧中？這里有幾點需要解釋：
- 局部變量保存在棧中，這個棧是內存中實際存在的棧，是真實的物理區。而我們全文所介紹的棧是一個數據結構，是抽象的。要區分開兩個棧。
- 內存中的棧因為它的操作特性符合棧數據結構的特點，所以稱為棧區。棧區主要存儲運行方法的形參、局部變量、返回值。由系統自動分配和回收。
那么我們為什么要將局部變量保存在棧區呢?
????????其實我們并不是必須要使用棧結構，使用數組和鏈表也是可以的。可能稍微會麻煩點。函數之間調用，變化的主要是作用域及生命周期。
- 當A函數進入B函數，就不能再訪問A函數中的局部變量了。
- B函數返回A函數之后，B函數中的局部變量就需要釋放。
????????針對作用域和生面周期變化的，我覺得棧可以很好的實現。進入一個函數時，在棧中記錄入口（作用域界限），之后進行壓棧操作，在該函數內部只能訪問界限以內的數據。當退出函數時，將入口以內的數據直接釋放。
隊列
????????隊列和棧都是抽象的數據結構，是一個操作受限的線性表。它的特點就是先進先出（FIFO）。 它的操作又入隊（將一個數據放到隊尾）和出隊（從隊列頭部取出一個數據）。和棧相似，如圖：
順序隊列
????????隊列和棧一樣，都能用數組和鏈表來實現。用數組實現就是順序隊列，用鏈表實現就是鏈式隊列。我這里就簡單用C語言實現一個順序隊列。
| queue_len = 100 |
該實現方式，出隊和入隊操作的復雜度都是O(1)。
循環隊列
????????在上面的隊列中，當tail等于隊列長度時，就需要進行數據搬移。循環隊列就是省去了這個操作。循環隊列的難點就在于如何確定隊列滿和隊列空
- 隊列滿：(tail+1 % queue) == head
- 隊列空：head=tail
堆滿的判斷方式會浪費數組中一個元素。故循環隊列可按照下列實現：
| queue_len = 100 |
隊列的用途
????????隊列一般用于緩存操作。比如消息隊列，線程池等都是使用了隊列。但是隊列的大小設置是需要我們關注的。我個人主要的考慮依據是：在可接受的反應時間內，將隊列設置到最大。
總結
????????本節主要介紹了棧數據結構，它具有先進后出，后進先出的操作特點。以及棧的在表達式和函數調用上的應用。一定要區別棧數據結構和內存中的棧不是完全相同的概念。算是交際關系.
????????隊列的概念，并實現了隊列和循環隊列。以及隊列大小設置的依據。
)