Java:设计一个有getMin功能的栈，要求pop,push,getMin操作的时间复杂度均为O(1)

1.方法一：

package offer;
import java.util.Stack;
public class MyStack {
private Stack<Integer> StackData;
private Stack<Integer> StackMin;
public MyStack(){
this.StackData=new Stack<Integer>();
this.StackMin=new Stack<Integer>();
}
public int getMin(){
if(this.StackMin.isEmpty()){
throw new RuntimeException("Your stack is empty.");
}
return this.StackMin.peek();
}
public void push(int newNum){
if(this.StackMin.isEmpty()){
this.StackMin.push(newNum);
}else if(newNum<=this.getMin()){
this.StackMin.push(newNum);
}
this.StackData.push(newNum);
}
public int pop(){
if(this.StackData.empty()){
throw new RuntimeException("Your stack is empty");
}
int value=this.StackData.pop();
if(value==this.StackMin.peek()){
this.StackMin.pop();
}
return value;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
MyStack s=new MyStack();
s.push(4);
s.push(5);
s.push(5);
System.out.println(s.getMin());
}
}

2.一种改进的牺牲空间换取时间的实现方法：

package offer;
import java.util.Stack;
public class MyStack2 {
private Stack<Integer> StackData;
private Stack<Integer> StackMin;
public MyStack2(){
this.StackData=new Stack<Integer>();
this.StackMin=new Stack<Integer>();
}
public void push(int newNum){
if(this.StackMin.isEmpty()){
this.StackMin.push(newNum);
}else if(newNum<this.StackMin.peek()){
this.StackMin.push(newNum);
}else{
this.StackMin.push(this.StackMin.peek());
}
this.StackData.push(newNum);
}
public int pop(){
if(this.StackData.isEmpty()){
throw new RuntimeException("Your stack is empty");
}
this.StackMin.pop();
return this.StackData.pop();
}
public int getMin(){
if(this.StackMin.isEmpty()){
throw new RuntimeException("Your stack is empty");
}
return this.StackMin.peek();
}
public static void main(String[] args) {
// TODO Auto-generated method stub
MyStack2 s=new MyStack2();
s.push(4);
s.push(5);
s.push(5);
System.out.println(s.getMin());
}
}

最后

以上就是爱笑镜子为你收集整理的Java:设计一个有getMin功能的栈，要求pop,push,getMin操作的时间复杂度均为O(1)的全部内容，希望文章能够帮你解决Java:设计一个有getMin功能的栈，要求pop,push,getMin操作的时间复杂度均为O(1)所遇到的程序开发问题。

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