- 一、队列（Queue）
- 1. 队列的定义
- 2. 队列的特性
- 3. 使用python实现队列
- 二、队列的应用：打印任务
- 1. 实例
- 2. 抽象建模
- 3. python代码实现
- 三、双端队列（Deque）
- 1. 双端队列的定义
- 2 .使用Python实现双端队列
- 四、双端队列的应用：“回文词”判定
- 1. “回文词”的概念
- 2. “ 回文词”的判定方法
- 3. python代码实现
队列是一种有次序的数据集合，其特征是新数据项的添加总发生在一端（通常称为“尾rear”端）而现存数据项的移除总发生在另一端（通常称为“首front”端）。
当数据项加入队列，首先出现在队尾进行等待，随着队首数据项的移除，它逐渐接近队首，最后被移除。
这种次序安排的原则称为**“先进先出FIFO”**（First-in
first-out）。
这就跟我们在收银台前排队等待结账是极为相似的。新来的顾客到队尾（尾端）排队，而最前面的顾客（首端）结完帐后直接走人。慢慢的，后面的顾客就会走到最前面。
2. 队列的特性- 首端的数据项“排队”等待的时间是现有数据项中最长的。
- 队列仅有一个入口和一个出口，不允许数据项直接插入队中，也不允许从中间移除数据项。
采用List来容纳Queue的数据项，将List首端作为队列
尾端List的末端作为队列首端。
class Queue:
"""队列类"""
def __init__(self):
"""初始化一个空队列"""
self.items = []
def is_empty(self):
"""判断队列是否为空"""
return self.items == []
def enqueue(self, item):
"""添加元素"""
self.items.append(item)
def dequeue(self):
"""返回首端元素并移除"""
return self.items.pop(0)
def size(self):
"""返回队列数据项的数量"""
return len(self.items)
- 操作复杂度：
- enqueue()复杂度为 O ( 1 ) O(1) O(1)；
- dequeue()复杂度为 O ( n ) O(n) O(n)。
一个实验室，在任意的一个小时内，大约有10名学生共享一台打印机，采取“先到先服务”的队列策略来执行打印任务：
-
这一小时中，每人会发起2次左右的打印，每次1～20页。
-
打印机的性能是：
以草稿模式打印的话，每分钟10页；以正常模式打印的话，打印质量好，但速度下降为每分钟5页。
问题：怎么设定打印机的模式，让大家都不会等太久的前提下尽量提高打印质量？
这是一个典型的决策支持问题，但无法通过规则直接计算。我们要用一段程序来模拟这种打印任务场景，然后对程序运行结果进行分析，以支持对打印机模式设定的决策。
2. 抽象建模-
对象及其属性：
- 打印任务：提交时间、打印页数；
- 打印任务队列：具有FIFO性质的打印任务队列；
- 打印机：打印速度、是否忙。
-
过程：
-
生成和提交打印任务：
确定任务生成概率：实例为每小时会有10个学生提交的20个作业，这样，概率是每180秒会有1个作业生成并提交，概率为每秒1/180。
确定打印页数：实例是1～20页，那么就是1～20页之间概率相同，在范围内随便选一个数，作为作业的页数。 -
实施打印：
当前的打印作业：正在打印的作业打印结束倒计时：新作业开始打印时开始倒计时，回0表示打印完毕，可以处理下一个作业。
-
-
模拟时间：
-
统一的时间框架：
以最小单位（秒）均匀流逝时间，设定结束时间。
-
同步所有过程：
在一个时间单位里，对生成打印任务和实施打印两个过程各处理一次。
-
import random
class Printer:
"""打印机类"""
def __init__(self, ppm):
# 打印速度
self.pagerate = ppm
# 打印任务
self.current_task = None
# 任务倒计时
self.time_remaining = 0
def tick(self):
"""打印1秒"""
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
# 计算打印时间，因为速度是按分钟算的，所以要乘以60
self.time_remaining = new_task.get_pages() * 60 / self.pagerate
class Task:
"""打印任务"""
def __init__(self, time):
# 生成时间戳
self.time_stamp = time
# 任务页数
self.pages = random.randint(1, 21)
def get_stamp(self):
return self.time_stamp
def get_pages(self):
return self.pages
def wait_time(self, current_time):
"""等待时间"""
# 等待时间为当前时间减去生成时间
return current_time - self.time_stamp
def new_print_task():
"""生成新的打印任务，概率为1/180"""
num = random.randint(1, 181)
if num == 180:
return True
else:
return False
def simulation(num_seconds, pages_per_minute):
"""
模拟打印
Args:
num_seconds：总共打印多长时间
pages_per_minute：打印速度
"""
# 实例化打印机
labprinter = Printer(pages_per_minute)
# 实例化等待队列
print_queue = Queue()
# 用来保存等待时间的列表，以便最后计算平均等待时间
waiting_times = []
# 开始模拟打印
for current_second in range(num_seconds):
# 尝试生成打印任务，如果成功，将任务添加到打印队列
if new_print_task():
task = Task(current_second)
print_queue.enqueue(task)
# 如果打印机不忙，且打印队列不是空的
if (not labprinter.busy()) and (not print_queue.is_empty()):
# 从任务队列取出任务
next_task = print_queue.dequeue()
# 记录任务等待时间
waiting_times.append(next_task.wait_time(current_second))
# 切换到新的打印任务
labprinter.start_next(next_task)
# 打印1秒
labprinter.tick()
# 计算平均等待时间
average_wait = sum(waiting_times) / len(waiting_times)
print(f"平均等待时间为{average_wait}，剩余{print_queue.size()}个任务")
多次设定尝试后，发现使用打印速度到10PPM、1小时的设定：总平均等待时间12秒，最长的平均等待35秒，最短的平均等待0秒，而且没有剩余任务。
三、双端队列（Deque） 1. 双端队列的定义双端队列Deque是一种有次序的数据集，跟队列相似，其两端可以称作“首”、“尾”端，但deque中数据项既可以从队首加入，也可以从队尾加入；数据项也可以从两端移除。
2 .使用Python实现双端队列采用List实现，List下标0作为deque的尾端；List下标-1作为deque的首端。
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)
- 操作复杂度：
- addFront/removeFront复杂度为 O ( 1 ) O(1) O(1)；
- addRear/removeRear复杂度为 O ( n ) O(n) O(n)。
“回文词”指正读和反读都一样的词，比如：radar、toot、“上海自来水来自海上”、“山东落花生花落东山”等。
2. “ 回文词”的判定方法用双端队列很容易解决“回文词”问题，先将需要判定的词从队尾加入deque。再从两端同时移除字符判定是否相同，直到deque中剩下0个或1个字符（因为奇数“回文词”最中间的字，并不会影响整个“回文词”）。
3. python代码实现def palchecker(word):
deque = Deque()
for ch in word:
deque.add_rear(ch)
while deque.size() > 1:
first = deque.remove_front()
last = deque.remove_rear()
if first != last:
return False
else:
return True
