栈

栈跟数组一样，也是一种线性数据结构。相比数组，栈对应的操作是数组的子集，只能从一端(栈顶)添加元素，也只能从一端(栈顶)取出元素，接近栈顶的先出，接近栈底的后出，所以栈是一种后进先出的数据结构（LIFO）。

栈的应用

程序调用的系统栈：

假如 A 方法里调用了 B 方法，B 方法里调用了 C 方法。系统栈会在 A 方法中运行到调用 B 方法的代码时，会将当前位置入栈（假设将A2入栈），然后系统会调 B 方法，当在 B 方法中运行到调用 C 方法的代码时，会将当前位置入栈（假设将B2入栈），然后系统会调用 C 方法。当 C 方法运行完，会回到系统栈的 B2 位置来继续运行 B 方法，当 B 方法运行完，会将 B2 出栈，然后回到系统栈的 A2 位置来继续运行 A 方法，A 方法运行完后，会将 A2 出栈。

栈代码实现

首先，我们先定义一个栈需要用到的接口方法，因为栈的底层实现可以是多样的，只要实现了接口方法的，都可以称为栈。

栈接口定义

public interface Stack<E> {

    /**
     * 返回栈内元素的个数
     */
    int getSize();

    /**
     * 栈内元素个数是否为空
     */
    boolean isEmpty();

    /**
     * 向栈顶添加一个元素
     */
    void push(E e);

    /**
     * 移除栈顶元素
     */
    E pop();

    /**
     * 查看栈顶元素
     */
    E peek();
}

底层为数组的栈实现

public class ArrayStack<E> implements Stack<E> {

    private Array<E> array;

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

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

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

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

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

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

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

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

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

时间复杂度分析

int getSize() ， O(1) 级别

boolean isEmpty() ，O(1) 级别

void push(E e) ，O(1) 级别，均摊

E pop() ，O(1) 级别，均摊

E peek() ，O(1) 级别

LeetCode 的题目解答

20.有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

解题代码如下：

public boolean isValid(String s) {
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        // 如果是左侧括号，则入栈
        if (c == ('(') || c == ('[') || c == ('{')) {
            stack.push(s.charAt(i));
        } else {
            // 如果是右侧括号，但是此时栈内为空，则返回 false
            if (stack.isEmpty()) {
                return false;
            } else {
                // 将栈顶括号和当前括号比较，如果左右括号闭合，则出栈，然后返回 false
                char topChar = stack.peek();
                if (topChar == ('(') && c == (')') || topChar == ('[') && c == (']') || topChar == ('{') && c == ('}')) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
    }
    // 最后，如果栈内元素为空，则返回 true ，否则返回 false
    return stack.isEmpty();
}