编写一个类,用两个栈实现队列,支持队列的基本操作:add、poll、peek。
栈的特点是先进后出,队列的特点是先进先出,使用两个栈正好能把顺序反过来实现类似队列的操作。
public class TwoStackQueue<T extends Comparable<T>> {
private Stack<T> mStack1;
private Stack<T> mStack2;
public TwoStackQueue() {
mStack1 = new Stack<>();
mStack2 = new Stack<>();
}
public void add(T item) {
mStack1.push(item);
}
/**
* 移除并返回队首的元素
*
* @return
*/
public T poll() {
if (mStack1.isEmpty() && mStack2.isEmpty()) {
throw new IllegalStateException("Queue is empty!");
} else if (mStack2.isEmpty()) {
while (!mStack1.isEmpty()) {
mStack2.push(mStack1.pop());
}
}
return mStack2.pop();
}
/**
* 返回队列头部的元素
*
* @return
*/
public T peek() {
if (mStack1.isEmpty() && mStack2.isEmpty()) {
throw new IllegalStateException("Queue is empty!");
} else if (mStack2.isEmpty()) {
while (!mStack1.isEmpty()) {
mStack2.push(mStack1.pop());
}
}
return mStack2.peek();
}
}