一、棧的概述
和佇列一樣，棧是一種操作受限的線性表，和佇列不同的是棧只允許從一端插入和刪除資料。
因此，棧的特點是：
棧中的資料元素遵守“
先進後出
“（First In Last Out）的原則，簡稱FILO結構。
限定只能在棧頂進行插入和刪除操作，棧最重要的特徵
一些需要了解的概念：
棧頂與棧底：允許元素插入與刪除的一端稱為棧頂，另一端稱為棧底。
壓棧：棧的插入操作，叫做進棧，也稱壓棧、入棧。
彈棧：棧的刪除操作，也叫做出棧。
就像生活中我們取放盤子，當一摞盤子在桌子上時候，我們總是會取最上邊的盤子，同時，我們在放盤子時，也會放在最上面。其實，每個棧都有一個棧頂指標，它初始值為-1，且總是指向最後一個入棧的元素，棧有兩種處理方式，即進棧（push）和出棧（pop），因為在進棧只需要移動一個變數儲存空間，所以它的時間複雜度為O（1），但是對於出棧分兩種情況，棧未滿時，時間複雜度也為O（1），但是當棧滿時，需要重新分配記憶體，並移動棧內所有資料，所以此時的時間複雜度為O（n）。
棧有兩種儲存方式，即線性儲存和連結儲存（連結串列）。
二、棧的常用操作和實現
棧的常用操作有：
pop彈棧，向棧底新增一個元素
pop 壓棧，從棧頂取出一個元素
size 判定棧中所含元素的個數
isEmpty 判斷棧是否為空
peek 獲取棧頂元素的值，複製棧頂元素返回，但不進行刪除
1、線性儲存
線性儲存的方式和線性表基本一致，不同的是添加了後進先出的限制，並且是靜態分配的，即使用前，它的記憶體就已經以陣列的形式分配好了，所以在初始化時，需要指明棧的節點最大個數。基於陣列的棧是以陣列為底層資料結構的，通常以陣列頭為棧底，陣列頭到陣列尾為棧頂的生長方向。
public class MyStack { //大小 private int size； //棧的最大容量 private int maxSize； //預設最大容量10 private static final int DEFAULT_MAX_SIZE =10；/陣列（用來儲存資料）String［］ stack； //有參初始化，設定棧的最大容量 public MyStack（int maxSize） { this。maxSize=maxSize； stack =new String［maxSize］； } //無參初始化，設定棧的預設容量 public MyStack（） { this（DEFAULT_MAX_SIZE）； } //進行入棧操作 public void push（String s） { if（size >= maxSize） { throw new IndexOutOfBoundsException（”棧已經滿了！“）； } stack［size］ =s； size++； look（）； } //出棧操作 public String pop（） { String rs=stack［size-1］； //從後往前將做高位的值賦為null stack［size-1］=null； size——； look（）； return rs； } //清棧操作 public void clear（） { for（int i=0；i 2、連結儲存 對於單鏈表類，只要做適當的修改，限制其插入、刪除、修改和訪問結點的行為，使其符合棧先進後出的規則即可，另外需要單獨提供棧訪問的介面函式，例如進棧、出棧、獲取棧大小等。基於單鏈表的棧是以連結串列為底層的資料結構的，以連結串列頭為棧頂，便於節點的插入與刪除，壓棧產生的新節點將一直出現在連結串列的頭部 / * 棧的實現 * */public class MyStackNode { //大小 private int size； //棧的最大容量 private int maxSize； //預設最大容量10 private static final int DEFAULT_MAX_SIZE =10； //棧頂的節點 private Node top； //有參初始化，設定棧的最大容量 public MyStackNode（int maxSize） { this。maxSize=maxSize； } //無參初始化，設定棧的預設容量 public MyStackNode（） { this（DEFAULT_MAX_SIZE）； } //進行入棧操作 public void push（String s） { if（size >= maxSize） { throw new IndexOutOfBoundsException（”棧已經滿了！“）； } Node node=new Node（s，top）； top=node； look（）； size++； } //移除棧頂的元素 public String pop（） { if（top == null） return null； Node oldTop=top； Node newTop=top。next； String rs=oldTop。s； oldTop。next=null； oldTop。s=null； oldTop=null； top=newTop； look（）； size——； return rs； } //清棧操作 public void clear（） { Node node=top； while（node ！=null） { Node newTop=node。next； node。next=null； node。s=null； node =newTop； } look（）； size =0； } //新增一個Node內部類 class Node{ public String s； public Node next； public Node（String s，Node next） { this。s=s； this。next=next； } public void setNext（Node next） { this。next=next； } } //獲取棧的長度 public int getSize（） { return size； } //動態顯示棧中的資料 private void look（） { System。out。println（”“）； Node node=top； while（node ！=null） { System。out。print（node。s + ” “）； node=node。next； } } public static void main（String［］ args） { MyStackNode stack=new MyStackNode（4）； //MyStack stack=new MyStack（）； stack。push（”壹“）； stack。push（”貳“）； stack。push（”叄“）； stack。push（”肆“）； stack。pop（）； stack。pop（）； stack。push（”money“）； stack。push（”money“）； System。out。println（”當前棧的容量為：“ + stack。getSize（））； stack。clear（）； }}測試： 三、棧的應用場景 數制轉換 字元匹配 資料反轉 括號匹配檢驗 平衡符號的判斷 四、棧和佇列的區別 棧的插入和刪除操作都是在一端進行的，而佇列的操作卻是在兩端進行的。 棧是先進後出，佇列是先進先出。 棧只允許在表尾一端進行插入和刪除，佇列只允許在表尾一端進行插入，在表頭一端進行刪除。
