扫码获取更多资源

●队列

队列的特点在于其基本操作的特殊性，即它必须按照“先进先出”规则进行操作。与线 性表相比，它的插入和删除操作受到更多的约束和限定。

队列的类型定义

在日常生活中，经常会遇到为了维护社会正常秩序而需要排队的情景。在计算机程序 设计中也经常出现类似问题。数据结构的“队列”与生活中的“排队”极为相似，也是按照“先 到先办”的原则行事，并且严格限定：既不允许“加塞儿”，也不允许“中途离队”。

队列的定义

队列(Queue)是只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线 性表。允许插入的一端称为队尾(Rear),队尾将随着队列中元素的增加而浮动，通过队尾指 针指明队尾的位置；允许删除的一端称为队头(Front),队头将随着队列中元素的减少而浮 动，通过队头指针指明队头的位置。不含任何元素的队列称为空队列(Empty Queue) o

如图3-6所示，队列中有5个元素，插入元素(也称入队)顺序为a】,a2 .a3 >a4 .a5,删除元 素(也称出队)顺序依然是a1>a2>a3.a4.a5,即最先入队者最先出队，所以队列中的元素除了 具有线性关系外，还具有先进先出(First In First Out, FIFO)的特性。队列也可以简称为 FIFO 表。

在现实生活中有许多问题可以用队列来描述。例如，顾客服务部门的工作往往是按队 列方式进行的，这类系统称为排队系统。在程序设计中，也经常使用队列记录需要按先进先 出方式处理的数据，如键盘缓冲区、操作系统中的作业调度等。

例如，CPU资源的竞争问题。在具有多个终端的计算机系统中，有多个用户需要使用 CPU各自运行自己的程序，它们分别通过各自终端向操作系统提岀使用CPU的请求，操作 系统按照每个请求在时间上的先后顺序，将其排成一个队列，每次把CPU分配给队头用户 使用，当相应的程序运行结束后令其出队，再把CPU分配给新的队头用户，直到所有用户 任务处理完毕。

又如，主机与外部设备之间速度不匹配的问题。以主机和打印机为例来说明，主机输出 数据给打印机打印，主机输出数据速度比打印机打印速度要快得多。直接把输岀数据送给 打印机打印，由于速度不匹配，显然是不行的，因此解决的方法是设置一个打印数据缓冲区， 主机把要打印输出的数据依次写入这个缓冲区中，写满后就暂停输出，继而去做其他的事 情，打印机就从缓冲区中按照先进先岀的原则依次取出数据并打印，打印完后再向主机发出 请求，主机接到请求后再向缓冲区写入打印数据，这样利用队列既保证了打印数据的正确， 又使主机提高了效率。

队列的抽象数据类型

联系我们：