03.04、化栈为队

03.04、化栈为队1、题目描述实现一个MyQueue类该类用两个栈来实现一个队列。2、解题思路本题要求使用两个栈来实现一个队列。队列遵循先进先出FIFO的原则而栈遵循后进先出LIFO的原则。因此我们需要两个栈来模拟队列的行为pushS用于存储入队的元素。popS用于反转元素顺序以实现队列的出队操作。3、解题步骤入队操作 (push)将新元素直接压入到pushS栈中。出队操作 (pop)检查 popS 栈是否为空如果popS为空将pushS中的所有元素逐个弹出并压入popS。这一步将反转元素的顺序从而实现队列的 FIFO 行为。如果popS不为空直接弹出并返回popS的栈顶元素。获取队首元素 (peek)类似于pop操作只是我们不弹出popS栈的栈顶元素而是返回它。检查队列是否为空 (empty)队列为空的条件是pushS和popS都为空。4、代码详解class MyQueue { private: stackint pushS; // 入队栈 stackint popS; // 出队栈 public: MyQueue() {} void push(int x) { pushS.push(x); } int pop() { // 如果出队栈为空将入队栈的所有元素移到出队栈中 if (popS.empty()) { while (!pushS.empty()) { popS.push(pushS.top()); pushS.pop(); } } int ret popS.top(); // 获取出队栈的栈顶元素 popS.pop(); // 弹出该元素 return ret; } int peek() { // 如果出队栈为空将入队栈的所有元素移到出队栈中 if (popS.empty()) { while (!pushS.empty()) { popS.push(pushS.top()); pushS.pop(); } } return popS.top(); // 返回出队栈的栈顶元素 } bool empty() { return pushS.empty() popS.empty(); } };5、时间复杂度入队操作 (push)O(1)出队操作 (pop)均摊 O(1)因为每个元素最多只会从pushS转移到popS一次。获取队首元素 (peek)均摊 O(1)检查队列是否为空 (empty)O(1)6、空间复杂度使用了两个栈存储元素空间复杂度为 O(n)其中 n 是队列中元素的数量。这道题通过使用两个栈成功模拟了队列的行为展示了栈和队列之间的转换关系。