队列 Queue 建立
class Queue:
def __init__(self):
self.items = []
def is_empty(self):
return self.items ==[]
# input在前，output在后
def enqueue(self, item):
self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
def show(self):
return self.items用stack在python中解决实际问题
击鼓传花（hot potato）
击鼓传花问题，使用queue进行一个循环，敲打的次数为num，当敲打完毕，quene尾的小朋友被剔除，queue中最后的人即为胜者。
每一次循环的过程为：queue尾的小朋友重制到queue前，即sim_queue.enqueue(sim_queue.dequeue())
def hot_potato(name_list, num):
sim_queue = Queue()
for name in name_list:
sim_queue.enqueue(name)
while sim_queue.size()>1:
for i in range(num):
sim_queue.enqueue(sim_queue.dequeue())
sim_queue.dequeue()
return sim_queue.dequeue()
print(hot_potato(["Bill", "David", "Susan", "Jane", "Kent",
"Brad"], 20))Bill
打印机问题
学校的打印店是一个嘈杂的地方，有时一个打印机连着几台电脑，这个时候先按print的那一台在队列前面，这很好理解。 
实现这个算法需要建立两个class，分别是Printer & Task。
假设printer一分钟可以打印纸的张数为page_rate，每个task的纸张数只能为1-20之间。
具体步骤
- 创建一个task queue，每个task一旦入队给一个时间标签
- For every second:
- 检查是否新的task被创建了，如果是，将他放入task queue中，并将此时的时间作为时间标签
- 如果printer不busy且task正在等待
- dequeue下一个task且将其置入printer
- 用当前时间减去该task的时间戳，计算该task的等待时间
- 将这个task的等待时间放入list中
- 根据这个task的纸张数目，计算完成这个task需要的时间
- 一秒过去了～～～
- 如果这个task完成了，或者说需要的时间减少为0，那么printer也不在busy了
- 根据list中的时间计算平均等待时间
class Printer:
def __init__(self, ppm):
self.page_rate = ppm # pages per minute
self.current_task = None
self.time_remaining =0
def tick(self): # 1 second goes by
if self.current_task != None:
self.time_remaining = self.time_remaining-1
if self.time_remaining <=0:
self.current_task = None
def busy(self):
if self.current_task != None:
return True
else:
return False
def start_next(self, new_task):
self.current_task = new_task
self.time_remaining = new_task.get_pages() * 60 / self.page_rateimport random
class Task:
def __init__(self, time):
self.timestamp = time
self.pages = random.randrange(1,20) #每个task的pages随机产生
def get_stamp(self):
return self.timestamp
def get_pages(self):
return self.pages
def wait_time(self, current_time):
return current_time - self.timestamp模拟过程
def simulation(num_seconds, ppm):
lab_printer = Printer(ppm)
print_queue = Queue()
waiting_times = []
for current_second in range(num_seconds):
if new_print_task(): # 每秒有1/180的概率产生一个新的task
task = Task(current_second)
print_queue.enqueue(task)
if (not lab_printer.busy()) and (not print_queue.is_empty()):
next_task = print_queue.dequeue()
waiting_times.append(next_task.wait_time(current_second))
lab_printer.start_next(next_task)
lab_printer.tick()
average_wait = sum(waiting_times)/len(waiting_times)
print("Average Wait %6.2f secs %3d tasks remaining."%(average_wait, print_queue.size()))
def new_print_task():
num = random.randrange(1, 181)
if num == 180:
return True
else:
return False
for i in range(10):
simulation(3600,5)Average Wait 173.06 secs 2 tasks remaining.
Average Wait 102.06 secs 0 tasks remaining.
Average Wait 69.00 secs 1 tasks remaining.
Average Wait 191.58 secs 4 tasks remaining.
Average Wait 29.80 secs 0 tasks remaining.
Average Wait 136.38 secs 0 tasks remaining.
Average Wait 56.15 secs 0 tasks remaining.
Average Wait 160.18 secs 0 tasks remaining.
Average Wait 301.59 secs 4 tasks remaining.
Average Wait 107.88 secs 0 tasks remaining.
双端队列 deques
双端队列中的元素可以从两端弹出，插入和删除操作限定在队列的两边进行。
deques 建立
class Deque:
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def add_front(self, item):
self.items.append(item)
def add_rear(self, item):
self.items.insert(0,item)
def remove_front(self):
return self.items.pop()
def remove_rear(self):
return self.items.pop(0)
def size(self):
return len(self.items)由上述代码可以看出，从front端插入和删除的时间复杂度为O(1)，从rear端插入和删除的操作的时间复杂度为O(n)
deque应用：回文检查
回文：一个string顺序读和倒序读是一样的，如radar
方法： 将string储存到deque中，提取the rear和the front，然后进行比较。
def pal_checker(a_string):
char_deque = Deque()
for ch in a_string:
char_deque.add_rear(ch)
still_equal = True
while char_deque.size()>1 and still_equal:
first = char_deque.remove_front()
last = char_deque.remove_rear()
if first != last:
still_equal = False
return still_equal
print(pal_checker("lsdkjfskf"))
print(pal_checker("radar"))False
True