3.4.1 队列的定义

队列（Queue）是一种先进先出（First In First Out，缩写为FIFO）的线性表，它只允许在表的一端插入元素，而在另一端删除元素。其中，允许插入的一端叫作队尾（rear），允许删除的一端称为队头（front）。

假设队列为q=（a₁，a₂，…，a_i，…，a_n），那么a₁就是队头元素，a_n则是队尾元素。进入队列时，是按照a₁，a₂，…，a_n的顺序依次进入的，退出队列时也是按照这个顺序退出的。即退出队列时，只有当前面的元素都退出之后，后面的元素才能退出。因此，只有当a₁，a₂，…，a_n-1都退出队列以后，a_n才能退出队列。队列的示意图如图3.21所示。

图3.21 队列的示意图

在日常生活中，人们买票排的队就是一个队列。新来买票的人到队尾排队，形成新的队尾，即入队，在队头的人买完票离开，即出队。操作系统中的多任务处理也是队列的应用问题。