【0. 引子】
大家好，歡迎來到本期的資料結構教學。今天，我們要聊的是棧（Stack），這個神奇而又有趣的資料結構。棧無處不在，它的應用涉及到各個領域，從計算機科學到日常生活。無論你是程式設計新手還是經驗豐富的開發者，本文都會給你帶來新的認識和啟發。
【1. 回顧上一章節】
在上一章節(歪說基礎算法1-2：數組，資料結構中的萬能武器！)，我們學習了數組和它的各種操作。數組是一種線性資料結構，而棧則是一種具有特定特性的線性資料結構。如果你還記得數組的概念和基本操作，那麼了解棧将更加輕松。
【2. 棧的概念和特性】
棧是一種遵循後進先出（Last-In-First-Out，LIFO）原則的資料結構。就像是我們生活中的一個堆疊的盤子，我們隻能從最頂端取出或放入盤子。棧具有以下幾個特性：
- 入棧（Push）：将元素添加到棧的頂部。
- 出棧（Pop）：從棧的頂部移除元素。
- 棧頂（Top）：指向棧頂的元素。
- 空棧（Empty）：棧中沒有任何元素。
【3. 棧的實作方式】
棧可以使用兩種主要的實作方式：數組和連結清單。
【數組實作】 數組實作的棧使用一個固定大小的數組來存儲元素。通過一個指針來表示棧頂元素的位置。入棧操作會将元素添加到數組的末尾，并将棧頂指針向上移動；出棧操作會将棧頂指針向下移動，并移除棧頂元素。數組實作的棧簡單高效，但容量有限。
在這個示例代碼中，我們使用一個固定大小的數組來實作棧。通過維護一個指針 top 來表示棧頂元素的位置。push 操作将元素添加到棧頂，pop 操作将棧頂元素移除，peek 操作傳回棧頂元素，isEmpty 操作用于檢查棧是否為空。
【連結清單實作】 連結清單實作的棧使用連結清單結構存儲元素。每個節點包含一個資料項和一個指向下一個節點的指針。入棧操作會建立一個新節點，并将其設定為新的棧頂；出棧操作會移除棧頂節點，并将棧頂指針指向下一個節點。連結清單實作的棧靈活且無容量限制，但相對于數組實作，會消耗更多的記憶體空間。
在這個示例代碼中，我們使用連結清單來實作棧。連結清單中的每個節點包含一個整數值和一個指向下一個節點的指針。push 操作将新的節點添加到連結清單的頭部，表示新的棧頂元素；pop 操作将連結清單頭部的節點移除；peek 操作傳回連結清單頭部節點的值，即棧頂元素；isEmpty 操作用于檢查棧是否為空。
通過使用數組和連結清單來實作棧，我們可以根據實際需求選擇适合的實作方式。數組實作的棧具有固定的容量，而連結清單實作的棧可以動态擴充。根據具體場景和需求，我們可以選擇合适的實作方式來應用棧的概念。
【4. 棧的應用場景】
棧在計算機科學中有許多應用場景，下面我們介紹兩個常見的應用。
【遞歸】 遞歸是一種函數調用自身的技術。在遞歸過程中，棧被用于儲存每次遞歸調用的狀态。當遞歸函數被調用時，它将目前的狀态（包括局部變量和傳回位址）入棧，并在遞歸結束時從棧中恢複狀态。遞歸是一種強大的工具，它在解決許多問題時非常有效。
下面是一個經典的遞歸示例，計算斐波那契數列的第n個數字：
在這個遞歸函數中，每次遞歸調用都會将目前的狀态儲存在棧中，并等待後續的遞歸調用完成後再從棧中恢複。
【括号比對】 括号比對是指檢查表達式中的括号是否比對和嵌套正确。例如，"(())"是合法的括号比對，而"())("則是非法的。棧可以用于解決括号比對問題。我們周遊表達式中的每個字元，如果遇到左括号，就将其入棧；如果遇到右括号，就将棧頂元素出棧，并檢查其是否與目前右括号比對。如果周遊完整個表達式後，棧為空，則說明括号比對正确。
下面是一個使用棧進行括号比對的示例代碼：
【5. 棧的實作原理與僞代碼示範】
棧的實作原理非常簡單，我們可以使用僞代碼進行示範：
【6. 簡單案例及代碼解析】
現在，我們來看一個簡單的棧應用案例：将一個字元串反轉。我們可以使用棧來實作這個功能。具體代碼如下：
以上就是一個簡單的棧應用案例，我們将字元串中的字元入棧，然後再依次出棧構成反轉後的字元串。這個案例展示了棧在字元串進行中的應用。
【結語】
通過本文的介紹，我們深入淺出地了解了棧的概念、特性、實作方式以及應用場景。棧作為一種重要的資料結構，在計算機科學中發揮着重要的作用。希望本文能夠幫助你對棧有更深入的了解，并激發你對資料結構和算法的興趣。