栈与队列理论基础
栈是先进后出，队列是先进先出：
LeetCode232 用栈实现队列
题目链接/文章讲解/视频讲解：https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html
⭐2个栈模拟队列
用栈实现队列：使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。
执行语句：
queue.push(1);
queue.push(2);
queue.pop(); 注意此时的输出栈的操作
queue.push(3);
queue.push(4);
queue.pop();
queue.pop();注意此时的输出栈的操作
queue.pop();
queue.empty();
在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。
最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。
class MyQueue(object):
def __init__(self):
self.stack_in = [] # 入栈，push
self.stack_out = [] # 出栈，pop
def push(self, x):
"""
:type x: int
:rtype: None
"""
self.stack_in.append(x)
def pop(self):
"""
:rtype: int
"""
if not self.stack_out: # 出栈为空
while self.stack_in: # 当入栈不为空时，全部复制到出栈
self.stack_out.append(self.stack_in.pop())
return self.stack_out.pop() # 出栈
else: # 出栈不为空，直接弹出
return self.stack_out.pop() # 出栈
def peek(self):
"""
:rtype: int
"""
# 从出栈中找，复用pop代码
result = self.pop()
self.stack_out.append(result) # 再压栈
return result
def empty(self):
"""
:rtype: bool
"""
# 只要in或者out有元素，说明队列不为空
return not (self.stack_in or self.stack_out)
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
LeetCode225 用队列实现栈
题目链接/文章讲解/视频讲解：https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html
⭐一个队列模拟栈（两个队列也可以模拟栈，看文章讲解）
流程演示：
class MyStack(object):
def __init__(self):
self.que = deque()
def push(self, x):
"""
:type x: int
:rtype: None
"""
self.que.append(x)
def pop(self):
"""
:rtype: int
"""
for i in range(len(self.que) - 1):
self.que.append(self.que.popleft())
return self.que.popleft()
def top(self):
"""
:rtype: int
"""
res = self.pop()
self.que.append(res)
return res
def empty(self):
"""
:rtype: bool
"""
return not self.que
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
deque是栈和队列的一种广义实现，deque是”double-end queue”的简称https://blog.csdn.net/chl183/article/details/106958004
