用两个栈实现队列

用两个栈实现队列

题目描述：

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

解题思路

• 一个栈用于保存输入元素，并一个元素用于保存输出元素。队列末尾添加元素时，即向 in 栈中添加元素，当从队头删除元素时，将 in 栈中的元素出栈，每次先出栈元素 push 到 out 栈中，这样起到反转元素顺序的作用，此时对 out 栈进行 pop ，就相当于从对头删除元素

由于问题特殊，以下分析仅满足添加 N 个元素并删除 N 个元素，即栈初始和结束状态下都为空的情况

• 时间复杂度：appendTail()函数为 O(1)；deleteHead() 函数在 N 次队首元素删除操作中总共需完成 N 个元素的倒序。
• 空间复杂度：O(N)

class CQueue {
    Deque<Integer> in;
    Deque<Integer> out;
    public CQueue() {
        in = new ArrayDeque<>();
        out = new ArrayDeque<>();
    }
    
    public void appendTail(int value) {
        in.push(value);
    }
    
    public int deleteHead() {
        if (in.isEmpty() && out.isEmpty())
            return -1 ;

        if (out.isEmpty()) {
            while(!in.isEmpty()) {
                out.push(in.pop());
            }
        }

        return out.pop();
    }
}