利用Stack函數實現先進後出數據結構

Stack(棧)是一種常用的數據結構，它可以用於實現許多算法和函數。在Java中，可以通過java.util.Stack類來實現棧。當需要LIFO（Last-In-First-Out）數據結構時，可以使用Stack。

一、Stack的基本操作

在Java中，Stack類是Vector的一個子類。除了由Vector提供的全部操作之外，Stack還提供了自己的push、pop、empty等方法。其中，push方法用於入棧，pop方法用於出棧，empty方法用於判斷棧是否為空。下面是Stack的基本操作的代碼示例。

    Stack stack = new Stack();
    stack.push(1); //入棧
    stack.push(2);
    stack.push(3);
    
    while (!stack.empty()) { //判斷棧是否為空
        System.out.println(stack.pop()); //出棧
    }

在以上示例代碼中，聲明了一個Stack對象並將元素1、2、3入棧，然後通過while循環不斷將棧頂元素出棧並打印，直到棧為空。

二、Stack的應用1：括號匹配

括號匹配是棧最常見的應用之一。對於一個字符串，如果其中的括號全部是匹配的，那麼就可以認為它是一個合法的表達式。可以使用Stack來檢查一個字符串中的括號是否匹配。

    public static boolean isMatch(String s) {
        Stack stack = new Stack();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
                stack.pop();
            } else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
                stack.pop();
            } else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
                stack.pop();
            } else {
                return false;
            }
        }
        return stack.isEmpty();
    }

在以上示例代碼中，isMatch方法使用Stack來判斷字符串s中的括號是否匹配。遇到左括號就入棧，遇到右括號就判斷它和棧頂元素是否匹配。如果匹配，則將棧頂元素出棧；如果不匹配，則說明括號不匹配，返回false。最後，如果棧為空，則說明括號全部匹配，返回true。

三、Stack的應用2：逆波蘭表達式求解

逆波蘭表達式（Reverse Polish Notation，簡稱RPN）也稱後綴表達式。它將運算符寫在操作數（即數字）的後面，使得整個表達式沒有括號，從而避免了表達式的歧義。可以用Stack來求解逆波蘭表達式。

    public static int evalRPN(String[] tokens) {
        Stack stack = new Stack();
        for (String token : tokens) {
            if (token.equals("+")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a + b);
            } else if (token.equals("-")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a - b);
            } else if (token.equals("*")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a * b);
            } else if (token.equals("/")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a / b);
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }

在以上示例代碼中，evalRPN方法使用Stack來求解逆波蘭表達式。對於一個操作符，從棧頂依次彈出兩個操作數進行計算，並將計算結果壓入棧中。對於一個操作數，直接將它壓入棧中。最後，棧中只剩下一個元素，即為表達式的值。

四、總結

Stack是Java中常用的數據結構之一，它可以用於實現許多算法和函數。本文介紹了Stack的基本操作，以及兩個應用：括號匹配和逆波蘭表達式求解。希望讀者通過本文的學習，可以更深入地理解Stack的使用。