用两个栈实现队列 -- java

用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。

假设元素先进stack1栈，如果这个时候需要弹出元素时，分为两种情况：

• 当stack2栈为空时，我们把stack1栈的元素逐个弹出并压入stack2栈，此时我们会发现最先进入的元素已经在stack2栈顶，可以直接弹出；
• 当stack2栈不为空，在stack2中的栈顶元素就是最先进入队列的元素，可以弹出。

import java.util.Stack;

public class CQueue {
    private Stack stack1 = new Stack<>();
    private Stack stack2 = new Stack<>();

    public void appendTail(T node) {
        stack1.push(node);
    }

    public T deleteHead() throws Exception {
        // 当stack2为空时，将stack1中的数据pop到stack2
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        // stack1和stack2都为空 那么说明队列为空
        if (stack2.isEmpty()) {
            throw new Exception("queue is empty");
        }

        return stack2.pop();
    }

    // 测试
    public static void main(String[] args)  throws Exception{
        CQueue queue = new CQueue<>();
        queue.appendTail(1);

        queue.deleteHead();
        
        // 加上下面这局代码 会抛出异常queue is empty
        queue.deleteHead();
    }
}

来自
《剑指Offer》
Coding-Interviews/用两个栈实现队列.md at master · todorex/Coding-Interviews