最小栈的实现
程序员文章站
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
下一篇: 二分查找-006-旋转数组的最小数字