9-1. 用两个栈实现队列

题目描述：

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

代码：

class Solution:
    def __init__(self):
        self.stack1, self.stack2 = [], []
    
    def push(self, x):
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        self.stack1.append(x)
        while self.stack2:
            self.stack1.append(self.stack2.pop())
    
    def pop(self):
        return self.stack1.pop()
    
    # 下面这两个是额外加上去的
    def peek(self): # 取出队列头部的元素
        return self.stack1[-1]
    
    def empty(self):
        return not self.stack1

思路分析：

假设已经有了一个栈stack1，我们需要一个额外的栈stack2：每新来一个元素，我们都把stack1中原有的元素全部搬到stack2中，然后将新来的元素append到stack1中，最后再把原来的元素再搬回来，这样新来的元素将总是会出现在栈底，弹出元素时依旧弹出栈顶的元素，这样便可以实现“先进先出”。