题目原文:
Implement a queue with two stacks so that each queue operations takes a constant amortized number of stack operations.
题目要求用栈实现队列的所有操作。
package week2; import java.util.Stack; /**
* Queue with two stacks. Implement a queue with two stacks so that each queue
* operations takes a constant amortized number of stack operations
* @author yangjingjing
*
*/
public class QueueWith2Stacks<E>{
Stack<E> inStack = new Stack<E>();
Stack<E> outStack = new Stack<E>();
public boolean isEmpty(){
if(inStack.isEmpty() && outStack.isEmpty())
return true;
else return false;
}
public int size(){
return (inStack.size() + outStack.size());
}
public void enqueue(E item){
inStack.push(item);
}
public E dequeue(){
if(outStack.isEmpty()){
if(inStack.isEmpty()) return null;
else{
while(!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
return outStack.pop();
}
}else{
return outStack.pop();
}
}
public static void main(String[] args) {
QueueWith2Stacks<Object> queue = new QueueWith2Stacks<Object>();
queue.enqueue("a");
queue.enqueue("b");
queue.enqueue("c");
System.out.println(queue.dequeue());
queue.enqueue(1);
queue.enqueue(2);
Object o = null;
while((o = queue.dequeue()) != null) {
System.out.println(o);
}
}
}