队列

来自计算思维百科
跳转至: 导航搜索

队列也是一种运算受限的线性表,在这种插入限定在表的某一端进行,删除限定在表的另一端进行。允许插入的一端为队尾,允许删除的一端为队头。设Q= a1,a2,…,an (n≥0),那么a1为队头元素,an为队尾元素。队列中的元素是按照a1,a2,…,an的顺序进入的,退出队列只能按照进队的次序依次退出,如图1(a)所示,因此通常称队列为先进先出(First In First Out,FIFO)的线性表。在程序设计中,一般采用循环队列,以便重复使用存储空间,如图1(b)所示。

RTENOTITLERTENOTITLE

图1 队列

队列在程序设计中也经常出现。一个最典型的例子就是操作系统中的作业排队。在允许多道程序允许的计算机系统中,同时有几个作业运行。如果运行的结果都需要通过通道输出,那就要按请求输出的先后次序排队。队列的逻辑结构也是线性表。

应用范围

队列作为一种基本抽象数据类型,不仅广泛用于程序设计中的作业排队,还大量应用于日常生活中各种各样的排队问题。

汽车加油站

随着城市里汽车数量的急速增长,汽车加油站也渐渐多了起来。通常汽车加油站的结构基本上是:入口和出口为单行道,加油车道可能有若干条,每辆车加油都要经过三段路程,第一段是在入口处排队等候进入加油车道;第二段是在加油车道排队等候加油;第三段是在进入出口排队等候离开。 实际上,这三段都是队列结构,每个队列中,汽车按先后顺序排好,排在前面的汽车可以优先离开队列进行下一步操作,不容许插队,若用算法模拟这个过程,我们可以用队列这种结构来表示不同车道。

银行业务模拟

假设某银行有4个窗口对外接待客户,从早晨银行开门起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户,因此在客户人数众多时需在每个窗口前顺次排队,对于刚进入银行的客户,如果某个窗口的业务员正空闲,则可上前办理业务;反之,若4个窗口均有客户所占,他便会排在人数最少的队伍后面。 在这个案例中,我们可以把每个窗口看成一个队列,排在前面的客户可以先进行业务办理,即先进先出。

可以体现的计算思维

队列是一种抽象数据类型,是计算机组织数据的一种方式,可以方便地进行插入和删除,体现了计算思维的抽象特点。