基礎(chǔ)知識(shí)

棧也是一種特殊的線性表，他只能對(duì)棧頂進(jìn)行添加和刪除元素。棧有入棧和出棧兩種操作，他就好像我們把書(shū)一本本的摞起來(lái)，最先放的書(shū)肯定是摞在下邊，最后放的書(shū)肯定是摞在了最上面，摞的時(shí)候不允許從中間放進(jìn)去，拿書(shū)的時(shí)候也是先從最上面開(kāi)始拿，不允許從下邊或中間抽出來(lái)。

棧的原理圖

棧的實(shí)現(xiàn)可以使用數(shù)組也可以使用鏈表，我們這里分析的主要是使用數(shù)組的形式。

在這里插入圖片描述

代碼實(shí)現(xiàn)

棧的實(shí)現(xiàn)其實(shí)非常簡(jiǎn)單，常見(jiàn)的就兩種操作，一種是壓棧一種是出棧，我們來(lái)看下代碼

public class Stack<E> {
    private Object[] data;
    private int size;

    public Stack(int capacity) {
        if (capacity <= 0)
            throw new IllegalArgumentException("棧的大小必須大于0");
        data = new Object[capacity];
    }

    public void push(E item) {
        if (isFull())
            throw new IllegalArgumentException("棧已經(jīng)滿了");
        data[size++] = item;
    }

    public E pop() {
        if (isEmpty())
            throw new IllegalArgumentException("棧是空的");
        E temp = (E) data[--size];
        data[size] = null;
        return temp;
    }

    public E peek() {
        if (isEmpty())
            throw new IllegalArgumentException("棧是空的");
        return (E) data[size - 1];
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public boolean isFull() {
        return size() == data.length;
    }

    public int size() {
        return size;
    }
}

這里為了方便，棧的空間大小在初始化的時(shí)候就就已經(jīng)固定了，并且棧滿的時(shí)候沒(méi)有擴(kuò)容，棧是一個(gè)非常有用的數(shù)據(jù)結(jié)構(gòu)，尤其在算法中用到的還是比較多的。棧是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，他和隊(duì)列正好相反，隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。

例子

我們來(lái)看個(gè)非常簡(jiǎn)單的例子，驗(yàn)證括號(hào)的有效性，括號(hào)只包含"("，")"，"["，"]"，"{"，"}"這6個(gè)字符，比如()，{()}，{}都是有效的，而{]，{(]}都是無(wú)效的。

我們來(lái)分析一下這道題，當(dāng)我們遍歷到括號(hào)的左半邊的時(shí)候，我們把括號(hào)的右半邊壓棧，當(dāng)我們遍歷到括號(hào)右半邊的時(shí)候，我們就把棧頂?shù)脑貜棾?，然后在和我們遍歷的符號(hào)比較看是否一樣，我們以字符串"{()}"為例來(lái)畫(huà)圖分析一下，

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

搞懂了上面的圖，寫(xiě)出代碼就容易多了，我們來(lái)看下代碼怎么實(shí)現(xiàn)

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>(s.length());
    for (char c : s.toCharArray()) {
        if (c == '(')
            stack.push(')');
        else if (c == '{')
            stack.push('}');
        else if (c == '[')
            stack.push(']');
        else if (stack.isEmpty() || stack.pop() != c)
            return false;
    }
    return stack.isEmpty();
}