本文共 1274 字，大约阅读时间需要 4 分钟。

剑指offer—两个栈实现队列

题目描述：

使用一个栈stack1 来存储队列插入的值，使用另一个栈stack2 来进行队列删除。因为队列是先进先出，而栈是后进先出的，因此插入将先把值插入到stack1 中，删除时需要改变值的顺序，将stack1 中栈顶的值一次pop（） 到stack2 中，此时stack2 中的栈顶元素就变为了最先进行到队列中的元素，弹出即完成了出队列工作。

# -*- coding:utf-8 -*-class Solution:    def __init__(self):        self.stack1 = []        self.stack2 = []    def push(self, node):        self.stack1.append(node)    def pop(self):        if len(self.stack2) == 0:            if len(self.stack1) == 0:                return None            else:                for i in range(len(self.stack1)):                    self.stack2.append(self.stack1.pop())        return self.stack2.pop()

该题可以扩展为使用两个队列来实现一个栈：同样的使用两个队列queue1 和queue2 来分别进行入栈和出站操作。入栈时将元素压入queue1 中，出栈时需要pop 出queue1 中的最后被压入的元素。因此将最后被压入元素的前几个元素压入到queue2 中，这时queue1 中就值剩下了最后被压入的元素，将其pop 出即可。在这里将queue1和queue2 进行交换，便于继续pop 操作。

class Solution:    def __init__(self):        self.queue1 = []        self.queue2 = []    def push(self, node):        self.queue1.append(node)    def pop(self):        if len(self.queue1) == 0:            return None        while len(self.queue1) != 1:            self.queue2.append(self.queue1.pop())        self.queue2, self.queue1 = self.queue1, self.queue2        return self.queue2.pop()

转载地址：http://xqmws.baihongyu.com/