摘要：以數組的最后一個元素當成棧頂元素。解題思路首先，我們可以把左括號直接壓入棧，不論是小括號中括號還是大括號。拿出棧頂元素，如果與之右括號不匹配，則返回。如果字符串比較完成，沒有返回，則判斷棧是否為空。

棧是一種線性結構

相比較數組，棧對應的操作是數組的子集

只能從一端添加元素，也只能從同一端取出元素，這一端稱為棧頂

棧是一種后進先出的數據結構，LIFO（Last In First Out）

Undo操作（撤銷）

程序調用所使用的系統棧

其實，實現一個棧結構非常簡單，我們只需要復用上一節我們自己封裝的數組就可以快速的實現一個棧的創建。
以數組的最后一個元素當成棧頂元素。

public interface Stack {
    boolean isEmpty();
    int getSize();
    // 移除棧頂元素
    E pop();
    // 查看棧頂元素
    E peek();
    // 壓入棧
    void push(E ele);
}

注：這里我們有一個peek方法，就是查看棧頂元素，所以我們需要給我們自己封裝的數組類添加一個查看最后一個元素的方法：

// 獲取最后一個元素
public E getLast() {
    return get(size - 1);
}

public class ArrayStack implements Stack {

    private ArrayNew array;

    public ArrayStack(int capacity) {
        array = new ArrayNew<>(capacity);
    }

    public ArrayStack() {
        array = new ArrayNew<>();
    }

    public int getCapacity() {
        return array.getCapacity();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public void push(E ele) {
        array.addLast(ele);
    }

    @Override
    public E pop() {
        return array.removeLast();
    }

    @Override
    public E peek() {
        return array.getLast();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();

        res.append("Stack: [");
        for (int i = 0; i < getSize(); i++) {
            res.append(array.get(i));
            if (getSize() - 1 != i) {
                res.append(", ");
            }
        }
        res.append("] top");
        return res.toString();
    }

}

注：其中的ArrayNew即是我們在上一節自己封裝的數組類，不知道的同學可以去查看：
我理解的數據結構（一）—— 不要小看了數組

因為我在ArrayNew中已經實現了動態數組，所以不用考慮棧長度的問題，這樣我們就自己封裝了一個棧（注釋在Stack接口中和ArrayNew類中足夠詳細）。

這是一道leetcode上，編號為20的題目，具體題目描述如下：

給定一個只包括 "("，")"，"{"，"}"，"["，"]" 的字符串，判斷字符串是否有效。

有效字符串需滿足：
    1.左括號必須用相同類型的右括號閉合。
    2.左括號必須以正確的順序閉合。
注意空字符串可被認為是有效字符串。

解題思路

首先，我們可以把左括號直接壓入棧，不論是小括號、中括號還是大括號。

如果拿到的是右括號，則需要做匹配判斷。

拿出棧頂元素，如果與之右括號匹配，則pop出棧頂元素。

拿出棧頂元素，如果與之右括號不匹配，則返回false。

如果字符串比較完成，沒有返回false，則判斷棧是否為空。

為空，返回true，括號匹配成功

不為空，返回false

public boolean isValid(String s) {

    ArrayStack stack = new ArrayStack<>();

    for (int i = 0; i < s.length(); i++) {

        char c = s.charAt(i);

        // 左括號直接壓入棧
        if (c == "(" || c == "[" || c == "{") {
            stack.push(c);
        } else {

            if (stack.isEmpty()) {
                return false;
            }

            char topChar = stack.pop();
            if (c == ")" && topChar != "(") {
                return false;
            }
            if (c == "]" && topChar != "[") {
                return false;
            }
            if (c == "}" && topChar != "{") {
                return false;
            }
        }

    }

    return stack.isEmpty();
}

因為棧的時間復雜度都是O(1)，所以棧的性能是很高的。