(栈队列堆) 剑指 Offer 09. 用两个栈实现队列 —

(栈队列堆) 剑指 Offer 09. 用两个栈实现队列 ——【Leetcode每日一题】

❓ 剑指 Offer 09. 用两个栈实现队列

难度：简单

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

示例 1：

输入：
[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”,“deleteHead”]
[[],[3],[],[],[]]
输出：[null,null,3,-1,-1]

示例 2：

输入：
[“CQueue”,“deleteHead”,“appendTail”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

提示：

$1 <= v a l u es <= 10000$
最多会对 appendTail、deleteHead 进行 10000 次调用

💡思路：

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

in 栈用来处理入栈（push）操作，out 栈用来处理出栈（pop）操作;
一个元素进入 in 栈之后，出栈的顺序被反转。当元素要出栈时，需要先进入 out 栈，此时元素出栈顺序再一次被反转，因此出栈顺序就和最开始入栈顺序是相同的，先进入的元素先退出，这就是队列的顺序。

🍁代码：(C++、Java)

C++

class CQueue {
private:
    stack<int> in, out;

    void in2out(){
        while(!in.empty()){
            out.push(in.top());
            in.pop();
        }
    }

public:
    CQueue() { }
    
    void appendTail(int value) {
        in.push(value);
    }
    
    int deleteHead() {
        if(out.empty()){
            if(in.empty()) return -1;
            in2out();
        }
        int ans = out.top();
        out.pop();
        return ans;
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */

Java

class CQueue {
    private Stack<Integer> in = new Stack<Integer>();
    private Stack<Integer> out = new Stack<Integer>();

    private void in2out(){
        while(!in.isEmpty()){
            out.push(in.pop());
        }
    }

    public CQueue() { }
    
    public void appendTail(int value) {
        in.push(value);
    }
    
    public int deleteHead() {
        if(out.isEmpty()){
            if(in.isEmpty()) return -1;
            in2out();
        }
        return out.pop();
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

🚀 运行结果：

在这里插入图片描述

🕔 复杂度分析：

时间复杂度：appendTail 为 $O (1)$ ，deleteHead 为均摊 $O (1)$ 。对于每个元素，至多入栈和出栈各两次，故均摊复杂度为 $O (1)$ 。
空间复杂度： $O (n)$ ，其中 n 是操作总数。对于有 n 次appendTail 操作的情况，队列中会有 nnn 个元素，故空间复杂度为 $O (n)$ 。