栈 - Stack

基本概念

栈是一种数据结构，类似一个箱子：每次往栈中添加元素，都是向栈顶添加；每次从栈中拿出元素，也是从栈顶拿走。栈有着先进后出的规律。

实现

• 通过ArrayList实现栈

public class Stack {
    private List<Integer> array = new ArrayList<>();
    // 入栈
    public void push(int x) {
        array.add(x);
    }
    // 出栈
    public void pop() {
        int n = array.size();
        if (n > 0) {
            array.remove(n - 1);
        }
    }
    // 返回栈顶元素
    public int top() {
        int n = array.size();
        if (n > 0) {
            return array.get(n - 1);
        } else {
            return -1;
        }
    }
    public boolean isEmpty() {
        return array.size() == 0;
    }
}

• Java内置Stack类

Stack<Integer> s = new Stack<>();
s.size(); // 返回栈的大小
s.peek; // 返回栈顶元素，但不弹出栈顶元素
s.push(); // 入栈
s.pop(); // 出栈，并返回弹出元素

Lintcode 相关练习

Implement Stack by Two Queues
Valid Parentheses
Min Stack
Largest Rectangle in Histogram
Evaluate Reverse Polish Notation