队列(Queue)的python实现及其应用

队列的说明

• 一个线性的数据结构
• 队列遵循FIFO的原则，First In ， First Out 即先进先出
• 队列头部为front，尾部为rear

队列的函数列表

代码实现

# author: HuYong
# coding=utf-8

class Queue:
def __init__(self):
        self.items = []

def isEmpty(self):
return self.items == []

def enqueue(self,item):
''''
 时间复杂度为 O(n)
 '''
        self.items.insert(0,item)

def dequeue(self):
'''
 时间复杂度为O(1)
 '''
return self.items.pop()

def size(self):
return len(self.items)

测试结果

q = Queue()
q.enqueue("first")
q.enqueue("second")
print q.dequeue()
print q.size()
print q.isEmpty()
print q.dequeue()
print q.isEmpty()

'''
first
1
False
second
True
'''

应用

Josephus problem

• 约瑟夫环问题，n人排成一个圆，从某个位置开始依次从1报数，报到m，则那个人退出，再重新报数，如此循环，求解最后留下的人。
• 这个问题可以用队列实现，就是将n人构成一个队列，模拟从队头报数，队头的人若报m则移出队列，不是则出队再入队（模拟圆环！！），等待下次到达队头。

def hotPotato(namelist, num):
    queue = Queue()
for each in namelist:
        queue.enqueue(each)

while queue.size() > 1 :
for i in range(num):
            queue.enqueue(queue.dequeue())
        queue.dequeue()

return queue.dequeue()

print hotPotato(["Bill","David","Susan","Jane","Kent","Brad"],7)#Susan

打印事务模拟

数学建模+计算机编程模拟Simulation: Printing Tasks