当前位置：首页 > news >正文

C# 使用堆栈实现队列

news 2025/7/21 14:54:50

232 使用堆栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（、、、）：pushpoppeekempty

实现类：MyQueue

void push(int x)将元素 x 推到队列的末尾
int pop()从队列的开头移除并返回元素
int peek()返回队列开头的元素
boolean empty()如果队列为空，返回；否则，返回truefalse
说明：

你只能使用标准的栈操作 —— 也就是只有 , , , 和操作是合法的。push to toppeek/pop from topsizeis empty
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

1 <= x <= 9
最多调用次、、和100pushpoppeekempty
假设所有操作都是有效的（例如，一个空的队列不会调用或者操作）poppeek

解决方案：

提供思路

将一个栈当作输入栈，用于压入 push 传入的数据；另一个栈当作输出栈，用于 pop和 peek操作。

每次 pop 或 peek时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

上代码：

public class MyQueue
{Stack<int> inStack;Stack<int> outStack;public MyQueue(){inStack = new Stack<int>();outStack = new Stack<int>();}public void Push(int x){inStack.Push(x);}public int Pop(){if (outStack.Count == 0){In2Out();}return outStack.Pop();}public int Peek(){if (outStack.Count == 0){In2Out();}return outStack.Peek();}public bool Empty(){return inStack.Count == 0 && outStack.Count == 0;}private void In2Out(){while (inStack.Count > 0){outStack.Push(inStack.Pop());}}
}