一、棧的定義

【百度百科】棧作為一種數據結構，是一種只能在一端進行插入和刪除操作的特殊線性表。它按照先進後出的原則存儲數據，先進入的數據被壓入棧底，最後的數據在棧頂，需要讀數據的時候從棧頂開始彈出數據（最後一個數據被第一個讀出來）。棧具有記憶作用，對棧的插入與刪除操作中，不需要改變棧底指針。

棧是允許在同一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動；棧中元素個數為零時稱為空棧。插入一般稱為進棧（PUSH），刪除則稱為退棧（POP）。棧也稱為後進先出表。

由於堆疊數據結構只允許在一端進行操作，因而按照後進先出（LIFO, Last In First Out）的原理運作。棧也稱為後進先出表。

二、棧的示意圖

三、棧的實現方式

棧可以用順序存儲，也可以用鏈式存儲，分別稱為順序棧和鏈棧。

四、Java中棧的實現舉例

1.利用棧實現字元串逆序

    @Test
    public void testStringReversal(){
        Stack stack=new java.util.Stack();
        String str="Hello World!";
        
        char[] chars = str.toCharArray();
        for (char c : chars) {
            stack.push(c);
        }
        
        while (!stack.isEmpty()) {
            System.out.print(stack.pop());
        }

    }

2.用棧實現括弧匹配

假設表達式中只允許兩種括弧：()、{}；
正確表達順序為：()或{}或({})或{({}{})}的形式；如{(}或(})或({)}的表達形式均不對。
演算法的設計思想：

　　1）出現左括弧則進棧；

　　2）出現右括弧則首先檢測棧是否為空；

• 　　　　若棧空則表明此右括弧多餘，表達式不匹配。
• 　　　　否則和棧頂數據比較，若匹配則棧頂出棧。
• 　　　　否則表明表達式不匹配；

　　3）最後若棧空，則表明匹配成功；否則表明不匹配。

/**
 * 此題還可以引申至配對字元符匹配問題，如單引號，雙引號匹配問題。
 */
public class ExpStackMatching {
    public boolean matching(String expression) {
        if (expression == null || expression == "") {
            System.out.println("輸入表達式為空或沒有輸入表達式");
        }
        Stack<Character> stack = new java.util.Stack<Character>();
        for (int index = 0; index < expression.length(); index++) {
            switch (expression.charAt(index)) {
                case '(':
                    stack.push(expression.charAt(index));
                    break;
                case '{':
                    stack.push(expression.charAt(index));
                    break;
                case ')':
                    if (!stack.empty() && stack.peek() == '(') {
                        stack.pop();
                    }
                    break;

                case '}':
                    if (!stack.empty() && stack.peek() == '{') {
                        stack.pop();
                    }
            }
        }

        if (stack.empty())
            return true;
        return false;
    }
    public static void main(String[] args) {
        String expression = "{((1+3)+2+4)+9*7}";
        ExpStackMatching oj = new ExpStackMatching();
        boolean flag = oj.matching(expression);
        if (flag) {
            System.out.println("匹配成功！");
        } else {
            System.out.println(" 匹配失敗 ");
        }
    }
}

五、棧的位元組碼解析

六、我們使用過的棧

1. Struts2的ValueStack(值棧)
2. 使用棧實現瀏覽器的前進和後退

七、棧的總結

棧是一個概念上的工具，具體能實現什麼功能可以由我們去想象。棧通過提供限制性的訪問方法push()和pop()，使得程式不容易出錯。

對於棧的實現，我們稍微分析就知道，數據入棧和出棧的時間複雜度都為O(1)，也就是說棧操作所耗的時間不依賴棧中數據項的個數，因此操作時間很短。而且需要註意的是棧不需要比較和移動操作，我們不要畫蛇添足。

我的微信公眾號：架構真經（id：gentoo666），分享Java乾貨，高併發編程，熱門技術教程，微服務及分散式技術，架構設計，區塊鏈技術，人工智慧，大數據，Java面試題，以及前沿熱門資訊等。每日更新哦！

參考文章

1. https://blog.csdn.net/weixin_41362649/article/details/81660908
2. https://www.cnblogs.com/ysocean/p/7911910.html
3. https://www.cnblogs.com/rrttp/p/7913091.html