3.1.4　队列的基本知识

1. 队的定义

队是一种操作受限的线性表，它限定只能在表的一端进行插入，这一端称作队尾(rear)；在另一端进行删除，这一端称作队头(front)。记作：

2. 队的操作特征

队的操作特征是“先进先出”(First In First Out)。故队又称作先进先出线性表，简称FIFO表。

3. 队的存储结构

队作为一种特殊的线性表，同样可以采用顺序存储和链式存储两种存储结构。利用顺序存储可以构成顺序队列和循环队列，利用链式存储可以构成链队列。

4. 队的5种基本操作

(1) 置队空SetNull(Q) 将队Q置成空队列。

(2) 判队空Empty(Q) 若Q为空队列，函数值为“真”；否则为“假”。

(3) 取队头元素GetFront(Q) 读取队列Q的队头元素作为函数值。

(4) 入队EnQueue(Q,x) 向队列Q的尾部插入元素x。

(5) 出队Dequeue(Q) 删除队列Q的队头元素。

5. 队列的典型应用

凡是遵循“先到先处理”原则的操作，都可以用队列来管理和模拟。例如：

(1) 银行接待储户的业务活动。

(2) 计算机中CPU响应各种请求的排队管理。

(3) 树和图(非线性结构)的某种遍历算法的实现。

(4) 计算机的打印机输出缓冲区管理。