目錄
Day 14：棧
一、棧的基本知識
二、棧的方法
1. 順序表實現棧
2. 入棧
3. 出棧?
三、代碼及測試
拓展：
小結?
Day 14：棧
Task：
- push 和 pop 均只能在棧頂操作.
- 沒有循環, 時間復雜度為 O(1).
一、棧的基本知識
? ? ? ? 詳細的介紹，可以參考這篇學習筆記：【數據結構】棧-CSDN博客。本博文中只選取部分知識點講解。
? ? ? ? 簡單來說，我們可以把棧理解成一種 “運算受限” 的線性表，即后進先出(Last In First Out，簡稱LIFO)或先進后出(First In Last Out，簡稱FILO)的原則進行的線性表，因此，棧又稱為LIFO表或FILO表。
? ? ? ? 對于棧這種數據結構的定位，我們可以從棧這個字本身出發。
????????“ 棧 ”是一個用于存儲貨物的房間，就像我們古代用于旅人駐腳歇店的客棧，人們不會在這久居，不過是中轉站罷了。
????????這個翻譯可謂很靈性了，計算機中的“ 棧 ”(Stack)也確實也可以理解為暫時存儲的容器。比如在函數調用時，底層編譯器會把我們當前的數據放于這個臨時的容器中存儲，避免在進入函數后當前上下文環境的信息丟失，之后，待到函數返回后再從Stack中取出。
????????當然，這種數據中轉存儲的數據類型我們不是說都稱之為棧，還包括有有隊列性質的高速緩存與各種正常的順序存儲的文件系統等，只是說棧有些獨有方面的特例。
二、棧的方法
1. 順序表實現棧
????????同時需要注意的一點，根據線性表的分類（順序表和鏈表）?，我們可以用這兩種方式來實現棧的構建，即分為順序棧和鏈棧。本博文中通過順序表來實現棧，具體構造原理可以參考學習筆記，這里不做展開。
/*** The depth.*/public static final int MAX_DEPTH = 10;/*** The actual*/int depth;/*** The data*/char[] data;/************************ Construct an empty char stack.**********************/public CharStack() {depth = 0;data = new char[MAX_DEPTH];}// Of the first constructor/************************ Overrides the method claimed in Object, the superclass of any class.**********************/public String toString() {String resultString = "";for (int i = 0; i < depth; i++) {resultString += data[i];} // Of for ireturn resultString;}// Of toString
????????這里的屬性與靜態順序表中的內容無差，構造函數完成棧深度（長度）初始化，空間開辟遵循靜態鏈表開辟的方法——使用new開辟固定“MAX_DEPTH”大小的空間。
????????但注意，棧是于棧頂一端進行刪除與插入的結構，而為了順序表的實現方便，我們往往在下標較大處插入，因此我們定義棧頂在數組的最右側。
????????所以，按照從左向右打印的習慣，toString()函數完成的就是棧底向棧頂的打印過程。
2. 入棧
????????本質上就是加入一個元素，只不過位置被限定在棧頂。
????????從順序表的角度來看，其意義就是在順序表的最后一個元素后面再插入一個元素。
? ? ? ? 由于位置固定，所以我們只需要給末尾元素之后的空位賦值并且讓棧深度+1即可（對于從0開始記錄的任何表，表長都默認值最后一個元素的下一個位置）
/************************ Push an element.* * @param paraChar The given char.* @return Success or not.**********************/public boolean push(char paraChar) {if (depth == MAX_DEPTH) {System.out.println("Stack full.");return false;} // Of ifdata[depth] = paraChar;depth++;return true;}// Of push
????????對于任何順序表的插入都不要忘記判斷表滿的情況，因此，這里先進行一次判滿的判斷，這是棧的基本健壯性保證。
????????之后的入棧操作怎么寫，要根據你的棧頂指針的默認指向來確定。
????????這里我們用depth來表示棧深度，同時，自然也用于表示棧頂指針。這種情況的話，depth默認指向的位置剛好就是尾元素后面的空位，剛好可以直接插入，于是可以使用：
data[depth] = paraChar;depth++;
????????我們可以做如下簡寫：
data[depth++] = paraChar;?????????當然，若棧頂指針假設指向末尾元素本身的話，這里我們假設這個變量為top。在插入元素時需要保證棧頂指針要先移動到末尾元素后面的空位才能進行插入，于是就要使用：
top++;data[top] = paraChar;
? ? ? ? ?當然，也可以簡寫成：
data[++top] = paraChar;????????習慣上，我們會將入棧操作定義為 Boolean 類型，這是因為布爾信息能夠明確的告訴我們該操作是否成功。
3. 出棧?
? ? ? ? 同順序表一樣，元素刪除需要先判斷是否為空，以保證程序的健壯性。
????????出棧時，使用resultChar先接收棧頂數據，之后再進行棧指針的下移操作，實現邏輯上元素減少（但是實際上這個值還是存放在原指針所指的位置的），因為我們確定棧元素的多少僅依靠棧頂指針的具體值而定。
????????這個操作與入棧的操作是完全相逆的，而且也會因為棧頂指針的含義不同而變化，即：棧頂指針指向棧頂有效元素的上方的一個無數據位，一般我們令其值為 -1。由于這里我們采用的是 depth（深度），所以最小值為0，但觀察可知，實際操作中讀取的 depth - 1，是等效的。
public char pop() {if (depth == 0) {System.out.println("Nothing to pop.");return '\0';} // Of ifchar resultChar = data[depth - 1];depth--;return resultChar;}// Of pop
三、代碼及測試
package datastructure.stack;/*** Char stack. I do not use Stack because it is already defined in Java.** @author: Changyang Hu joe03@foxmail.com* @date created: 2025-05-13*/
public class CharStack {/*** The depth.*/public static final int MAX_DEPTH = 10;/*** The actual depth.*/int depth;/*** The data*/char[] data;/************************ Construct an empty char stack.**********************/public CharStack() {depth = 0;data = new char[MAX_DEPTH];}// Of the first constructor/************************ Overrides the method claimed in Object, the superclass of any class.**********************/public String toString() {String resultString = "";for (int i = 0; i < depth; i++) {resultString += data[i];} // Of for ireturn resultString;}// Of toString/*** ********************** @Title: push* @Description: Push an element.** @param paraChar The given char.* @return Success or not.* @return boolean **********************/public boolean push(char paraChar) {if (depth == MAX_DEPTH) {System.out.println("Stack full.");return false;} // Of ifdata[depth] = paraChar;depth++;return true;}// Of push/*** ********************** @Title: pop* @Description: Pop an element.** @return The popped char.* @return char **********************/public char pop() {if (depth == 0) {System.out.println("Nothing to pop.");return '\0';} // Of ifchar resultChar = data[depth - 1];depth--;return resultChar;}// Of pop/*** ********************** @Title: main* @Description: The entrance of the program.** @param args Not used now.* @return void **********************/public static void main(String args[]) {CharStack tempStack = new CharStack();for (char ch = 'a'; ch < 'm'; ch++) {tempStack.push(ch);System.out.println("The current stack is: " + tempStack);} // Of for chchar tempChar;for (int i = 0; i < 12; i++) {tempChar = tempStack.pop();System.out.println("Poped: " + tempChar);System.out.println("The current stack is: " + tempStack);} // Of for i}// Of main}// Of CharStack
拓展：
? ? ? ? 棧：【數據結構】棧-CSDN博客
小結?
? ? ? ? 通過順序表來實現棧操作，本身并不復雜，只是說一些要點需要我們在使用前就想好：
- 采用 depth（指向棧頂的下一個元素）還是 top（指向棧頂）作為下標
- 采用順序表來實現還是鏈表（鏈表相關參考學習筆記）
? ? ? ? 棧雖然本身簡單，但是其在數據傳輸中的戰略地位極高。?
? ? ? ? 棧實現了“ 調用 ”思想的核心。棧的臨時存儲與棧出數據總是最近一次棧入的數據的特性非常符合嵌套調用與返回的特性。所以如今我們使用的各種函數都用到了棧的思想，任何使用函數完成的算法體系都可以使用棧完成模擬。
????????棧貫穿了計算機的各個鄰域，棧的概念在硬件中就早有使用，因為棧的實現，促成了操作系統的中斷特性的實現，而中斷的特性又促成后來批處理操作系統的誕生，是當代計算機的奠基石。也許毫不夸張說，沒有棧，就沒有我們如今的計算機的基礎。
文件)
