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

为什么叫'懒惰'？ 数据转移不是在 Push 时立即执行，也不是每次 Peek 都执行，而是只在不得不执行的时候才触发——即当输出栈 s2 为空时。一旦触发，必须将 s1 中的所有元素一次性全部转移到 s2。

这个策略避免了不必要的重复转移。只要 s2 非空，所有的 Peek/Pop 操作都能以 O(1) 的速度进行，直到 s2 被耗尽。

出队操作：myQueuePop

// [摊还 O(1)，最坏 O(N)] 队列出队操作
int myQueuePop(MyQueue* obj) {
    assert(obj);
    
    // 复用 Peek 逻辑，确保队头元素已就位
    int ret = myQueuePeek(obj);
    
    // 弹出栈顶元素
    STPop(&(obj->s2));
    
    return ret;
}

实现极其优雅，完全复用了 myQueuePeek 的核心逻辑。调用 Peek 既解决了数据可用性（若 s2 为空则触发转移），又返回了正确顺序的队头元素，随后只需一次 O(1) 的 STPop 即可完成移除。

判空操作：myQueueEmpty

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

队列中的所有元素要么在输入栈 s1 中（待处理），要么在输出栈 s2 中（待取出）。因此，充要条件是两个存储位置都必须是空的。

内存管理与辅助函数

创建与销毁

C 语言编程中，动态数据结构的内存管理至关重要。

初始化策略：

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

采用自底向上的初始化策略，先分配外部结构体，再初始化内部栈，保证对象完全可用。

销毁顺序：

void myQueueFree(MyQueue* obj) {
    STDestroy(&(obj->s1));
    STDestroy(&(obj->s2));
    free(obj);
}

必须先释放内部栈的动态数组空间，最后释放结构体本身。顺序颠倒会导致内存泄漏。

算法全面分析

时间复杂度：摊还 O(1)

双栈实现队列的性能优势在于其摊还时间复杂度为 O(1)。

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

每个元素只会被移动两次：一次 Push 到 s1，另一次从 s1 转移到 s2。这种平滑峰值延迟的特性，使得它在实际应用中表现出和原生队列一样的高效性能。

空间复杂度

• 数据存储：所有 N 个元素分别存储在 s1 和 s2 的动态数组中，总空间复杂度为 O(N)。
• 结构体开销：元数据开销为 O(1)。
• 对比链表：基于数组的双栈实现具有更好的缓存局部性，通常优于传统链表实现。

扩展思考

线程安全

在多线程环境中，需引入互斥锁保护临界区，特别是在执行懒惰转移操作的整个过程中。

泛型支持

C 语言可通过 void* 指针让栈存储数据的指针，用户自行进行类型转换，或使用宏生成代码来实现泛型。

面试常见问题

• Q: 为什么 Push 时不能直接转移数据？ A: 否则 Push 会退化为 O(N)，且打乱 s2 中的正确顺序。
• Q: 转移时为什么必须一次性转移所有元素？ A: 只转移一个会导致下次 Pop 时仍需再次转移，效率极低。一次性转移保证了 s1 中最底部的元素被放到 s2 顶部，等待连续 N 次的 O(1) Pop。

通过组合和精妙的转移策略，我们实现了功能上的完美模拟和性能上的高效保证。理解其背后的摊还分析原理，是掌握工业级算法设计的关键。