文章目录
- 一、题目
- 二、解法
- 三、完整代码
所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。
一、题目
二、解法
思路分析:这道题要求我们用栈模拟队列(工作上一定没人这么搞)。程序当中,push函数很好解决,直接将元素push进输入栈当中。pop函数需要实现队列先进先出的操作,而栈是先进后出。只用一个栈是无法实现,需要两个栈,一个输入栈,一个输出栈。输入栈当中,先进栈的元素在栈底所以后出,此时我们将输入栈的元素push进输出栈,先进的元素就在栈顶,会先输出,这样就实现了先进先出的队列。peek函数复用了pop函数,实现代码缩减。最后empty函数,只要输入栈和输出栈同时为空那么队列就是空的。
程序如下:
class MyQueue {
public:
stack<int> stIn;
stack<int> stOut;
MyQueue() { // 构造函数
}
void push(int x) {
stIn.push(x);
}
int pop() {
if (stOut.empty()) { // 只有当Out栈为空的时候,才将In栈的元素全部导入Out栈
while (!stIn.empty()) {
stOut.push(stIn.top());
stIn.pop();
}
}
int result = stOut.top();
stOut.pop();
return result;
}
int peek() {
int res = this->pop(); // 直接使用已经写好的pop函数
stOut.push(res); // 已经弹出,再添加回去
return res;
}
bool empty() {
return stIn.empty() && stOut.empty();
}
};
复杂度分析:
- 时间复杂度: push和empty为 O ( 1 ) O(1) O(1), pop和peek为 O ( n ) O(n) O(n)。
- 空间复杂度: O ( n ) O(n) O(n)。
三、完整代码
# include <iostream>
# include <stack>
using namespace std;
class MyQueue {
public:
stack<int> stIn;
stack<int> stOut;
MyQueue() { // 构造函数
}
void push(int x) {
stIn.push(x);
}
int pop() {
if (stOut.empty()) { // 只有当Out栈为空的时候,才将In栈的元素全部导入Out栈
while (!stIn.empty()) {
stOut.push(stIn.top());
stIn.pop();
}
}
int result = stOut.top();
stOut.pop();
return result;
}
int peek() {
int res = this->pop(); // 直接使用已经写好的pop函数
stOut.push(res); // 已经弹出,再添加回去
return res;
}
bool empty() {
return stIn.empty() && stOut.empty();
}
};
int main()
{
int x = 10;
MyQueue* obj = new MyQueue();
obj->push(x);
obj->push(x);
int param_2 = obj->pop();
int param_3 = obj->peek();
bool param_4 = obj->empty();
system("pause");
return 0;
}
end