基本概念

棧是一種數(shù)據(jù)結(jié)構(gòu)，類似一個(gè)箱子：每次往棧中添加元素，都是向棧頂添加；每次從棧中拿出元素，也是從棧頂拿走。棧有著先進(jìn)后出的規(guī)律。

實(shí)現(xiàn)

• 通過ArrayList實(shí)現(xiàn)棧

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內(nèi)置Stack類

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

Lintcode 相關(guān)練習(xí)

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