leetcode232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):
实现 MyQueue 类:
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空,返回 true ;否则,返回 false
说明:
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is 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
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)
目录
题目分析
这是一个关于使用栈实现队列的算法题。题目要求实现一个队列,其主要操作包括push
(入队)、pop
(出队)、peek
(查看队头元素)和empty
(判断队列是否为空)。这里的关键在于如何使用两个栈来模拟队列的行为。
算法介绍
栈是一种后进先出(Last In First Out, LIFO)的数据结构,而队列是一种先进先出(First In First Out, FIFO)的数据结构。要使用栈来实现队列,我们需要两个栈:一个用于模拟队列的入队操作,另一个用于模拟队列的出队操作。
- 当执行
push
操作时,直接将元素压入第一个栈(stIn
)。 - 当执行
pop
或peek
操作时,如果第二个栈(stOut
)为空,则将第一个栈的所有元素移动到第二个栈中,然后执行相应的操作。 empty
操作需要检查两个栈是否都为空。
算法步骤
- 初始化两个空栈:
stIn
和stOut
。 push
操作:将元素压入stIn
。pop
操作:- 如果
stOut
为空,将stIn
的所有元素移动到stOut
。 - 从
stOut
弹出顶部元素并返回。
- 如果
peek
操作:- 执行
pop
操作。 - 将弹出的元素重新压入
stOut
。 - 返回该元素。
- 执行
empty
操作:检查stIn
和stOut
是否都为空。
算法代码
class MyQueue {
public:
stack<int> stIn;
stack<int> stOut;
MyQueue() {
}
void push(int x) {
stIn.push(x);
}
int pop() {
if(stOut.empty())
{
while(!stIn.empty())
{
stOut.push(stIn.top());
stIn.pop();
}
}
int result=stOut.top();
stOut.pop();
return result;
}
int peek() {
int res=this->pop();
stOut.push(res);
return res;
}
bool empty() {
return stIn.empty() && stOut.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
算法流程图
算法分析
- 时间复杂度:
push
操作:O(1)。pop
和peek
操作:最坏情况下(当stOut
为空时)需要将所有元素从stIn
转移到stOut
,时间复杂度为O(n)。empty
操作:O(1)。
- 空间复杂度:O(n),其中n是队列中的元素数量。
- 易错点:
- 在
pop
操作中,确保在stOut
为空时才移动stIn
中的元素。 - 在
peek
操作中,弹出元素后需要将其再次压入stOut
。
- 在
相似题目
题目 | 链接 |
---|---|
用队列实现栈 | LeetCode 225 |
最小值栈 | LeetCode 155 |
栈的压入、弹出序列 | LeetCode 946 |
请注意,以上表格仅为示例,实际链接可能需要根据具体平台和题目编号进行调整。
标签:stIn,leetcode232,队列,pop,用栈,stOut,push,empty From: https://blog.csdn.net/qq_51350957/article/details/142316801