用C#玩转数据结构：栈与队列的相互实现（C#栈实现队列与队列实现栈完整教程）

一、用两个栈实现一个队列

目标：实现一个类 MyQueue，支持 Enqueue（入队）、Dequeue（出队）、Peek（查看队首元素）和 Empty（判断是否为空）操作，但底层只使用两个栈。

思路：

• 使用两个栈：stackIn 用于入队，stackOut 用于出队。
• 当需要出队时，如果 stackOut 为空，则将 stackIn 中所有元素依次弹出并压入 stackOut。这样，stackOut 的顶部就是最早入队的元素。

using System;using System.Collections.Generic;public class MyQueue {    private Stack<int> stackIn;    private Stack<int> stackOut;    public MyQueue() {        stackIn = new Stack<int>();        stackOut = new Stack<int>();    }    public void Enqueue(int x) {        stackIn.Push(x);    }    public int Dequeue() {        if (stackOut.Count == 0) {            while (stackIn.Count > 0) {                stackOut.Push(stackIn.Pop());            }        }        return stackOut.Pop();    }    public int Peek() {        if (stackOut.Count == 0) {            while (stackIn.Count > 0) {                stackOut.Push(stackIn.Pop());            }        }        return stackOut.Peek();    }    public bool Empty() {        return stackIn.Count == 0 && stackOut.Count == 0;    }}

这个实现的关键在于“懒转移”——只有在 stackOut 为空且需要出队时，才把 stackIn 的内容倒过来。这样保证了每个元素最多被移动两次（入 stackIn、出 stackIn 入 stackOut、出 stackOut），时间复杂度均摊为 O(1)。

二、用两个队列实现一个栈

目标：实现一个类 MyStack，支持 Push（入栈）、Pop（出栈）、Top（查看栈顶元素）和 Empty（判断是否为空），但底层只使用两个队列。

思路（主队列法）：

• 使用两个队列：queueMain 和 queueHelper。
• 始终让 queueMain 保存元素，且队尾即为栈顶。
• 当执行 Pop 或 Top 时，将 queueMain 中除最后一个元素外的所有元素移到 queueHelper，然后处理最后一个元素。操作完成后，交换两个队列的角色。

using System;using System.Collections.Generic;public class MyStack {    private Queue<int> queueMain;    private Queue<int> queueHelper;    public MyStack() {        queueMain = new Queue<int>();        queueHelper = new Queue<int>();    }    public void Push(int x) {        queueMain.Enqueue(x);    }    public int Pop() {        // 将 queueMain 中除最后一个元素外全部移到 queueHelper        while (queueMain.Count > 1) {            queueHelper.Enqueue(queueMain.Dequeue());        }        int top = queueMain.Dequeue();        // 交换两个队列        var temp = queueMain;        queueMain = queueHelper;        queueHelper = temp;        return top;    }    public int Top() {        while (queueMain.Count > 1) {            queueHelper.Enqueue(queueMain.Dequeue());        }        int top = queueMain.Dequeue();        queueHelper.Enqueue(top); // 把它也移过去，保持数据完整        // 交换队列        var temp = queueMain;        queueMain = queueHelper;        queueHelper = temp;        return top;    }    public bool Empty() {        return queueMain.Count == 0;    }}

注意：Pop 操作的时间复杂度是 O(n)，因为每次都要移动 n-1 个元素。但在实际应用中，这种实现能帮助我们深刻理解栈与队列的差异。

三、总结与应用场景

通过以上两个例子，我们掌握了：

• 如何用 C#栈实现队列（双栈法，高效）
• 如何用 C#队列实现栈（双队列法，教学意义强）

这些技巧不仅出现在算法面试中，也在系统设计中有实际价值。例如，在某些受限环境中（如只能使用栈的虚拟机），你可能需要用栈模拟队列来实现任务调度。

作为 数据结构教程 的一部分，建议你动手敲一遍代码，并尝试添加单元测试验证其正确性。这将极大提升你的 C#编程基础 能力。

提示：在 .NET 中，Stack<T> 和 Queue<T> 都是泛型集合，性能优秀，日常开发可直接使用。但理解其底层原理，才能写出更高效的程序。