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

题目:

实现一个栈,该栈带有出栈(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());

    }

}
最后修改日期:2019年7月29日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。