队列与双向队列

队列类

 1 # python
 2 # -*- coding: utf-8 -*-
 3 """
 4 __title__ = ''
 5 __author__ = 'wlc'
 6 __mtime__ = '2017/10/13'
 7 """
 8 class pythonQueue:
 9     def __init__(self):
10         self.items = []
11     #isEmpty
12     def isEmpty(self):
13         return self.items == []
14     #enqueue
15     def enqueue(self, element):
16         self.items.insert(0, element)
17     #dequeue
18     def dequeue(self):
19         return self.items.pop()
20     #queue size
21     def size(self):
22         return len(self.items)

双向队列类

 1 # python
 2 # -*- coding: utf-8 -*-
 3 """
 4 __title__ = ''
 5 __author__ = 'wlc'
 6 __mtime__ = '2017/10/13'
 7 """
 8 class pythonDeque:
 9     def __init__(self):
10         self.items = []
11     #isEmpty
12     def isEmpty(self):
13         return self.items == []
14     #size
15     def size(self):
16         return len(self.items)
17     #addFront
18     def addFront(self, item):
19         self.items.append(item)
20     #addRear
21     def addRear(self, item):
22         self.items.insert(0, item)
23     #removeFront
24     def removeFront(self):
25         return self.items.pop()
26     #removeRear
27     def removeRear(self):
28         return self.items.pop(0)

使用队列模拟打印机类

 1 # python
 2 # -*- coding: utf-8 -*-
 3 """
 4 __title__ = ''
 5 __author__ = 'wlc'
 6 __mtime__ = '2017/10/13'
 7 """
 8 class pythonPrinter:
 9     def __init__(self, ppm):
10         self.pageRate = ppm
11         self.currentTask = None
12         self.timeRemaining = 0
13     #计时器
14     def tick(self):
15         if self.currentTask != None:
16             self.timeRemaining = self.timeRemaining - 1
17             if self.timeRemaining <= 0:
18                 self.currentTask = None
19     #是否忙
20     def busy(self):
21         if self.currentTask == None:
22             return False
23         else:
24             return True
25 
26     #开始下一个任务
27     def startNextTask(self, task):
28         """
29         :param task: 此处task是一个pythonPrinterTask对象
30         """
31         self.currentTask = task
32         self.timeRemaining = task.getPage() * 60 / self.pageRate

打印机任务类

 1 # python
 2 # -*- coding: utf-8 -*-
 3 """
 4 __title__ = ''
 5 __author__ = 'wlc'
 6 __mtime__ = '2017/10/13'
 7 """
 8 import random
 9 class pythonPrinterTask:
10     def __init__(self, timeStamp):
11         #当前的时间戳
12         self.timeStamp = timeStamp
13         #假设打印页数在1-20之间
14         self.page = random.randrange(1,21)
15     #得到时间戳
16     def getStamp(self):
17         return self.timeStamp
18     #得到打印页数
19     def getPage(self):
20         return self.page
21     #计算等待时间
22     def waitTime(self, currentTime):
23         return currentTime - self.timeStamp

相关算法实现

  1 # python3
  2 # -*- coding: utf-8 -*-
  3 """
  4 __title__ = ''
  5 __author__ = 'wlc'
  6 __mtime__ = '2017/10/13'
  7 """
  8 from dataStructure.dS import pythonQueue
  9 from dataStructure.dS import  pythonPrinter
 10 from dataStructure.dS import  pythonPrinterTask
 11 from dataStructure.dS import  pythonDeque
 12 import random
 13 
 14 def hotPotato(nameList, num):
 15     """
 16     :program:烫手山芋问题 约瑟夫环
 17     :param nameList:
 18     :param num:
 19     :return: 最后一个人
 20     """
 21     #实例化一个队列
 22     queue = pythonQueue.pythonQueue()
 23     #将名字依次放入队列
 24     for list in nameList:
 25         queue.enqueue(list)
 26     #直到队列size为1 之前依次执行队列首出队列并且进入队尾
 27     while queue.size() > 1:
 28         for i in range(num):
 29             queue.enqueue(queue.dequeue())
 30         queue.dequeue()
 31     return queue.dequeue()
 32 ##################################################################################
 33 
 34 def printerTask(numSeconds, pageRate):
 35     """
 36     :program:模拟打印机排队过程
 37     :param numSeconds: 模拟时间长度单位秒
 38     :param pageRate: 打印机每分钟处理页数
 39     :return: 队列的平均等待时间
 40     """
 41     #实例化打印对象
 42     printer = pythonPrinter.pythonPrinter(pageRate)
 43     #list 用于保存task 等待时间
 44     waitList = []
 45     #实例化一个队列用于保存task队列
 46     tasksQueue = pythonQueue.pythonQueue()
 47 
 48     #模拟给定时间段的秒数
 49     for currentSecond in range(numSeconds):
 50         #随机生成一个任务3600秒内 假设一共有20个任务平均下来大约180秒产生一个新的任务
 51         if newTask():
 52             #如果是一个新的任务则将其实例化并且添加到队列中
 53             taskNew = pythonPrinterTask.pythonPrinterTask(currentSecond)
 54             tasksQueue.enqueue(taskNew)
 55         #如果打印机不忙并且打印队列不是空的 就将队列的队首给打印机 并且将该队首的等待时间计算出来放到waitList列表中
 56         if (not printer.busy()) and (not tasksQueue.isEmpty()):
 57             #取出队首
 58             taskQueue = tasksQueue.dequeue()
 59             #将等待时间放到list里边保存
 60             waitList.append(taskQueue.waitTime(currentSecond))
 61             #打印机开始下一个任务
 62             printer.startNextTask(taskQueue)
 63         #打印机开始一张一张的减去
 64         printer.tick()
 65     average = sum(waitList) / len(waitList)
 66     print("平均等待时间%6.2f %3d 任务正在等待" %(average, int(tasksQueue.size())))
 67 
 68 def newTask():
 69     """
 70     #program:随机产生1-180的数字 用于模拟在180秒内平均会有一次打印任务
 71     :return: True False
 72     """
 73     var = random.randrange(1, 181)
 74     if var == 180:
 75         return True
 76     else:
 77         return False
 78 
 79 ##################################################################################
 80 def palChecker(str):
 81     """
 82     program:回文检测 boob
 83     :param str: 输入字符串
 84     :return: true false
 85     """
 86     #实例化一个双向队列
 87     palDeque = pythonDeque.pythonDeque()
 88     #str 的每一个字符从尾部（index为0的位置）依次保存到双向队列中
 89     for str0 in str:
 90         palDeque.addRear(str0)
 91     #定义一个flag 若为false则返回
 92     flag = True
 93     #直到双向队列的大小>1 等于一意味着字符数为奇数 等于零 意味为偶数
 94     while palDeque.size() > 1 and flag:
 95         front = palDeque.removeFront()
 96         rear = palDeque.removeRear()
 97         if front != rear:
 98             flag = False
 99     return  flag
100 
101 
102 
103 if __name__ == '__main__':
104     queue = pythonQueue.pythonQueue()
105     print(queue.isEmpty())
106     queue.enqueue('dog')
107     print(queue.size())
108     print(queue.items)
109     pop = queue.dequeue()
110     print(pop)
111     print(queue.isEmpty())
112     ###################################################################
113     var = input("请输入排队列表以空格分隔：")
114     var = [str for str in var.split()]
115     var1 = input("请输入规则num：")
116     result = hotPotato(var, int(var1))
117     print("最后一个人是：%s" %result)
118     ###################################################################
119     var = int(input("请输入时间（单位秒）："))
120     var1 = int(input("打印机处理速率（页/分钟）："))
121     printerTask(var, var1)
122     for i in range(10):
123         printerTask(var, var1)
124     ###################################################################
125     var = input("请输入要检测回文的字符串：")
126     print("检测结果："+str(palChecker(var)))