欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最小栈的实现

程序员文章站 2024-03-15 21:25:42
...
public class Code2_Stack_Min {

	/**
	 * @program: Aglorithm
	 * @Date: today
	 * @Author: Kyrie
	 * @Description: 关于最小栈的实现
	 * 实现一个栈,该栈带有出栈(pop)、入栈(push)、取最小元素(getMin)3个方法。
	 * 保证这3个方法的时间复杂度都是O(1)。
	 * 思路:借助一个辅助栈来实现
     */
    public Stack<Integer> mainStack =  new Stack<>();  //Stack集合
    public Stack<Integer> minStack = new Stack<>();

    //入栈
    public void push(int data){
        mainStack.push(data);
        if(minStack.isEmpty() || data <= minStack.peek()){  //如果辅助栈为空或者其栈顶元素小于要压入栈的元素
            minStack.push(data);
        }
    }
    //出栈
    public Integer pop() throws Exception{
        if (mainStack.isEmpty()){
            throw new Exception("stack is empty");
        }
        //若主栈顶元素是最小值,则辅助栈的栈顶先出栈,主栈的栈顶再出栈
        if(mainStack.peek().equals(minStack.peek())){
        //if(mainStack.peek() == minStack.peek()){
            minStack.pop();
        }
        return mainStack.pop();
    }

    //获取最小值
    public Integer getMin() throws Exception{
        if(minStack.isEmpty()){
            throw new Exception("stack is empty");
        }
        return minStack.peek();
    }

    public static void main(String[] args) throws Exception{

        Code3_Stack_Min stack_min = new Code3_Stack_Min();
        stack_min.push(4);
        stack_min.push(4);
        stack_min.push(9);
        stack_min.push(3);
        stack_min.push(7);
        stack_min.push(2);
        System.out.println(stack_min.minStack.peek());
        System.out.println("=======================");
        System.out.println(stack_min.pop());
        System.out.println(stack_min.pop());
        System.out.println(stack_min.pop());
        System.out.println("=======================");
        System.out.println(stack_min.minStack.peek());
    }
}

2
=======================
2
7
3
=======================
4
相关标签: 最小值