用两个栈模拟队列：LIFO 到 FIFO 的转换实现与复杂度分析

关键点在于：stackOut 只有在为空时才会被重新填充。一旦填充，后续操作直接从中读取，直到再次变空。

1.4 时间复杂度摊还分析

双栈实现队列的性能优势在于**摊还时间复杂度（Amortized Time Complexity）**为 O(1)。

• 最坏情况：发生在 s2 为空且 s1 中有 N 个元素时。此时需执行 N 次 Pop 和 Push 进行转移，耗时 O(N)。
• 最佳情况：s2 非空时，直接 Pop 或 Peek，耗时 O(1)。
• 摊还分析：考虑包含 N 次操作的序列。虽然某次转移可能耗时 O(N)，但接下来的 N-1 次操作都是 O(1)。平均下来，每次操作的成本为 O(N)/N = O(1)。

二、核心函数深度解析

2.1 myQueuePush 函数详解

功能：实现队列的入队操作（Enqueue）。

// [O(1)] 队列入队操作：将元素 x 压入输入栈 s1
void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    // 直接将新元素压入输入栈 s1
    STPush(&(obj->s1), x);
}

为什么只需简单压入 s1？ 这体现了职责分离原则。s1 的唯一职责就是接收入队请求。新元素 x 压入栈顶后，位于当前所有元素之'上'。未来进行 Pop 操作时，所有元素会被转移到 s2，此时 x 将位于 s2 的栈底，保证了它是最晚出队的元素，完美满足 FIFO 要求。

时间复杂度：假设底层栈的 STPush 是 O(1) 的，那么该函数严格为 O(1)。

2.2 myQueuePeek 函数详解

功能：获取队头元素（Front），但不移除。

// [摊还 O(1)，最坏 O(N)] 队列查看队头元素操作
int myQueuePeek(MyQueue* obj) {
    assert(obj);
    
    // 1. 检查输出栈 s2 是否为空
    if (STEmpty(&(obj->s2))) {
        // 2. 关键的'懒惰转移'策略：当 s2 为空时，才执行数据转移
        // 转移操作确保了 FIFO 的顺序：s1 的栈底（最早入队）将成为 s2 的栈顶
        while (!STEmpty(&(obj->s1))) {
            STDataType data = STTop(&(obj->s1));
            STPop(&(obj->s1));
            STPush(&(obj->s2), data);
        }
    }
    
    // 3. 返回 s2 的栈顶元素，即当前队头
    return STTop(&(obj->s2));
}

懒惰转移策略的设计哲学 数据转移不是在 Push 时立即执行，也不是在每次 Peek 时都执行。它只在不得不执行的时候触发，即当输出栈 s2 为空时。只要 s2 非空，所有的 Peek/Pop 操作都能以 O(1) 的速度进行。

摊还计算过程 在一个完整的生命周期中，假设总共 Push 了 K 个元素。这 K 个元素只会从 s1 转移到 s2 一次。转移总成本约为 O(K)，Pop/Peek 总次数也约为 K 次。因此，总操作次数约等于 2K 次，摊还成本 ≈ (O(K) + O(K)) / 2K = O(1)。

2.3 myQueuePop 函数详解

功能：移除并返回队头元素（Dequeue）。

// [摊还 O(1)，最坏 O(N)] 队列出队操作
int myQueuePop(MyQueue* obj) {
    assert(obj);
    
    // 1. 复用 myQueuePeek 获取队头元素
    // 此操作会确保 s2 非空，并在 s2 为空时触发数据转移
    int ret = myQueuePeek(obj);
    
    // 2. 将 s2 的栈顶元素弹出，完成移除操作
    STPop(&(obj->s2));
    
    // 3. 返回被移除的元素
    return ret;
}

复用 Peek 的巧妙设计 myQueuePop 完全复用了 myQueuePeek 的核心逻辑。调用 myQueuePeek 既解决了数据可用性（触发转移），又获取了返回值。随后只需执行一次 O(1) 的 STPop 即可移除元素。

边界条件处理 代码通过 assert 检查指针有效性。如果尝试对空队列进行 Pop，程序将断言失败，起到保护边界的作用。

2.4 myQueueEmpty 函数详解

功能：判断队列是否为空。

// [O(1)] 队列判空操作
bool myQueueEmpty(MyQueue* obj) {
    // 当且仅当输入栈 s1 和输出栈 s2 同时为空时，队列才为空
    return (STEmpty(&(obj->s1)) && STEmpty(&(obj->s2)));
}

判断逻辑 队列中的所有元素要么在输入栈 s1 中（待处理），要么在输出栈 s2 中（待取出）。只有当两个栈都为空时，队列才为空。该操作只包含两次 O(1) 的检查和一次逻辑与，时间复杂度严格为 O(1)。

三、内存管理与辅助函数

3.1 myQueueCreate 的初始化策略

MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    if (obj == NULL) {
        perror("malloc");
        exit(-1);
    }
    STInit(&(obj->s1)); // 初始化 s1
    STInit(&(obj->s2)); // 初始化 s2
    return obj;
}

采用自底向上的初始化策略：先分配上层结构体，再初始化内嵌的两个栈对象，保证新创建的队列是一个完全可用的空队列。

3.2 myQueueFree 的销毁顺序重要性

void myQueueFree(MyQueue* obj) {
    STDestroy(&(obj->s1)); // 1. 销毁 s1 占用的动态数组空间
    STDestroy(&(obj->s2)); // 2. 销毁 s2 占用的动态数组空间
    free(obj);             // 3. 释放 MyQueue 结构体本身的堆空间
}

销毁顺序至关重要：必须先释放内部栈的动态数组内存，最后才能释放外部结构体。如果顺序颠倒，先释放了 obj，将无法访问栈的内部指针，导致内存泄漏。

四、算法全面分析

4.1 与《用队列实现栈》的深度对比

这两道题就像一对'镜像问题'，共同揭示了数据结构抽象的强大魅力。它们都要求我们绕过数据结构的直接行为，通过对其基本操作的组合与调度，来构建新的语义。

4.2 时间复杂度的三种场景分析

正如第二部分所述，双栈队列的精妙之处在于将 O(N) 的高峰成本摊还成了 O(1) 的平均成本。这是一种非常重要的算法设计思想，允许我们在局部牺牲效率，以换取全局的效率保证。

4.3 空间复杂度分析

• 数据存储空间：所有 N 个元素分别存储在 s1 和 s2 的动态数组中，总空间复杂度为 O(N)。
• 结构体开销：外部结构体只包含元数据，开销为 O(1)。
• 总空间复杂度：O(N)。

与链表队列相比，基于双栈和动态数组实现的队列在空间效率和缓存性能（Cache Locality）方面通常更优，因为数组存储紧凑，无额外指针开销。

五、应用场景与扩展思考

5.1 实际应用场景

1. 任务调度系统：批处理环境中，任务快速入队（Push to s1）和顺序出队（Pop from s2）。
2. 数据流处理：处理网络数据包、日志记录等连续数据流，保持原有顺序。
3. 广度优先搜索（BFS）：作为底层存储结构。

5.2 扩展可能性

1. 如何实现线程安全版本？

引入互斥锁（Mutex）。在 myQueuePush 前后加锁解锁；在 myQueuePeek 和 myQueuePop 中，在执行懒惰转移操作的整个临界区加锁，确保原子性。

2. 如何支持泛型？

C 语言不支持原生泛型。可通过 void* 指针让栈存储数据的指针，用户自行类型转换；或使用宏生成不同数据类型的代码。

3. 双向队列（Deque）的思考

仅用两个栈无法高效实现双向队列。通常需要四个栈或双向链表来实现，这会显著增加复杂性。

结论与展望

双栈实现队列是一种将 LIFO 结构转化为 FIFO 结构的高级应用。通过职责分离的设计和懒惰转移的优化策略，我们实现了稳定的 O(1) 入队和优秀的 O(1) 均摊出队。理解其背后的摊还分析原理，是掌握工业级算法设计的关键。

附录：常见面试问题解析

• Q: 为什么 Push 时不能直接转移数据？ A: 如果每次 Push 都将 s1 中的数据转移到 s2 再加新元素，Push 操作将退化为 O(N)，且每次 Push 都会打乱 s2 中的正确顺序。
• Q: 转移操作时为什么必须一次性转移 s1 的所有元素？ A: 如果只转移一个元素，下一次 Pop 时 s1 的队头仍然在底部，无法取出，且转移操作会反复进行，效率极低。一次性转移保证了 s1 中最底部的元素被放到 s2 的顶部，等待连续 N 次的 O(1) Pop。
• Q: 如果使用 realloc 而不是 malloc，底层栈的实现会有什么变化？ A: 使用 realloc 在扩容时会更高效且更安全，能原地扩展内存或自动拷贝数据，使底层栈的 Push 操作在摊还意义上更稳定地保持 O(1)。