下载掌阅APP，畅读海量书库
立即打开
队列（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 队列的基本运算
双向队列（Double Ended Queues，DEQue）是一种有序线性表，加入与删除可在队列的任意一端进行，如图2-43所示。
图2-43 双向队列的示意图
具体来说，双向队列就是允许队列两端都具备删除或加入功能，而且无论是左端还是右端的队列，队首与队尾指针都是朝队列中央移动的。通常，双向队列的应用可以分为两种：一种是数据只能从一端加入，但可以从两端取出；另一种是可从两端加入，但从一端取出。
优先队列（Priority Queue）是一种不必遵守队列先进先出特性的有序线性表，其中的每一个元素都赋予一个优先级（Priority），加入元素时可任意加入，但有最高优先级者（Highest Priority Out First，HPOF）最先输出。
图2-44 急诊病人的安排就是优先队列的应用
像一般医院中的急诊室，当然以最严重的病患（如得SARS的病人）优先诊治，跟进入医院挂号的顺序无关，如图2-44所示。或者在计算机中CPU的作业调度中，优先级调度（Priority Scheduling，PS）就是一种按照进程优先级“调度算法”（Scheduling Algorithm）进行的调度，这种调度会用到优先队列，优先级高的用户比一般用户拥有较高的优先权利。
假设有4个进程：P1、P2、P3和P4，其在很短的时间内先后到达等待队列，每个进程所需的运行时间如表2-3所示。
表2-3 每个进程所需的运行时间
在此设置进程P1、P2、P3、P4的优先次序值分别为2、8、6、4（此处假设数值越小其优先级越低，数值越大其优先级越高）。按优先级调度进程绘出的甘特图如图2-45所示。
图2-45 优先级调度进程的示意图
在此特别提醒大家，当各个元素以输入的先后次序为优先级时，就是一般的队列，假如以输入先后次序的倒序作为优先级，此优先队列其实就是一个堆栈。