(算法优化) 栈和队列(2)--由两个栈组成的队列
题目:
编写一个类,用两个栈来实现队列,支持队列的基本操作(add,poll,peak).
解析:
用两个栈,一个作为压入栈,压入数据时只往这个栈压入,记为stackPush;另一个栈只作为弹出栈,在弹出数据时只从这个栈弹出,记为stackPop。如图所示:
操作必须注意以下两点:
1.如果stackPush要往stackPop压入数据,那么必须一次性把stackPush中数据全部压入。
2.如果stackPop不为空,stackPush绝对不能向stackPop压入数据。
代码实现:
package test;
import java.util.Stack;
public class TwoStacksQueue {
public Stack<Integer> stackPush;//压入栈
public Stack<Integer> stackPop;//弹出栈
public TwoStacksQueue(){
stackPush=new Stack<Integer>();
stackPop=new Stack<Integer>();
}
/**
* add:增加一个元素 如果队列已满,则抛出异常
*/
public void add(int pushInt){
stackPush.push(pushInt);
}
/**
* poll:移除并返回队列头部的元素,如果队列为空,则返回null
*/
public int poll(){
if(stackPop.empty()&&stackPush.empty()){
throw new RuntimeException("Queue is empty");
}else if(stackPop.empty()){
while(!stackPush.empty()){
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}
/**
* peek:返回队列头部的元素,如果队列为空,则阻塞
*/
public int peek(){
if(stackPop.empty()&&stackPush.empty()){
throw new RuntimeException("Queue is empty");
}
else if(stackPop.empty()){
while(!stackPush.empty()){
stackPop.push(stackPush.pop());
}
}
return stackPop.peek();
}
}