Java实现包含min函数的栈

Java实现包含min函数的栈

基本思路：数据栈dataStack正常存入和pop出数据，辅助栈minStack存放同stack1同水平线最小值。
pop时，只要将两个栈同时pop即可。

class MinStack {
	//存入数据主栈
    private Deque dataStack;
    //辅助栈，存放最小值
    private Deque minStack;

    public MinStack() {
    	//使用linkedList创建栈可提高效率
        dataStack = new linkedList<>();
        minStack = new linkedList<>();
    }

    public void push(int x) {
        dataStack.push(x);
        //minStack不为空时存放栈顶和x中的最小值
        if (!minStack.isEmpty()){
            minStack.push(Math.min(minStack.peek(),x));
            return;
        }
        //minStack为空时直接加入
        minStack.push(x);
    }
	//同时pop出两个栈的栈顶元素
    public void pop() {
        dataStack.pop();
        minStack.pop();
    }

    public int top() {
        return dataStack.peek();
    }

    public int min() {
        return minStack.peek();
    }
}

测试类：

public class Test {
    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.min());
        minStack.pop();
        System.out.println(minStack.top());
        System.out.println(minStack.min());
    }
}

结果：