Python与数据结构——队列

定义

队列是一系列有次序的数据项的集合，数据项从一端添加，从另一端移除。数据项添加的一端称为队尾，数据项取出的一端称为队首。

队列的次序原则是“先进先出”，即先从队尾添加的数据项，先从队首移除。在实际生活中，排队就是遵循“先进先出”原则。

入队演示：

出队演示：

现有队列Q，对队列进行如下操作：

• Q.enqueue()：向队列中（队尾）添加数据项；
• Q.dequeue()：移除队列中（队首）的数据项；
• Q.isEmpty()：判断队列是否为空；
• len(Q)：返回队列的大小。

队列的实现

使用列表实现队列:

class Queue():
    # 创建队列
    def __init__(self):
        self.items = []

    # 判断队列是否为空
    def is_empty(self):
        return len(self.items) == 0

    # 入队
    def enqueue(self, item):
        self.items.insert(0, item)

    # 出队
    def dequeue(self):
        return self.items.pop()

    # 返回队列的大小
    def size(self):
        return len(self.items)
    
# queue = Queue()
# queue.enqueue(1)
# queue.enqueue(2)
# print(queue.items)      # 查看队列中的元素
# print(queue.dequeue())      # 删除队首
# print(queue.is_empty())     # 判断是否为空

### 运行结果
# [2, 1]
# 1
# False

我们在使用list类实现队列时，利用list.pop()实现了队列的出队操作，但是这种方法在每次实现出队操作时，都需要通过一个循环将队首右端的数据项向左移动一次。

为了优化程序，我们可以使用Python中的pythonds模块，这个模块提供了实现队列的方法。（LeetCode不提供pythonds模块）

from pythonds.basic.queue import Queue

queue = Queue()     # 创建一个队列
queue.enqueue(1)    # 向队列（队尾）添加一个数据项1
queue.dequeue()     # 移除队列（队首）的数据项
queue.isEmpty()     # 判断队列是否为空
queue.size()        # 返回队列的大小
queue.items         # 以列表形式返回队列

队列的应用

队列解决约瑟夫问题

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

from pythonds.basic.queue import Queue

# 创建队列
queue = Queue()
# 添加初始座位号
for i in range(1, 42):
    queue.enqueue(i)
    
n = 0       # 报数
while queue.size() > 2:
    n += 1      # 当前报数
    k = queue.dequeue()     # 当前报数的人
    # 如果当前报数为3，则杀掉这个人，不再入队，并重新报数
    if n == 3:      
        n = 0
    else:
         # 如果当前报数不为3，则重新将这个人加入队列
        queue.enqueue(k)       

print(queue.items)      # 打印最后活下来的两个人的初始座位号