题目
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作：
push(int x) 将元素 x 压入栈顶
pop() 移除并返回栈顶元素
top() 返回栈顶元素
empty() 如果栈是空的，返回 true ；否则，返回 false
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
例：
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
方法一：两个队列
与使用两个栈实现队列的先进先出思路不同，当使用两个队列实现先进后出时，其中一个队列用于备份数据
- 使用双端队列进行模拟操作，queue_in 用于存储元素，queue_out 用于移除操作
- push 为将元素压入栈顶，即将元素推到 queue_in 队列的末尾
- pop 为将栈顶元素移除和返回，即将 queue_in 队尾的元素移除并返回，即将 queue_out 队列的元素移除并返回。首先，应判断是否为空队列。其次，将 queue_in 队列除队尾以外的元素均按照原顺序依次移入 queue_out 队列，后交换两个队列的元素。最终输出 queue_out 队列的元素
- top 为返回栈顶元素，即返回 queue_in 队列的末尾元素。首先，应判断是否为空队列。若队列不为空，那么返回末尾元素
- empty 为判断是否为空栈，即判断 queue_in 队列是否为空
class MyStack(object):
def __init__(self):
self.queue_in = deque()
self.queue_out = deque()
def push(self, x):
self.queue_in.append(x)
def pop(self):
if self.empty():
return None
for i in range(len(self.queue_in)-1):
self.queue_out.append(self.queue_in.popleft())
self.queue_in, self.queue_out = self.queue_out, self.queue_in
return self.queue_out.pop()
def top(self):
if self.empty():
return None
return self.queue_in[-1]
def empty(self):
return len(self.queue_in) == 0
# 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()
方法二：一个队列
当使用一个队列实现先进后出时，与使用两个队列不同之处在于进行 pop 操作时。此时，我们没有另一个队列来实现备份，那么可以通过将除队列末尾元素以外的所有元素按照原顺序依次移入该队列的末尾
class MyStack:
def __init__(self):
self.que = deque()
def push(self, x):
self.que.append(x)
def pop(self):
if self.empty():
return None
for i in range(len(self.que)-1):
self.que.append(self.que.popleft())
return self.que.popleft()
def top(self):
if self.empty():
return None
return self.que[-1]
def empty(self):
return not self.que
相关知识
-
deque：
双端队列
append()： 将元素从右侧移入队列
pop()： 将右侧末尾元素从队列移除
popleft()： 将左侧末尾元素从队列移除
a = deque()
a.append()
a.pop()
a.popleft()
-
list 和 deque 区别：
deque 的 append 和 pop 操作的时间复杂度是O(1)
list 的 append 和 pop 操作的时间复杂度是O(n)
参考
代码相关：https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html
