请设计一个栈,除了常规栈支持的pop与push函数以外,还支持min函数,该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。 示例: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
利用两个栈,一个存储完整数据DataStack,一个只存储当前最小值MinStack。
元素入栈时,和MinStack中的栈顶元素比较,如果小或者等于则将该元素分别压入DataStack和MinStack;
若大则只将元素压入DataStack中,直至元素入栈完毕,最小值为MinStack的栈顶元素。
//本题中可以直接引用现成的栈结构和方法
class MinStack {
private Stack<Integer> DataStack;
private Stack<Integer> MinStack;
public MinStack() {
this.DataStack = new Stack<Integer>();
this.MinStack = new Stack<Integer>();
}
//入栈
public void push(int newNum){
if(this.MinStack.isempty()){
this.MinStack.push(newNum);
}else if(newNum < MinStack.getMin()){
this.MinStack.push(newNum);
}
this.DataStack.push(newNum);
}
//出栈
public int pop(){
if(this.DataStack.isempty()){
throw new runtimeException("the stack is empty");
}
int Num = this.DataStack.pop();
if(Num == this.getMin()){
this.MinStack.pop();
}
return Num;
}
//获得最小值
public int getMin(){
if(this.MinStack.isempty()){
throw new runtimeException("the stack is empty");
}
return this.MinStack.peek();
}
}
时间复杂度:O(1) 空间复杂度:O(n)
编写一个类,用两个栈实现队列,支持队列的基本操作(add, poll, peek)
public class TwoStacks_Queue{
private Stack<Integer> pushStack;
private Stack<Integer> popStack;
public TwoStacks_Queue(){
pushStack = new Stack<Integer>();
popStack = new Stack<Integer>();
}
//add 入队操作
public void add(int NewNum){
if(popStack.isEmpty()){
//若入队列栈非空,将该栈元素迁移到出队栈
while(!pushStack.isEmpty()){
popStack.push(pushStack.pop);
}
pushStack.push(NewNum);
}
}
//poll 出队操作
public int poll(){
if(pushStack.isEmpty() & popStack.isEmpty()){
throw new RuntimeException("队列为空");
//入队列栈非空,出队列栈为空时,将入队列栈元素全部移动到出队列栈
}else if(popStack.isEmpty()){
while(!pushStack.isEmpty()){
popStack.push(pushStack.pop());
}
}
return popStack.pop();
}
//peek 查看队首元素 和poll函数类似
public int peek(){
if(pushStack.isEmpty() & popStack.isEmpty()){
throw new RuntimeException("队列为空");
//入队列栈非空,出队列栈为空时,将入队列栈元素全部移动到出队列栈
}else if(popStack.isEmpty()){
while(!pushStack.isEmpty()){
popStack.push(pushStack.pop());
}
}
return popStack.pop();
}
}