棧，也是一種特定的數據結構，生活中有大量類似棧結構的場景，所以我們對棧一定不陌生。棧主要的特點就是只能在一端操作數據，后進先出。

棧是一種操作受限的線性表，一開始接觸的時候我就在想，相比鏈表和數組，棧帶給我的只有限制，并沒有什么優勢，不如直接使用數組和鏈表。實際上，特定的數據結構對應特定的場景，數組和鏈表的確靈活，但也暴露了太多接口，容易出錯。所以當某個數據集合只涉及在一端插入和刪除數據，并且滿足后進先出、先進后出的特性，我們就應該首選“棧”這種數據結構。

棧的實現

棧涉及的操作就是入棧和出棧，也就是在棧頂插入一個數據和從棧頂刪除一個數據。
可以使用數組或鏈表來實現，下面是基于數組的棧。

public class StackArray {//數組private String[] items;//棧中元素個數private int count;//棧的大小private int n;public StackArray(int n){this.items = new String[n];this.n = n;this.count = 0;}/*** 往棧中放入一個元素*/public boolean push(String item){//如果棧中元素已經滿了，直接返回false。支持動態擴容的棧不常用，所以這里就實現不能擴容的棧了if(count == n){return false;}items[count++] = item;return true;}/*** 從棧中取出一個元素*/public String pop(){if(count == 0){return null;}//取出下標為count-1的元素，并且元素個數count減一return items[--count];}}

棧的應用

在函數調用中的應用

棧作為一個比較基礎的數據結構，應用場景還是蠻多的。其中，比較經典的一個應用場景就是函數調用棧。我們知道，操作系統給每個線程分配了一塊獨立的內存空間，這塊內存被組織成“棧”這種結構, 用來存儲函數調用時的臨時變量。每進入一個函數，就會將臨時變量作為一個棧幀入棧，當被調用函數執行完成，返回之后，將這個函數對應的棧幀出棧。為了讓你更好地理解，我們一塊來看下這段代碼的執行過程。

int main() {int a = 1; int ret = 0;int res = 0;ret = add(3, 5);res = a + ret;printf("%d", res);reuturn 0; }int add(int x, int y) {int sum = 0;sum = x + y;return sum; }

從代碼中我們可以看出，main() 函數調用了 add() 函數，獲取計算結果，并且與臨時變量 a 相加，最后打印 res 的值。為了讓你清晰地看到這個過程對應的函數棧里出棧、入棧的操作，下圖中顯示的是，在執行到 add() 函數時，函數調用棧的情況。

棧在表達式求值中的應用

編譯器就是通過兩個棧來實現的。其中一個保存操作數的棧，另一個是保存運算符的棧。我們從左向右遍歷表達式，當遇到數字，我們就直接壓入操作數棧；當遇到運算符，就與運算符棧的棧頂元素進行比較。如果比運算符棧頂元素的優先級高，就將當前運算符壓入棧；如果比運算符棧頂元素的優先級低或者相同，從運算符棧中取棧頂運算符，從操作數棧的棧頂取 2 個操作數，然后進行計算，再把計算完的結果壓入操作數棧，繼續比較。
將 3+5*8-6 這個表達式的計算過程畫成了一張圖來理解計算過程。

逆波蘭表達式計算法

棧在括號匹配中的應用

/*** 假設表達式中只包含三種括號字符，圓括號 ()、方括號[]和花括號{}，并且它們可任意嵌套。比如，{[] ()[{}]}或[{()}([])]等都為合法格式，* 而{[}()]或[({)]為不合法的格式。現在給你一個包含三種括號的表達式字符串，如何檢查它是否合法呢？*/public static boolean match(String str){if(str == null || str.length() == 1){return false;}StackArray stack = new StackArray(str.length());//開始掃描字符串for(char c : str.toCharArray()){String s = new String(new char[]{c});//遇到左括號的時候，就壓入棧if("{".equals(s) || "[".equals(s) || "(".equals(s)){stack.push(s);//遇到右括號的時候，就和棧頂元素進行比較}else if("}".equals(s) || "]".equals(s) || ")".equals(s)){String left = stack.pop();//看是否匹配boolean match = ("}".equals(s) && "{".equals(left))|| ("]".equals(s) && "[".equals(left))|| (")".equals(s) && "(".equals(left));//如果匹配就繼續掃描，如果不匹配就直接返回falseif (!match){return false;}}}if(stack.size() != 0){return false;}return true;}

棧來實現瀏覽器的前進、后退功能

用兩個棧就可以非常完美地解決這個問題。我們使用兩個棧，X 和 Y，我們把首次瀏覽的頁面依次壓入棧 X，當點擊后退按鈕時，再依次從棧 X 中出棧，并將出棧的數據依次放入棧 Y。當我們點擊前進按鈕時，我們依次從棧 Y 中取出數據，放入棧 X 中。當棧 X 中沒有數據時，那就說明沒有頁面可以繼續后退瀏覽了。當棧 Y 中沒有數據，那就說明沒有頁面可以點擊前進按鈕瀏覽了。

總結

以上是生活随笔為你收集整理的（三）栈的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。