摘要
- 用栈实现队列，用队列实现栈，虽然可能没有什么实际应用价值，但是对于熟悉栈和队列的结构以及基本操作是很有意义的。
- 用两个栈实现队列
- 通过让队列循环来实现栈
今日学习的视频和文章
- 代码随想录 栈和队列的基础
- C++Primer 栈和队列部分
- 数据结构基础C++语言版（第二版）栈和队列部分
LeetCode232 用队列实现栈
- 今天的题目比较简单，栈是后进先出，而队列是先进先出，用栈实现队列的关键就在于如何将后进先出转化为先进先出。
- 如果我们只用一个栈，能不能做到先进先出呢？由于题目要求只能使用栈的标准操作，而弹出先进的元素（即栈底的元素）前必须弹出在其之后的所有元素，所以我们应该用另一块内存空间来保留这部分元素。而这部分元素的弹出顺序是遵循栈的后进先出的，由对称性的想法，这另一个用来保存元素的空间也可以是栈的结构。
- 例如，这里元素1，2，3入栈，【或】表示栈底
- 栈in：【1，2，3 ；栈out：【
- 此时，根据队列的先进先出，我们要弹出1，将2，3保留在另一个栈中
- 栈in：【1；栈out：【3，2，
- 为了代码逻辑更加简洁，我们可以统一将栈1的元素都push进栈2中，而不是判断栈1是否还剩余1个元素
- 栈in：【；栈out：【3，2，1
- 此时在让栈2的栈顶元素出栈即可
- 栈in：【；栈out：【3，2
- 再插入元素到用栈实现的队列中的逻辑与元素出队列的逻辑是对称的，衔接上面的例子，我们要插入元素4，元素4是后进的，所以对于出栈来说它应该位于栈底：栈out【4，3，2
- 栈in：【；栈out：【3，2
- 此时，将栈out的元素push回栈in中
- 栈in：【2，3；栈out：【
- 然后再将元素4 push进栈in中
- 栈in：【2，3，4；栈out：【
- 这样就完成了元素4进入用栈实现的队列的操作
完整题解代码如下
class MyQueue {
private:
stack<int> in;
stack<int> out;
public:
MyQueue() {
}
void push(int x) {
while (!out.empty()) {
in.push(out.top());
out.pop();
}
in.push(x);
}
int pop() {
while (!in.empty()) {
out.push(in.top());
in.pop();
}
int temp = out.top();
out.pop();// 要注意这里的 pop 会返回值，而C++STL的栈的pop是不返回值的
return temp;
}
int peek() {
while (!in.empty()) {
out.push(in.top());
in.pop();
}
return out.top();
}
bool empty() {
return in.empty() && out.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();
*/
LeetCode225 用队列实现栈
- 初见题目时的想法：既然用两个栈能实现队列，那对称地来想，是不是能用两个队列来实现栈呢？
- 这里用【表示队列头，用】表示队列尾
- 假设元素1，2，3进入由队列实现的栈，那么根据后进先出，此时应该弹出的是元素3
- 队列1：【1，2，3】；队列2：【】
- 如果我们简单去类比用两个栈实现队列，想用两个队列实现栈的话
- 队列1：【】；队列2：【1，2，3】
- 上面的队列2再pop，还是弹出元素1而不是元素3。
- 因为队列是先进先出，即使我们模仿栈实现队列的思路，把要弹出的元素之前的元素保留在另一个队列中，也无法实现栈。因为在栈的后进先出，我们可以通过两个栈颠倒元素的弹出顺序；但是队列的弹出顺序就是我们将元素放入队列的顺序。
- 然后，我注意到，两个栈实现队列中，有一个地方被简化了逻辑：
- ”为了代码逻辑更加简洁，我们可以统一将栈1的元素都push进栈2中，而不是判断栈1是否还剩余1个元素“
- 实际上，我们只需要判断队列是否出队到只剩队尾元素（即最后一个进入队列的元素），然后在按顺序保存队列的其他元素时让队尾元素出队即可。
- 这样一来，实际上我们可以只用一个队列来实现栈，即让队首元素出队后再入队，直到我们遍历到原来的队尾元素，让其出队而不再入队即可。
- 例子：【1，2，3】-> 【2，3，1】-> 【3，1，2】-> 【1，2】
- 那么如何push元素到由队列实现的栈中呢？我们在上面实现的出栈操作中，是固定弹出队尾元素的，所以我们直接将元素push到队列中就好了。
完整的题解代码如下
class MyStack {
private:
queue<int> q;
public:
MyStack() {
}
void push(int x) {
q.push(x);
}
int pop() {
int count = 0;
while (count < q.size() - 1) {
q.push(q.front());
q.pop();
count++;
}
int temp = q.front();
q.pop();
return temp;
}
int top() {
int temp = pop();
push(temp);
return temp;
}
bool empty() {
return q.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();
*/
