《计算思维与算法入门》 —2.6 队列

2.6    队列

队列（Queue）和堆栈都是有序列表，也属于抽象数据类型，所有加入与删除的操作都发生在队列前后两端，即队首和队尾，并且符合“先进先出”（First In First Out，FIFO）的特性。队列的概念就好比乘火车时买票的队伍，先到的人当然可以优先买票，买完后就从队伍前端离去准备乘火车，而队伍的后端又陆续有新的乘客加入，如图2-41所示。

图2-41  买火车票的队伍就是队列原理的应用

队列在计算机领域应用得也相当广泛，例如计算机的模拟（Simulation）、CPU的作业调度（Job Scheduling）、外围设备联机并发处理系统（Spooling）的应用与图遍历的广度优先搜索法（Breadth-First Search，BFS）。堆栈只需一个top指针指向堆栈顶部，而队列则必须使用front和rear两个指针分别指向队列的前端和末尾，如图2-42所示。

图2-42  队列结构示意图

队列是一种抽象数据结构，有下列特性：

（1）具有先进先出的特性。

（2）拥有加入与删除两种基本操作，而且使用front与rear两个指针分别指向队列的前端与末尾。

队列的基本运算有表2-2所示的5种。

表2-2  队列的基本运算

2.6.1  双向队列

双向队列（Double Ended Queues，DEQue）是一种有序线性表，加入与删除可在队列的任意一端进行，如图2-43所示。

图2-43  双向队列的示意图

具体来说，双向队列就是允许队列两端都具备删除或加入功能，而且无论是左端还是右端的队列，队首与队尾指针都是朝队列中央移动的。通常，双向队列的应用可以分为两种：一种是数据只能从一端加入，但可以从两端取出；另一种是可从两端加入，但从一端取出。