【算法】最小栈的实现(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());
}
}

最后

以上就是无语月饼为你收集整理的【算法】最小栈的实现(getMin)的全部内容，希望文章能够帮你解决【算法】最小栈的实现(getMin)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。