【算法】最小栈的实现(getMin)

看书时遇到这样一道题，挺有趣的数据结构，所以记录下来

题目:

实现一个栈，该栈带有出栈(pop)，入栈(push)，取最小元素(getMin)，三个方法。要保证这3个方法的时间复杂度都是O(1)

算法：

1.定义两个栈，一个栈自定义栈用于入栈、出栈，一个辅助栈用于动态存放自定义栈的最小值

2.入栈操作，当元素压入 自定义栈 的时候，会判断辅助栈是否为空，
如果辅助栈为空，或者新元素小于等于辅助栈栈顶，则将新元素压入(push) 辅助栈。

因为当第一个元素入栈时，这个唯一的元素也就是自定义栈当前最小的值，所以也压入(push) 辅助栈

3.出栈操作，如果出栈元素和辅助栈栈顶元素值相等，辅助栈出栈(pop)。

代码如下：

入栈操作

如果辅助栈为空，或者新元素小于等于辅助栈栈顶，则将新元素压入辅助栈

    /**
     * 入栈操作
     * @param element 入栈的元素 
     */

    public void push(int element){
        mainStack.push(element);
        //如果辅助栈为空，或者新元素小于等于辅助栈栈顶，则将新元素压入辅助栈
        if(minStack.empty()|| element <= minStack.peek()){
            //empty() 表示的是测试堆栈是否为空。
            //peek() 表示的是查看堆栈顶部的对象，但不从堆栈中移除它。
            minStack.push(element);
        }
    }

出栈操作

如果出栈元素和辅助栈栈顶元素值相等，辅助栈出栈(pop)。

    /**
     * 出栈操作
     */
    public Integer pop(){
        //如果出栈元素和辅助栈栈顶元素值相等，辅助栈出栈
        if(mainStack.peek().equals(minStack.peek())){
            minStack.pop();
        }
        return mainStack.pop();
    }

获取栈的最小元素(getMin方法)

/**
     * 获取栈的最小元素
     */
    public int getMin() throws Exception{
        if(mainStack.empty()){
            throw new Exception ("stack is empty");
        }
        return minStack.peek();
    }   

主函数

元素入栈，输出最小值，元素出栈，再输出最小值

public static void main(String[] args) throws Exception {
        MinStack stack=new MinStack();
        stack.push(4);
        stack.push(9);
        stack.push(7);
        stack.push(3);
        stack.push(8);
        stack.push(5);
        System.out.println(stack.getMin());
        stack.pop();
        stack.pop();
        stack.pop();
        System.out.println(stack.getMin());

    }

运行结果：
3
4

完整代码

package min_ini;
import java.util.Stack;
public class MinStack {

    private Stack<Integer> mainStack=new Stack<Integer>();
    private Stack<Integer> minStack=new Stack<Integer>();

    /**
     * 入栈操作
     * @param element 入栈的元素 
     */

    public void push(int element){
        mainStack.push(element);
        //如果辅助栈为空，或者新元素小于等于辅助栈栈顶，则将新元素压入辅助栈
        if(minStack.empty()|| element <= minStack.peek()){
            //empty() 表示的是测试堆栈是否为空。
            //peek() 表示的是查看堆栈顶部的对象，但不从堆栈中移除它。
            minStack.push(element);
        }
    }

    /**
     * 出栈操作
     */
    public Integer pop(){
        //如果出栈元素和辅助栈栈顶元素值相等，辅助栈出栈
        if(mainStack.peek().equals(minStack.peek())){
            minStack.pop();
        }
        return mainStack.pop();
    }
    /**
     * 获取栈的最小元素
     */
    public int getMin() throws Exception{
        if(mainStack.empty()){
            throw new Exception ("stack is empty");
        }
        return minStack.peek();
    }   

    public static void main(String[] args) throws Exception {
        MinStack stack=new MinStack();
        stack.push(4);
        stack.push(9);
        stack.push(7);
        stack.push(3);
        stack.push(8);
        stack.push(5);
        System.out.println(stack.getMin());
        stack.pop();
        stack.pop();
        stack.pop();
        System.out.println(stack.getMin());

    }

}