1. 题目描述

232 用栈实现队列

2. 解题思路

使用两个栈stk1、stk2来模拟队列的入队与出队操作:

1. 入队操作直接将元素压入stk1栈中；
2. 出队时需要先判断stk2是否为空，若为空则需要将stk1的所有元素移至stk2，这时stk2栈中元素顺序即为队列元素出队的顺序，若不为空直接出队即可；
3. 取队列队首元素与出队操作类似；
4. 判空操作需要判断stk1与stk2是否同时为空。

3. 代码实现

class MyQueue {// 用以入队stack<int> stk1;// 用以出队stack<int> stk2;void move() {// 当stk2为空时,将stk1中的所有元素移到stk2中if (stk2.empty()) {while (!stk1.empty()) {stk2.push(stk1.top());stk1.pop();}}}public:MyQueue() {}void push(int x) { stk1.push(x); }// 首先判断stk2是否为空,若为空则将stk1中所有元素移到stk2中,// 实现元素的正向队列化排序,再从stk2中出栈栈顶元素即可int pop() {move();int x = stk2.top();stk2.pop();return x;}int peek() {move();return stk2.top();}bool empty() { return stk1.empty() && stk2.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();
*/