线性结构：栈

思路

栈是一种先进后出（First In Last Out, FILO）的数据结构。相对上一篇的数组，它只能在最后添加或删除元素，因此它是数组的一个子集，可复用上一章的数组实现栈结构。

实现

先定义一个栈的接口

public interface Stack<E> {

    int size();

    boolean isEmpty();

    void push(E e);

    E pop();

    E peek();

}

其中pop会将栈顶元素推出，而peek只会读栈顶的值，不会改变栈。

实现数组栈：

public class ArrayStack<E> implements Stack<E> {
    private final Array<E> array;

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

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

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

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

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

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

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

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Stack ")).append('[');
        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if (i != array.getSize() - 1) {
                res.append(", ");
            }
        }
        res.append(']');
        return res.toString();
    }


}

复杂度分析

由于只能在栈顶操作，因此数组栈的所有方法的复杂度都为O(1)

力扣(20)：有效的括号

解题思路是利用栈结构，当碰到左括号时压入栈，碰到又括号时看是否栈顶有与之匹配的左括号。

class Solution {
    public boolean isValid(String s) {
        Stack<Character> 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;
                }
                if (c == ')' && stack.pop() != '(') {
                    return false;
                }
                if (c == ']' && stack.pop() != '[') {
                    return false;
                }
                if (c == '}' && stack.pop() != '{') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}