Posts List

栈和队列基础题

1,设计一个有getMin功能的栈 题目:实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中的最小值 要求: 1,pop、push、getMin操作的时间复杂度都是O(1) 2,设计的栈类型可以使用现成的栈的结构 public class Stack1 { private Stack<Integer> stackMin; private Stack<Integer> stackData; public Stack1(){ stackMin=new Stack<>(); stackData=new Stack<>(); } public int getMin(){ if(stackMin.isEmpty()){ throw new RuntimeException("stack is null"); } return stackMin.peek(); } //方案一 //节省空间,pop步骤多 public void push(int newNum){ if(stackMin.isEmpty()){ stackMin.push(newNum); }else{ if(getMin()<=newNum){ stackMin.push(newNum); } } stackData.push(newNum); } public int pop(){ if(stackData.isEmpty()){ throw new RuntimeException("stack is null"); } int value=stackData.pop(); if(value==getMin()){ stackMin.pop(); } return value; } //-------------------------- //方案2 //比方案1多费空间,但省时间 public void push2(int newNum){ if(stackMin.