程序员学数据结构

第5章　队列：先入先出的数据集

队列（queue）是一种抽象化的数据结构，它将其中的对象组织成为线性的数据集。这些对象在被插入进队列，或从队列中删除时，会遵循先入先出（FIFO, First-In First-Out）原则。队列中最显著的两个操作分别为入队（enqueue）和出队（dequeue）。入队操作将对象增添至队尾，出队操作将对象从队首删除。图5-1展示了队列的数据结构和上述两种基本操作。队列中其他常见操作还包括查看、判断队列是否为空、判断队列是否已满，所有这些操作将在本章后续内容中进行探讨。

图5-1

队列与栈非常相似，它们共享了一些相同的功能。甚至于它们的两种基本操作都非常相似，区别只在于其实现的原则正好相反。如同栈一样，队列也有数组队列和链表队列之分，大多数情况中链表队列的效率会更高。队列与栈的区别在于，栈可以是未排序或已排序栈，而队列根本就不是为排序而设计的，如果每当队列中增加对象就对其进行排序，则操作代价将会变为令人吃惊的O(n.log(n))。队列的另一种形式为基于堆这种数据结构的优先级队列（priority queue）。优先级队列支持排序，但其操作代价仍然较高，除一些特殊应用外并不会广泛使用。

总之，队列适用于需要根据先到先服务(first-come first-served)原则来确定操作优先级的任何应用。如果觉得难以具象化队列的结构，最简单的办法就是想象自己在排队时的样子。上小学时，我们会排队等待喝水；在超市里，我们会排队结账；在饭店，我们会排队等号；在许多政府办公地点，我们会排队等候办事。事实上，我们从出生起就开始在排队了……除非你有双胞胎兄弟，意味着你的排队生涯还要比我们早一点点。 ...