由两个栈组成的队列

问题

编写一个类，用两个栈实现队列，支持队列的基本操作：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();

    }
}