首页 > 代码库 > 算法之设计一个有getMin方法的栈结构
算法之设计一个有getMin方法的栈结构
要求该栈的getMin方法和push和pop方法的时间复杂度都是O(1).
设计方案一:
package coding.chapter01; import java.util.Stack; /** * Created by Needle on 2017/3/17. */ public class GetMinStack { private Stack<int> dataStack;//存储数据的栈 private Stack<int> minStack;//存储最小值的栈 public GetMinStack(){ dataStack = new Stack<int>(); minStack = new Stack<int>(); } public int getMin(){ if (minStack.isEmpty()) throw new RuntimeException("The Stack is empty...."); else return minStack.peek();//获取栈顶元素的值,并不出栈 } public void push(int num){ //对minStack操作 if (minStack.isEmpty()) minStack.push(num); else if (num <= getMin()) minStack.push(num); //对dataStack进行操作 dataStack.push(num); } public int pop(){ if (minStack.isEmpty()) throw new RuntimeException("The Stack is empty...."); int value = http://www.mamicode.com/dataStack.pop();//dataStack正常出栈 if (value =http://www.mamicode.com/= getMin())//minStack仅仅在于相等的情况下才出栈 minStack.pop(); return value; } }
设计方案二:
package coding.chapter01; import java.util.Stack; /** * Created by Needle on 2017/3/19. */ public class GetMinStack2 { private Stack<int> dataStack;//保存数据的栈 private Stack<int> minStack;//保存最小值的栈 public GetMinStack2(Stack<int> dataStack, Stack<int> minStack) { this.dataStack = dataStack; this.minStack = minStack; } //出栈 public int pop(){ if (dataStack.isEmpty()) throw new RuntimeException("Error: Stack is empty!"); int value =http://www.mamicode.com/ dataStack.pop(); minStack.pop(); return value; } public void push(int num){ dataStack.push(num); if(minStack.isEmpty()){ minStack.push(num); } else if(num <= minStack.peek()) minStack.push(num); else minStack.push(minStack.peek()); } public int GetMin2(){ if (minStack.isEmpty()) throw new RuntimeException("Error: Stack is empty!"); return minStack.peek(); } }
算法之设计一个有getMin方法的栈结构
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。