• Reference: Problem Solving with Algorithms and Data Structures, Release 3.0

队列 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之间。

具体步骤

1. 创建一个task queue，每个task一旦入队给一个时间标签
2. For every second:
   • 检查是否新的task被创建了，如果是，将他放入task queue中，并将此时的时间作为时间标签
   • 如果printer不busy且task正在等待
     • dequeue下一个task且将其置入printer
     • 用当前时间减去该task的时间戳，计算该task的等待时间
     • 将这个task的等待时间放入list中
     • 根据这个task的纸张数目，计算完成这个task需要的时间
   • 一秒过去了～～～
   • 如果这个task完成了，或者说需要的时间减少为0，那么printer也不在busy了
3. 根据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_rate

import 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