包含min函数的栈

题目

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

题目地址

解析与代码实现

正常来说用一个栈实现， push 和 pop的时间复杂度为 O(1) ， 但是 min 这个操作的时间复杂度为 O(n)。
所以我们用两个栈来实现此功能：
stack1 正常存储数据;
stack2 负责存储 stack1 中 不规则降序 的元素。

public class MinStack {

    Stack<Integer> stack1, stack2;
    
    public MinStack(){
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    //添加数据过程中，如果value <= stack2的栈顶，则代表有最新的最小值加入， 加上‘=’是为了保证pop时不出错
    public void push(int value) {
        stack1.add(value);
        if (stack2.isEmpty() || stack2.peek >= value) {
            stack2.add(value);
        }   
    }

    public void top() {
        return stack1.peek();
    }
    
    //如果stack1的栈顶和stack2的栈顶相同，则都pop()
    public void pop() {
        if(stack1.pop().equals(stack2.peek()) {
            stack2.pop();
        }
    }
    
    //stack2的栈顶就是最小值
    public void min() {
        return stack2.peek();
    }
    
}