11、数据结构与算法Python：队列抽象数据类型及Python实现

队列Queue：什么是队列？

队列是一种有次序的数据集合， 其特征是

新数据项的添加总发生在一端（通常称为“尾rear”端）而现存数据项的移除总发生在另一端（通常称为“首front”端）

当数据项加入队列， 首先出现在队尾， 随着队首数据项的移除， 它逐渐接近队首。

### 新加入的数据项必须在数据集末尾等待，而等待时间最长的数据项则是队首 ### 这种次序安排的原则称为（FIFO:First-infirst-out） 先进先出 或“先到先服务first-come first-served”

队列的例子出现在我们日常生活的方方面面：排队

队列仅有一个入口和一个出口

不允许数据项直接插入队中，也不允许从中间移除数据项

计算机科学中队列的例子：打印队列

一台打印机面向多个用户/程序提供服务

打印速度比打印请求提交的速度要慢得多有任务正在打印时，后来的打印请求就要排成队列，以FIFO的形式等待被处理。

操作系统核心采用多个队列来对系统中同时运行的进程进行调度

进程数远多于CPU核心数
有些进程还要等待不同类型I/O事件

调度原则综合了“先到先服务”及“资源充分利用”两个出发点

键盘敲击并不马上显示在屏幕上

需要有个队列性质的缓冲区，将尚未显示的敲击字符暂存其中，队列的先进先出性质则保证了字符的输入和显示次序一致性。

抽象数据类型Queue

抽象数据类型Queue是一个有次序的数据集合

数据项仅添加到“尾rear”端而且仅从“首front”端移除 Queue具有FIFO的操作次序

抽象数据类型Queue由如下操作定义：

• Queue()：创建一个空队列对象，返回值为Queue对象；
• enqueue(item)：将数据项item添加到队尾，无返回值；
• dequeue()：从队首移除数据项，返回值为队首数据项，队列被修改；
• isEmpty()：测试是否空队列，返回值为布尔值
• size()：返回队列中数据项的个数。

Python实现ADT Queue

采 用 List 来 容 纳 Queue的数据项

• 将List首端作为队列尾端
• List的末端作为队列首端
• enqueue()复杂度为 O(n)
• dequeue()复杂度为 O(1)

首尾倒过来的实现， 复杂度也倒过来

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

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

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

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

版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: