你能用栈实现队列，再用队列实现栈吗？
你能用栈实现队列，再用队列实现栈吗？
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
上一篇文章我们一起学习了栈和队列这两个数据结构，今天我们来小试牛刀用两道LeetCode中的经典问题来练练手。
首先来看第一题：用栈实现队列。
用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false
说明：
- 你 只能 使用标准的栈操作 —— 也就是只有
push to top,peek/pop from top,size, 和is empty操作是合法的。 - 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
题解
这题的难度是Easy，所以我们直接来看进阶版，即将每一个操作的复杂度控制在
。
要用栈来实现队列，难点在于栈是先进后出的，而队列是先进先出的。最早入栈的元素都在栈的底部，我们没办法直接弹出，更何况是以
的复杂度弹出。
不过好在题目当中提示我们了，我们可以使用两个栈来完成。既然单独一个栈内的元素是先进后出的，我们先进后出两次，就变成先进先出的了。假设栈A中的元素是[1, 2, 3]，我们把它们全部弹出放入栈B当中，得到的结果是[3, 2, 1]，当我们从栈B获取元素时，顺序又变回了[1, 2, 3]。
我们整理一下逻辑，当调用push插入元素时，我们将元素存入栈A当中。当调用pop或者peek时，我们从栈B的栈顶获取元素。如果栈B为空，那么则将栈A中所有的元素出栈插入到栈B中，如果不为空，则直接弹出栈B栈顶的元素。
class MyQueue {
public:
stack<int> ski, sko;
MyQueue() {
}
void push(int x) {
ski.push(x);
}
int pop() {
if (sko.empty()) {
// 注意这里要转移栈A中所有元素
while (!ski.empty()) {
sko.push(ski.top());
ski.pop();
}
}
int ret = sko.top();
sko.pop();
return ret;
}
int peek() {
if (sko.empty()) {
while (!ski.empty()) {
sko.push(ski.top());
ski.pop();
}
}
return sko.top();
}
bool empty() {
return ski.empty() && sko.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();
*/
同样，我们也可以用队列来实现栈。LeetCode中同样有类似问题。
用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
注意：
- 你只能使用队列的基本操作 —— 也就是
push to back、peek/pop from front、size和is empty这些操作。 - 你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
题解
虽然表面上看问题和刚才差不多，但我们稍微一想就能发现，即使我们使用两个队列一个出一个进，但元素的顺序并不会发生变化。所以我们只能从结果上入手，在弹出时，栈返回的是最后出现的元素，而队列返回的是最先出现的元素。
在只能弹出队首元素的情况下，别无他法，只能每次把队列中的元素都弹出，最后一个弹出的元素就是要pop的答案。一种做法是可以使用两个队列，一个队列作为备份，每次弹出时弹出的元素的都存入备份中。第二种做法是只使用一个队列，不使用备份，将弹出的元素插入到当前队列末尾。
比如我们现在队列中元素是[1, 2, 3]，我们要pop的答案是3。所以要先把3之前的元素都弹出插入到末尾，变成[3, 1, 2]，这是我们再弹出队首即可。
代码如下：
class MyStack {
public:
queue<int> que;
MyStack() {
}
void push(int x) {
que.push(x);
}
int pop() {
int sz = que.size();
for (int i = 0; i < sz-1; i++) {
int f = que.front();
que.pop();
que.push(f);
}
int ret = que.front();
que.pop();
return ret;
}
int top() {
return que.back();
}
bool empty() {
return que.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();
*/
文章的内容就到这里，感谢大家的阅读，如果喜欢的话，恳请帮忙转发扩散。算法学习之旅，与你同行。