下载掌阅APP，畅读海量书库
立即打开
队列（Queue）是一种特殊的线性表。由于其先进先出的运算特性，被广泛用于作业排队。
队列也是一种线性表，它与普通线性表的区别在于其运算仅限定在表首和表尾，是两端开口的线性表，队列只在表的一端进行插入操作，在表的另一端进行删除操作。允许进行插入操作的一端称为“队尾”，而允许进行删除操作的一端称为“队头”。队列的两端均可浮动。
队列的形式化定义为
Q ={ D , R }
其中， D ={ a i | a i ∈ ElemSet , i =1, 2, …, n, n ≥ 0}； R ={＜ a i -1 , a i ＞| a i -1 , a i ∈D, i =2,3,…, n }。
对于队列 Q =（ a 1 , a 2 , a 3 ,…, a n ）， a 1 是队头元素， a n 是队尾元素，队列中元素以 a 1 , a 2 , a 3 ,…, a n 的次序入队，也以同样的次序出队，其工作方式是先进先出，与栈的工作方式刚好相反，如图3-17所示。
图3-17 阶列结构
顺序存储或链式存储都可以作为队列的存储结构，但队列的容量一般是有限的，所以通常采用顺序存储作为栈的存储结构。
队列的两端均可浮动，因此需要设立两个指针，分别指向队头（Front）和队尾（Rear）。规定指针Front总是指向实际队头的前一位置，而指针Rear指向队尾元素。
显然，当Rear=0或Front=Rear时，队列为空；当Rear等于上界时，队列满。
队列的主要运算是入队和出队。入队时，队尾指针加1；出队时，队头指针加1。
操作系统中的作业排队是最典型的应用，当系统中有多道程序运行时，可能同时有几个作业的运行结果需要通过通道输出，这就要按申请的先后次序排队。申请输出的作业从队尾进行队列，当通道传输完一个作业，要接受一个新作业时，队头的作业先从队列中退出输出操作。