155. 最小栈

中等

解法：使用两个栈，一个存放所有的值，另一个存放最小值

class MinStack {

    int top;
	List<Integer> list;
	LinkedList<Integer> link;
	public MinStack() {
		top = -1;
		list = new ArrayList<>();
		link = new LinkedList<>();
	}

    public void push(int val) {
        list.add(val);
        top++;
        if (link.isEmpty() || val <= link.getLast()) {
            link.add(val);
        }
    }

    public void pop() {
        if (list.get(top).equals(link.getLast())) {
            link.removeLast();
        }
        list.remove(top);
        top--;
    }

	public int top() {
		return list.get(top);
	}

	public int getMin() {
		return link.getLast();
	}
}