日拱一卒：栈（Stack）

1. 栈（Stack）

• 栈是一种特殊的线性表，运算受限
• 栈有两种储存方式，顺序栈和链式栈

public class Stack<E> extends Vector<E> {
    public E push(E item) {
        addElement(item);
        return item;
    }

    // 出栈，弹出栈顶元素，并将栈顶元素返回
    public synchronized E pop() {
        E       obj;
        int     len = size();
        obj = peek();
        removeElementAt(len - 1);
        return obj;
    }

    // 获取栈顶元素
    public synchronized E peek() {
        int     len = size();
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
}

2. 手写栈

2.1 方式一：继承 ArrayList

缺点：可以调用父类的 add(), get(index), 实际并不应该对外提供

public class MyStack<E> extends ArrayList<E> {
    public void push(E element) {
        add(element);
    }
    public E pop() {
        return remove(size() - 1);
    }
    public E peek() {
        return get(size() - 1);
    }
}

测试

MyStack<Integer> stack = new MyStack<>();
stack.push(1);

2.2 方式二：组合方式

public class MyStack<E> {
    // 组合方式，ArrayList 作为一个属性
    private List<E> list = new ArrayList<>();
    public void push(E element) {
        list.add(element);
    }
}

3. 练习

3.1 Leetcode 20 括号序列

• 3 种括号 () {} []

方式一：用字符串处理

public static boolean check(String s) {
    // 此处是 while 循环，只要还有能匹配的字符就会一直循环
    while (s.contains("{}") || s.contains("()") || s.contains("[]")) {
        s = s.replace("{}", "");
        s = s.replace("()", "");
        s = s.replace("[]", "");
    }
    return s.isEmpty();
}

方式二：使用栈

1. 左括号入栈，右括号出栈并比较
2. 所有字符比较完后，栈应该为空

/**
 * check("{[()]}")
 * 1. 遇见左字符直接入栈
 * 2. 遇见右字符开始比较
 * 3. 注意判断左字符多于右字符的情况 {{[()]}
 */
public static boolean check(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '{' || c == '[' || c == '(') {
            stack.push(c);
        } else {
            // isEmpty 没有左字符了，可能是本身就没有，或出栈完了
            if (stack.isEmpty()) return false;

            char left = stack.pop();
            if (c == '}' && left != '{') return false;
            if (c == ']' && left != '[') return false;
            if (c == ')' && left != '(') return false;
        }
    }
    // 所有字符扫描完后，判断stack.isEmpty，避免左括号多于右括号判断出错
    return stack.isEmpty();
}

补充：其他获取字符的方式

public static boolean check(String s) {
    Stack<Character> stack = new Stack<>();
    int len = s.length();
    for (int i = 0; i < len; i++) {
        char c = s.charAt(i);
        // ...
    }
    return stack.isEmpty();
}

3.2 浏览器的前进后退

• 用两个栈实现