LeetCode刷题实战225：用队列实现栈
共 3322字，需浏览 7分钟
· 2021-03-31
Implement a last in first out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal queue (push, top, pop, and empty).
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
示例
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
解题
class MyStack {
public:
queue<int> q1,q2;
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
while(!q2.empty()) {
q1.push(q2.front());
q2.pop();
}
q2.push(x);
while(!q1.empty()) {
q2.push(q1.front());
q1.pop();
}
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int a = q2.front();
q2.pop();
return a;
}
/** Get the top element. */
int top() {
return q2.front();
}
/** Returns whether the stack is empty. */
bool empty() {
return q2.empty();
}
};