LeetCode 225. 用队列实现栈
程序员文章站
2022-07-14 12:14:10
...
题目描述
使用队列实现栈的下列操作:
- push(x) -- 元素 x 入栈
- pop() -- 移除栈顶元素
- top() -- 获取栈顶元素
- empty() -- 返回栈是否为空
思路
创建两个队列 q1,q2
-
入栈
将元素 x 直接放入 q1 队列中。
-
出栈
- 也就是把 q1 的队尾元素出队列,由于队列只能从队头出队,因此先把 q1 中除了队尾元素的其他值存到 q2 中
- 再把队尾元素也就是栈顶出队
- 最后将 q2 中的值存到 q1 中
-
获取栈顶元素
也就是获取 q1 的队尾元素
class MyStack {
public:
queue<int> q1, q2;
int i = 0;
int temp;
int res;
MyStack() {
}
void push(int x) {
q1.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int length1 = q1.size();
i = 0;
while(length1 > 1 && i < length1 - 1)
{
temp = q1.front();
q2.push(temp);
q1.pop();
i++;
}
res = q1.front();
q1.pop();
i = 0;
int length2 = q2.size();
while(i < length2)
{
temp = q2.front();
q1.push(temp);
q2.pop();
i++;
}
return res;
}
/** Get the top element. */
int top() {
return q1.back();
}
/** Returns whether the stack is empty. */
bool empty() {
return q1.empty();
}
};