5.2用队列实现栈（LC225-E）
算法：
其实这道题不用像上一道题一样，用两个队列实现栈。
由于队列的数据结构特性。用一个队列就可实现栈。
难点还是在出队的时候：
- 比如队列=[1,2,3]，要模拟一个栈
- 入栈就是直接append（其实就是C++中的push）
- 出栈时应该先出3，但是队列先出1
- 此时可以先把1取出来，再加入队列，即[2,3,1]
- 再把2取出来，再加入队列，即[3,1,2]
- 这个时候再取出队首3，也就模拟了出栈操作。
总结：
只要将队列首部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。
为什么用栈实现队列的时候要用两个栈？
因为栈底部是密封的，只有上面敞口；而队列前后都敞口。
所以队列可以实现“先从队首把1取出来，再加入队列”的操作，而栈要取数只能从最上面敞口的地方取。
Top算法：
对于 Python 中的序列类型（如列表、元组、字符串等），可以使用负数索引来访问元素。负数索引表示从序列的末尾开始计数，-1 表示最后一个元素，-2 表示倒数第二个元素，依此类推。
可以使用负数索引来访问队列的最后一个元素，如self.que[-1]。
调试过程：
Python普通的Queue或SimpleQueue没有类似于peek的功能
也无法用索引访问，在实现top的时候较为困难。
用list可以，但是在使用pop(0)的时候时间复杂度为O(n)
因此这里使用双向队列，我们保证只执行popleft()和append()，因为deque可以用索引访问，可以实现和peek相似的功能
class MyStack:def __init__(self):self.que = deque()def push(self, x: int) -> None:self.que.append(x)def pop(self) -> int:if self.empty():return Noneelse:for i in range(len(self.que)-1):self.que.append(self.que.pop())return self.que.pop()def top(self) -> int:if self.empty():return Noneelse:return self.que[-1]def empty(self) -> bool:return 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()
原因：
因为我的 `empty` 方法返回的是一个 `deque` 对象，而预期的返回类型是布尔值。
为了解决这个问题，可以将 `empty` 方法中的返回语句修改为 `return not self.que`。这样，如果队列为空，返回 `True`，否则返回 `False`。
正确代码：
class MyStack:def __init__(self):self.que = deque()def push(self, x: int) -> None:self.que.append(x)def pop(self) -> int:if self.empty():return Noneelse:for i in range(len(self.que)-1):self.que.append(self.que.pop())return self.que.pop()def top(self) -> int:if self.empty():return Noneelse:return self.que[-1]def empty(self) -> bool:return not self.que优化：
Top里面的que[-1]实际上用到了栈，因为直接获取了que的末尾元素。
其实可以类似pop函数，将队列首部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出的元素就是栈的首了
不过要把这个“栈首”再加回队列里面，因为top不改变栈。
- 比如队列=[1,2,3]，要模拟一个栈
- 出栈时应该先出3，但是队列先出1
- 此时可以先把1取出来，再加入队列，即[2,3,1]
- 再把2取出来，再加入队列，即[3,1,2]
- 这个时候再取出队首3，也就是top，将其弹出
- 再把这个3加入队列，即[1,2,3]。其实没有改变栈的内容。
class MyStack:def __init__(self):self.que = deque()def push(self, x: int) -> None:self.que.append(x)def pop(self) -> int:if self.empty():return Noneelse:for i in range(len(self.que)-1):self.que.append(self.que.pop())return self.que.pop()def top(self) -> int:if self.empty():return Noneelse:for i in range(len(self.que)-1):self.que.append(self.que.pop())temp = self.que.pop()self.que.append(temp)return tempdef empty(self) -> 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()