描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false提示：
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/implement-queue-using-stacks
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。
在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。
最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。
在代码实现的时候，会发现pop() 和 peek()两个函数功能类似，代码实现上也是类似的，可以思考一下如何把代码抽象一下。
C++
class MyQueue {
public:
stack<int> stIn;//进栈
stack<int> stOut;//出栈
MyQueue() {
}
void push(int x) {
stIn.push(x);
}
int pop() {
// 只有当stOut为空的时候，再从stIn里导入数据（导入stIn全部数据）
if(stOut.empty()){
// 从stIn导入数据直到stIn为空
while(!stIn.empty()){
stOut.push(stIn.top());
stIn.pop();
}
}
int result = stOut.top(); // 为后面peek()函数做准备
stOut.pop();
return result;
}
int peek() {
int result = this->pop(); // 直接使用已有的pop()函数
stOut.push(result); // 再把pop()弹出的元素添加回去
return result;
}
bool empty() {
return stIn.empty() && stOut.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();
*/Python
class MyQueue:
def __init__(self):
self.stIn = [] # 入栈
self.stOut = [] # 出栈
def push(self, x: int) -> None:
self.stIn.append(x)
def pop(self) -> int:
if(len(self.stOut) == 0):
while(len(self.stIn) != 0):
self.stOut.append(self.stIn[-1])
self.stIn.pop()
result = self.stOut[-1]
self.stOut.pop()
return result
def peek(self) -> int:
ans = self.pop()
self.stOut.append(ans)
return ans
def empty(self) -> bool:
return len(self.stIn)==0 and len(self.stOut)==0
# 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()上面的代码中，MyQueue 类实现了一个队列。它使用两个栈 inStack 和 outStack，其中 inStack 用于插入元素，outStack 用于删除元素。下面对每个函数进行详细说明：
MyQueue()：构造函数，无需实现。push(int x)：在队列尾部插入元素。直接将元素压入输入栈inStack中。pop()：在队列头部删除元素。先调用peek()获取队首元素，然后将输出栈outStack的栈顶元素出栈，最后返回队首元素。peek()：获取队列头部的元素。如果输出栈outStack为空，将输入栈inStack中的元素逐个弹出并压入输出栈outStack中，直到输入栈inStack为空。然后返回输出栈outStack的栈顶元素。empty()：判断队列是否为空。如果输入栈inStack和输出栈outStack都为空，则队列为空。
这里需要注意的是，在 peek() 函数中，我们需要判断输出栈 outStack 是否为空，如果为空，需要将输入栈 inStack 中的元素逐个弹出并压入输出栈 outStack 中。这样做的原因是，输出栈 outStack 存储了队列的元素，而输入栈 inStack 存储了最新插入的元素。如果我们直接从输入栈 inStack 中获取队首元素，那么队列中的元素顺序会被打乱，这显然是不符合队列的特性的。因此，我们需要将输入栈 inStack 中的元素逐个弹出并压入输出栈 outStack 中，这样就能保证输出栈 outStack 存储的是队列的元素，而且队首元素就在输出栈 outStack 的栈顶。
在插入元素时，由于我们只需要将元素插入输入栈 inStack 中，因此插入元素的时间复杂度为 $O(1)$。在删除元素时，我们需要先调用 peek() 获取队首元素，然后将输出栈 outStack 的栈顶元素出栈，这两个操作的时间复杂度都为 $O(1)$。如果输出栈 outStack 不为空，那么我们直接返回输出栈 outStack 的栈顶元素，这个操作的时间复杂度也为 $O(1)$。只有当输出栈 outStack 为空时，我们需要将输入栈 inStack 中的元素逐个弹出并压入输出栈 outStack 中，这个操作的时间复杂度是 $O(n)$，其中 $n$ 是队列中的元素个数。不过由于这个操作只会在输出栈 outStack 为空时执行一次，因此平均时间复杂度仍然是 $O(1)$。
总的来说，我们使用两个栈 inStack 和 outStack，使得在删除元素时，我们可以将输出栈 outStack 中的元素依次弹出，实现了先进先出的队列特性。这个方法时间复杂度和空间复杂度都非常优秀，是一种比较经典的解法。
