Java Stack相關知識總結

1、引言

Java中的Stack（棧）是一種數據結構，它遵循後進先出的原則。它包含兩個基本操作：push（入棧）和pop（出棧）。Java Stack類提供了這兩個方法，以及其他有關棧的操作。本篇文章將介紹Java Stack類及其相關知識。

2、Stack類的基本用法

1）Stack類的創建

要創建一個Stack對象，可以使用如下代碼：

Stack stack = new Stack();

上述代碼創建了一個空的整型棧。由於Java是泛型語言，我們需要聲明Stack類的類型參數。

2）Stack類中的push和pop方法

push方法用於將一個元素入棧，如下所示：

stack.push(1);
stack.push(2);
stack.push(3);

上述代碼將整數1，2和3按照後進先出的順序依次入棧。

pop方法用於將棧頂的元素出棧，如下所示：

int top = stack.pop();

上述代碼將棧頂的元素3出棧，並將其賦值給變量top。

3）其他Stack類中的方法

Stack類中還提供了其他一些有關棧的操作方法，如isEmpty、peek、search等。

isEmpty方法用於判斷棧是否為空：

boolean empty = stack.isEmpty();

peek方法用於查看棧頂的元素，但不將其出棧：

int top = stack.peek();

search方法用於查找棧中某個元素的位置：

int index = stack.search(2);

上述代碼查找元素2在棧中的位置，如果元素不存在，返回-1。

3、Stack類的應用

1）Stack類的逆波蘭表達式實現

逆波蘭表達式（Reverse Polish Notation，RPN）是一種無需使用括號來標識運算順序的數學表達式。例如，表達式“1 + 2 * 3”可以寫成“1 2 3 * +”。下面是使用Stack類實現逆波蘭表達式的示例代碼：

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

上述代碼實現了一個evalRPN方法，可以計算逆波蘭表達式的值。該方法使用了Stack類來模擬一個棧結構，用於存儲操作數和計算結果。

2）Stack類的括號匹配實現

括號匹配是一種常見的問題，其解決方式就是利用棧的特性。

下面是使用Stack類實現括號匹配的示例代碼：

public static boolean isValid(String s) {
    Map map = new HashMap();
    map.put('(', ')');
    map.put('[', ']');
    map.put('{', '}');

    Stack stack = new Stack();
    for (char c : s.toCharArray()) {
        if (map.containsKey(c)) {
            stack.push(c);
        } else if (map.containsValue(c)) {
            if (!stack.isEmpty() && map.get(stack.peek()) == c) {
                stack.pop();
            } else {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

上述代碼實現了一個isValid方法，可以判斷一個由括號組成的字符串是否匹配。該方法使用了Stack類來模擬一個棧結構，用於存儲左括號，並在遇到右括號時匹配左括號，如果匹配成功，則將左括號出棧。

4、總結

本篇文章介紹了Java Stack類及其相關知識。我們了解了Stack類的基本用法，如push和pop方法，以及其他一些有關棧的操作。此外，我們還介紹了Stack類的兩個實際應用場景，即逆波蘭表達式和括號匹配。

在實際應用中，棧是一種非常常用的數據結構，它被廣泛用於處理各種計算和程序問題。對Stack類的熟練掌握和運用，對於Java開發者來說是非常重要的。