面试题9：用两个栈实现队列

题目描述

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

知识点

栈，队列

---

Qiang的思路

这是一道神奇的题，和用两个队列实现一个栈一样神奇。

栈的特点是先进后出，而队列的特点是先进先出，这也就意味着当出队一个元素时应该是最先进入的。而最先进入的元素却在栈底。OK，这里能够想到既然一个栈的话最先进入的元素在栈底，如果我将其依次出栈放到另一个栈里，那么最先进入的元素就跑到了栈顶，将其弹出就完成了对了的先进先出功能。

需要主要的是，当执行入队请求时，只需要将元素压入第一个栈即可。当出队时，需要将第二个栈的栈顶元素出栈，此时，如果第二个栈为空，就需要将第一个栈中所有的元素全部压入第二个栈才可以。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        self.stack1.append(node)
    def pop(self):
        # return xx
        if self.stack2 == []:
            while self.stack1 != []:
                self.stack2.append(self.stack1.pop())
        if self.stack2 == []:
            return None
        return self.stack2.pop()

这里对python的栈和队列做一些说明，在python中，list便可以实现栈和队列的功能：

• 栈：append() & pop()
• 队列：append(0) & pop()

---

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。