Python编程题34--用队列实现栈

题目

栈和队列是常见的数据结构，队列的特点是 先进先出，而栈的特点是 先进后出。

请使用 队列 模拟实现栈的下列操作：

• push(x) -- 将元素 x 压入栈顶
• pop() -- 移除并返回栈顶元素
• top() -- 获取栈顶元素
• empty() -- 判断栈是否为空

说明：

• 可以用 列表list 来模拟队列，但只允许使用队列的基本操作。
• 假设每次调用 pop 和 top 都能保证栈不为空。

实现思路

• 使用两个队列，一个作为实际队列 queue1 ，另一个作为临时队列 queue2
• 每次 push 入栈操作，直接把 待入栈的新元素 添加到 queue1 的队尾即可
• 每次 pop 出栈操作，需要循环对 queue1 执行出队操作，并把出队的元素依次添加到 queue2 的队尾（最后一个出队的元素不添加），接着再反过来操作，循环对 queue2 执行出队操作，并把出队的元素依次添加到 queue1 的队尾
• 每次 top 获取栈顶元素操作，可以复用出栈操作的实现（但要记得把出栈元素重新添加到queue1），从而拿到栈顶的元素
• 每次 empty 操作，只需判断 queue1 是否为空

代码实现

class MyStack:

    def __init__(self):
        self.queue1 = []  # 实际队列
        self.queue2 = []  # 临时队列

    def push(self, x):
        self.queue1.append(x)

    def pop(self):
        while len(self.queue1) > 1:
            self.queue2.append(self.queue1.pop(0))
        res = self.queue1.pop(0)
        while self.queue2:
            self.queue1.append(self.queue2.pop(0))
        return res

    def top(self):
        res = self.pop()
        self.queue1.append(res)
        return res

    def empty(self):
        return self.queue1 == []

上面方法使用了两个队列来实现，那么如果限制只能使用一个队列的话，又该要如何优化实现呢？

其实并不难，我们只需在模拟出栈操作时，将队头的元素（除了最后一个元素外），依次执行出队操作，并重新添加到队尾，这样一来只需要使用一个队列即可实现栈的操作。

优化后的代码实现

class MyStack:

    def __init__(self):
        self.queue1 = []

    def push(self, x):
        self.queue1.append(x)

    def pop(self):
        len1 = len(self.queue1)
        while len1 > 1:
            self.queue1.append(self.queue1.pop(0))
            len1 -= 1
        return self.queue1.pop(0)

    def top(self):
        res = self.pop()
        self.queue1.append(res)
        return res

    def empty(self):
        return self.queue1 == []

更多Python编程题，等你来挑战：Python编程题汇总（持续更新中……）