leetcode
题目描述
使用队列实现栈的下列操作：
- push(x) -- 元素 x 入栈
- pop() -- 移除栈顶元素
- top() -- 获取栈顶元素
- empty() -- 返回栈是否为空
解题思路
- 可以使用两个队列
- 也可以使用一个队列，我们在此只讲述双队列
- 当使用队列实现栈时，另一个队列发挥着临时存储的作用
- 队列先进先出和栈先进后出的特性要理解
最终代码
class MyStack {
public:
queue<int> queueOne;
queue<int> queueTwo;
MyStack() {
}
void push(int x) {
queueOne.push(x);
}
int pop() {
int size = queueOne.size();
// 为了在queueOne中留下一个
size--;
while (size--) {
// 将queueOne的数据全部临时存储到queueTwo中
queueTwo.push(queueOne.front());
queueOne.pop();
}
// 返回结果
int result = queueOne.front();
queueOne.pop();
// 将queueTwo赋值给queueOne
queueOne = queueTwo;
// 清空queueTwo
while (!queueTwo.empty()) {
queueTwo.pop();
}
return result;
}
int top() {
return queueOne.back();
}
bool empty() {
return queueOne.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
