使用队列实现栈的下列操作：
push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空
注意:
你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-stack-using-queues
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：# 双队列
## 思路
本题和[232. 用栈实现队列](https://github.com/azl397985856/leetcode/edit/master/problems/232.implement-queue-using-stacks.md) 思想稍有不同。 相同之处在于都可以采用双xx来解决。而这道题稍微难一点。
需要明确一点的是，本题我使用python的数组来模拟队列。Python 中 pop(0) 表示从数组头删除一个元素， append(x) 表示向数组尾部添加一个元素。 `也就是说除了这两个API，我们不可以用别的数组api，当然也不可以直接用索引来操作，这都是不允许的。`
- 我们初始化两个队列q1和q2。其中q1是主队列，q2是辅助队列。
- push往q1末尾添加元素
- pop的时候，q1往q2转移，直到q1只剩下最后一个元素。我们将其返回即可。最后我们调换q1和q2
- top的时候我们复用pop，这样我们的q1实际上会少一个元素，我们再将其append回去即可。
- empty只需要判断q1是否为空即可
## 代码
```python
class MyStack:
def __init__(self):
self.q1 = []
self.q2 = []
def push(self, x: int) -> None:
self.q1.append(x)
def pop(self) -> int:
while len(self.q1) > 1:
self.q2.append(self.q1.pop(0))
self.q1, self.q2 = self.q2, self.q1
return self.q2.pop(0)
def top(self) -> int:
ans = self.pop()
self.q1.append(ans)
return ans
def empty(self) -> bool:
return len(self.q1) == 0
```
**复杂度分析**
- 时间复杂度：ppo 和 top 为 $O(N)$， push, empty 为 $O(1)$
- 空间复杂度：$O(N)$
# 一个队列
## 思路
实际上q2可以不存在，我们假想一个q2队列，将q1队列本身看成q2。 这样我们只需要将上面的pop方法稍加改造即可，其他代码不需要变化，具体见下方代码区。
## 代码
```python
class MyStack:
def __init__(self):
self.q1 = []
def push(self, x: int) -> None:
self.q1.append(x)
def pop(self) -> int:
n = len(self.q1)
for _ in range(n - 1):
self.q1.append(self.q1.pop(0))
return self.q1.pop(0)
def top(self) -> int:
ans = self.pop()
self.q1.append(ans)
return ans
def empty(self) -> bool:
return len(self.q1) == 0
```
**复杂度分析**
- 时间复杂度：ppo 和 top 为 $O(N)$， push, empty 为 $O(1)$
- 空间复杂度：$O(1)$
# 延伸阅读
实际上现实中也有使用两个栈来实现队列的情况，那么为什么我们要用两个stack来实现一个queue？
其实使用两个栈来替代一个队列的实现是为了在多进程中分开对同一个队列对读写操作。一个栈是用来读的，另一个是用来写的。当且仅当读栈满时或者写栈为空时，读写操作才会发生冲突。
当只有一个线程对栈进行读写操作的时候，总有一个栈是空的。在多线程应用中，如果我们只有一个队列，为了线程安全，我们在读或者写队列的时候都需要锁住整个队列。而在两个栈的实现中，只要写入栈不为空，那么`push`操作的锁就不会影响到`pop`。
- [reference](https://leetcode.com/problems/implement-queue-using-stacks/discuss/64284/Do-you-know-when-we-should-use-two-stacks-to-implement-a-queue)
- [further reading](https://stackoverflow.com/questions/2050120/why-use-two-stacks-to-make-a-queue/2050402#2050402)
欢迎关注我的公众号《脑洞前端》获取更多更新鲜的LeetCode题解
LeetCode题解计算机为什么是基于二进制的？可以是三进制么？二进制有什么好处？题解：为什么叫电子计算机？算盘应该没有二进制
LeetCode题解深度优先遍历和回溯的关系？深度优先遍历的范围更大还是回溯的范围更大？为什么？题解：我的理解是：dfs是回溯思想的一种体现- 回溯：是在整个搜索空间中搜索出可行解，在搜索过程中不断剪枝回退，这是回溯的思想，这个搜索空间并没有限制于特定的数据结构。- dfs：dfs是指特定的数据结构中如图，树（特殊的图）中搜索答案，范围限制在了特定的数据结构。个人拙见。
LeetCode题解盲人买袜子。他们都各自买了两对黑袜和两对白袜，八对袜子的布质、大小完全相同，而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢？题解：暴力破解， 把袜子都拆开 一人一只 哈哈
LeetCode题解10个小球，随机分到12个盒子里，求恰好10个盒子都为空的概率。10个小球，随机分到12个盒子里，求恰好10个盒子都为空的概率。要求用程序模拟十万次，暴力求出该概率来自：字节跳动 算法工程师一面的第一题 （3月30日，60分钟，牛客网视频面）https://www.nowcoder.com/discuss/395924
LeetCode题解烧绳子烧一根不均匀的绳要用一个小时，如果要准确判断一个小时十五分钟，至少需要几根绳子？注意：- 每一根绳子虽然都可以烧一个小时，但均匀程度都不一样题解：三根1. 第一根点燃一头的同时，第二根两头同时点燃。2. 点燃两头的绳子燃尽时，同时点燃第一根绳子的另一头 并开始计时3. 等第一根绳子燃尽 再点燃第三根绳子的一头4. 燃尽 一小时十五分钟