如何用两个栈实现一个队列？

概念回顾

栈

栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后入先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据，最后一个数据被第一个读出来。

队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

用两个栈来实现一个队列

实现思路

核心在于利用两个“后进先出”的结构，模拟“先进先出”的行为。

设两个栈：

inStack：负责入队（push）
outStack：负责出队（pop）

基本策略如下：

入队操作：

直接将元素压入 inStack

出队操作：

若 outStack 不为空，直接从 outStack 弹出
若 outStack 为空，则将 inStack 中所有元素依次弹出并压入 outStack
再从 outStack 弹出栈顶元素

该过程本质是通过“二次反转”实现顺序恢复：

第一次：进入 inStack（顺序反转）
第二次：倒入 outStack（再次反转 → 恢复 FIFO 顺序）

C++实现

#include <stack>
using namespace std;

class MyQueue {
private:
    stack<int> inStack;
    stack<int> outStack;

public:
    // 入队
    void push(int x) {
        inStack.push(x);
    }

    // 出队
    int pop() {
        if (outStack.empty()) {
            while (!inStack.empty()) {
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
        int val = outStack.top();
        outStack.pop();
        return val;
    }
};

JavaScript实现

class MyQueue {
    constructor() {
        this.inStack = [];
        this.outStack = [];
    }

    // 入队
    push(x) {
        this.inStack.push(x);
    }

    // 出队
    pop() {
        if (this.outStack.length === 0) {
            while (this.inStack.length > 0) {
                this.outStack.push(this.inStack.pop());
            }
        }
        return this.outStack.pop();
    }
}

算法分析

从单次操作来看，pop 在最坏情况下需要将 inStack 中所有元素搬运到 outStack，时间复杂度为 $O(n)$ 。然而，从摊还分析的角度看，每个元素最多只会被：

压入 inStack 一次
从 inStack 弹出并压入 outStack 一次
从 outStack 弹出一次

因此，每个元素的总操作次数是常数级，整体摊还时间复杂度为：

push： $O(1)$
pop： $O(1)$ （均摊）

空间复杂度为 $O(n)$ ，其中 $n$ 为队列中元素数量。