程序设计导论：Python语言实践

4.3.5　FIFO队列

一个FIFO队列（或简队列）是一个基于先进先出（FIFO）策略的集合。

按到达先后顺序执行任务的策略是日常生活中经常遇见的现象，从剧院中的排队人群，到在收费亭排队等候的汽车，到计算机中等候应用程序处理的任务。

任何服务政策的一个基本原则是公正。关于公正，大多数人首先想到的观念是等候最久的人应该优先得到服务。这正是FIFO原则，所以队列在许多应用程序中占据十分重要的地位。队列是许多日常现象的自然模型，在计算机出现之前其属性已经被详细研究。一个典型的FIFO队列如图4-3-11所示。

图4-3-11　一个典型的FIFO队列

按惯例，我们从描述队列的API开始。同样依据传统，队列的插入操作命名为入队（enqueue），队列的移除操作命名为出队（dequeue）。队列数据类型的API如表4-3-4所示。根据来自栈的知识，我们可以使用Python列表（可变数组）或链表来开发队列的实现，其操作时间为常量，队列所占据的内存大小随着队列中元素个数的增加或减少而变化。和栈一样，每种实现都代表了一种经典的程序设计练习。在进一步阅读之前，读者可以尝试思考如何在一种实现中达到这些目标。

表4-3-4　队列数据类型的API

注：队列的空间使用必须与队列中项目的个数呈线性关系。 ...