數據結構與算法系列——棧

什麼是棧

棧是一種運算受限制的線性表，只允許在表的一端進行插入和刪除操作。這一端被稱為棧頂，另一端被稱為棧底。向一個棧中插入新數據叫做進棧、入棧或者壓棧，是把新元素放到棧頂上邊，使其成為新的棧頂元素；刪除數據叫做出棧或者退棧，就是把棧頂的元素刪掉，使其下邊的元素稱為新的棧頂元素。

舉一個容易理解的例子，就是有一摞盤子，我們用的時候從上往下一個一個取，放的時候都是從下往上一個一個放，一般不從中間取或者放。這種先進後出，後進先出的數據結構就是棧。

這種操作受限的數據結構在什麼情況下用呢，我們為什麼不能用操作更為方便的數組或者鏈表呢。當某個數據只涉及在一端的插入和刪除數據，並滿足先進後出，後進先出的特點，我們就可以用棧這種數據結構，而數組和鏈表因為操作的靈活性，有時候會使一些數據不可控，更容易出現錯誤。

棧的實現

從功能上，我們是可以用數組和鏈表來實現棧，只要實現棧的入棧和出棧的操作，即從棧頂插入新的數據，從棧頂刪除數據。用數組實現的棧叫做順序棧，用鏈表實現的棧叫做鏈表棧。下邊我們分別看一下用數組和鏈表實現棧的代碼。這裡用Java代碼實現。

• 數組實現

//基於數組實現的棧
public class ArrayStack{
 //數組
 private String[] items;
 //棧的大小
 private int length;
 //棧中元素的個數
 private int count;
 public ArrayStack(int len){
 items = new String[len];
 length = len;
 count = 0;
 }
 //入棧
 public boolean Push(String x){
 //數組空間不足
 if(count == length){
 return false;
 }
 items[count] = x;
 count++;
 return true;
 }
 //出棧
 public String Pop(){
 //棧為空
 if(count == 0){
 return null;
 }
 String tem = items[count-1];
 count--;
 return tem;
 }
}

• 鏈表實現

//基於鏈表實現的棧 

public class ListNodeStack {
 private ListNode top;
 //進棧
 public void Push(int val) {
 ListNode node = new ListNode(val, null);
 if (top == null) {
 top = node;
 } else {
 node.next = top;
 top = node;
 }
 }
 //出棧
 public int Pop() {
 if (top == null) {
 return -1;
 }
 int val = top.val;
 top = top.next;
 return val;
 }
 //鏈表的結點
 class ListNode {
 private int val;
 private ListNode next;
 public ListNode(int x, ListNode next) {
 val = x;
 this.next = next;
 }
 public int GetValue() {
 return val;
 }
 }
}

上邊代碼用數組實現的棧是一個固定大小的棧，當棧滿了之後就沒法辦插入新的數據了，那麼我們能不能用數組實現一個動態擴容的棧呢？前邊我們將數組的時候說過，實現一個動態擴容的數組，是在數組滿了的時候，我們重新創建一個大小為原來兩倍的數組，然後把原來數組的數據拷貝到新的數組中，所以我們也可以用這個方法來實現一個動態擴容的棧。我們看一下代碼實現。

//基於數組實現的棧
public class ArrayStack {
 //數組
 private String[] items;
 //棧的大小
 private int length;
 //棧中元素的個數
 private int count;
 public ArrayStack(int len) {
 items = new String[len];
 length = len;
 count = 0;
 }
 //入棧
 public void Push(String x) {
 //數組空間不足
 if (count == length) {
 DilatationArray();
 }
 items[count] = x;
 count++;
 }
 //出棧
 public String Pop() {
 //棧為空
 if (count == 0) {
 return null;
 }
 String tem = items[count - 1];
 count--;
 return tem;
 }
 //數組擴容
 private void DilatationArray() {
 String[] newArray = new String[length * 2];
 for (int i = 0; i < length; i++) {
 newArray[i] = items[I];
 }
 items = newArray;
 }
}

棧的實際應用

1. 在函數調用中的應用

在Java的虛擬機中有一個內存區域被稱為虛擬機棧。每個方法在執行的時候都會創建一個“棧幀”。用來存儲局部變量表（包括參數）、操作棧、動態鏈接、方法出口等信息。每個方法從調用到結束就會有棧幀在虛擬機棧中入棧和出棧。

舉一個簡單的例子。

public class AddClass{
 public int Main(){
 int a = 0;
 int b = 5;
 int c = 0;
 a = Add(2, 3);
 c = a + b;
 return c;
 }
 public int Add(int x, int y){
 int sum = 0;
 sum = x + y;
 return sum;
 }
}

從代碼中我們看到 Main 方法中首先聲明瞭幾個變量，然後調用了 Add 方法，然後經過一些運算，最後返回一個值。我們畫圖來更直觀的看一下這個過程。

image.png

1. 在表達式求值中的應用

編輯器的表達式求值的過程，就是用棧來實現的。我們舉一個簡單的四則運算的表達式的求值過程來看一下。例如：1+2*3-4/2。編輯器是怎麼計算來得到最後的值呢。

這個求值過程，編輯器是用兩個棧來實現的，一個保存數字的棧，一個保存運算符號的棧。我們從左向右遍歷表達式，當遇到數字的時候把它壓入數字棧，當遇到運算符號的時候，就與運算符棧的棧頂的運算符比較，如果比棧頂的運算符優先級高，就直接壓入運算符棧，如果比棧頂的運算符優先級低或者相同，那麼就從運算符棧取出棧頂運算符號，從數字棧中取出兩個數字進行計算，然後把結果壓入數字棧，然後繼續比較，依次類推，知道最後。

我們為了更形象的理解，也用畫圖的方式來展示一下這個過程。

image.png

1. 在各種前進後退操作中的應用

我們在各中編輯器的撤銷和恢復操作，瀏覽器中的前進和後退操作，都是用棧來實現的。

我們用兩個棧 A 和 B，當我們執行操作的時候把我們的每一個操作依次壓入 A 棧中，當我們執行後退的操作時，依次從 A 棧中取出，然後壓入 B 棧中，當執行前進操作的時候，依次從 B 棧中取出，然後壓入 A 棧中。

比如我們依次執行了 a，b，c 操作，我們依次把 a，b，c 壓入 A 棧。如圖

image.png

假如我們現在想要撤銷 c 和 b 操作。那麼它就是這樣的。

image.png

假如我又想恢復操作 b

image.png

這個時候我繼續執行新的操作 d，那麼無論前進後退我們都無法再回到操作 c 了，所以我們應該清空 B 棧。

image.png