两个栈实现队列

两个栈实现队列

查看文章：http://www.cnblogs.com/kaituorensheng/archive/2013/03/02/2939690.html

enter image description here
有三种思路：

1. s1是入栈的，s2是出栈的。

   • 入队列时：如果s1为空，把s2中所有的元素倒出压到s1中；否则直接压入s1
   • 出队列时：如果s2不为空，把s2中的栈顶元素直接弹出；否则，把s1的所有元素全部弹出压入s2中，再弹出s2的栈顶元素

2. s1是入栈的，s2是出栈的。保证所有元素都在一个栈里面

   • 入队列时：如果s1为空，把s2中所有的元素倒出压到s1中；否则直接压入s1
   • 出队列时：如果s2不为空，把s2中的栈顶元素直接弹出；否则，把s1的所有元素全部弹出压入s2中，再弹出s2的栈顶元素

3. s1是入栈的，s2是出栈的

   • 入队列：直接压入s1即可
   • 出队列：如果s2不为空，把s2中的栈顶元素直接弹出；否则，把s1的所有元素全部弹出压入s2中，再弹出s2的栈顶元素

最优解是第三种方式

public class sQueue<T> {
    Stack<T> s1 = new Stack<T>();
    Stack<T> s2 = new Stack<T>();

    public void appendTrail(T append) {
        s1.push(append);
    }

    public T deleteHead(Stack<T> s) {
        if (s2 == null) {
            while (s1.size() > 0) {
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
}