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

棧是一種線性結(jié)構(gòu)

相比較數(shù)組，棧對應(yīng)的操作是數(shù)組的子集

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

棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，LIFO（Last In First Out）

Undo操作（撤銷）

程序調(diào)用所使用的系統(tǒng)棧

其實(shí)，實(shí)現(xiàn)一個(gè)棧結(jié)構(gòu)非常簡單，我們只需要復(fù)用上一節(jié)我們自己封裝的數(shù)組就可以快速的實(shí)現(xiàn)一個(gè)棧的創(chuàng)建。
以數(shù)組的最后一個(gè)元素當(dāng)成棧頂元素。

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

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

// 獲取最后一個(gè)元素
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即是我們在上一節(jié)自己封裝的數(shù)組類，不知道的同學(xué)可以去查看：
我理解的數(shù)據(jù)結(jié)構(gòu)（一）—— 不要小看了數(shù)組

因?yàn)槲以?b>ArrayNew中已經(jīng)實(shí)現(xiàn)了動(dòng)態(tài)數(shù)組，所以不用考慮棧長度的問題，這樣我們就自己封裝了一個(gè)棧（注釋在Stack接口中和ArrayNew類中足夠詳細(xì)）。

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

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

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

解題思路

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

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

拿出棧頂元素，如果與之右括號匹配，則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();
}

因?yàn)闂５臅r(shí)間復(fù)雜度都是O(1)，所以棧的性能是很高的。