什么是队列

​ 队列是有序集合，添加操作在”尾部”，移除操作在”头部”。新元素在尾部进入，然后一直向前移动到头部，直到称为下一个被移除的元素。

​ 这种操作叫做FIFO(first-in first out)。

​ 操作系统使用一些队列来控制计算机进程。调度机制往往基于一个队列算法，其目标是能尽可能的执行程序，同时服务尽可能多的用户。如打字的时候，有时候字符出现速度比敲键盘速度更慢，这是因为计算机正在做其他工作，敲键盘的操作被放在一个类似于队列的缓冲区，这样的话，便于对应的字符按正确的顺序显示。

队列抽象数据类型（操作）

  • Queue(): 创建一个空队列。它不需要参数，且返回一个空队列。
  • enqueue(item): 在队尾添加一个元素，需要参数，无返回值。
  • dequeue(): 在对头移除元素，不需要参数，有返回值（被删除的元素），并修改队列内容。
  • isEmpty(): 检查队列是否为空。无参数，返回布尔值。
  • size(): 返回队列中元素的数目，无参数，有返回值。

用Python实现队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Queue:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    def enqueue(self,item):
        self.items.insert(0,item)
    def dequeue(self):
        return self.items.pop()
    def size(self):
        return len(self.items)
    def printQueue(self):
        print (self.items)
q = Queue()
print(q.isEmpty())
q.enqueue(3)
q.enqueue('23')
q.enqueue("世界这么大")
q.enqueue("我想去去看看！")
print(q.size())
q.printQueue()

模拟，传土豆

​ 传土豆: 孩子们围成一圈，并且依次传递土豆。在某一个时刻，大家停止传递，此时手里面有土豆的孩子就得退出游戏。重复上诉过程，直至剩下一个孩子。（等价于约瑟夫问题）

​ 我们用队列来模拟一个环。假设捏着土豆的孩子在队头。在模拟传土豆的过程中，程序把这个队头孩子的名字移除，然后立刻插入队尾。随后，这个孩子会一直等待，直至再次到达队头。在出列和入列n次后，此时队头的孩子出局。新一轮游戏开始，如此反复，直至剩下最后一人（队列大小为1）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from pythonds.basic import  Queue
def Potato(nameList,num):
    simqueue = Queue()
    for name in nameList:
        simqueue.enqueue(name)
    while simqueue.size() > 1 :
        for i in range(num):

            simqueue.enqueue(simqueue.dequeue())
        print("踢掉：",simqueue.dequeue())

    return simqueue.dequeue()
a = (Potato(["1",'2','3','4','5','6'],7))
print(a)