《数据结构教程》-第四章

4.1队列的定义和基本运算4.1.1队列(Queue)的定义1.队列的定义设有n个元素的队列Q=,则称为队首元素，为队尾元素。队列中的元素按的次序进队，按次序出队，即队列的操作是按照“先进先出”的原则进行的，如图4-1所示。把进行插入的一端称作队尾(rear)，进行删除的一端称作队首(front)。向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素;从队列中删除元素称为出队或离队，元素出队后，其后继元素就成为队首元素。如图4-1所示。下一页返回4.1队列的定义和基本运算2.队列的特性(1)队列的主要特性是“先进先出”。(2)队列是限制在两端进行插人和删除操作的线性表。能够插人元素的一端称为队尾(Rear)，允许删除元素的一端称为队首(Front)。3.队列的实例(1)如车站排队买票或自动取款机排队取款。(2)在计算机处理文件打印时，为了解决高速的CPU与低速的打印机之间的矛盾，对于多个请求打印文件，操作系统把它们当作可以被延迟的任务，提出打印任务的先后顺序，就是它们实际打印的先后顺序。即按照“先进先出”的原则形成打印队列。下一页返回上一页4.1队列的定义和基本运算4.1.2队列的基木运算(1)入队操作:InQueue(q,x)初始条件:队q存在且未满。操作结果:输人一个元素x到队尾，长度加1。(2)出队操作:OutQueue(q,x)初始条件:队q存在，且非空。操作结果:删除队首元素，长度减1。(3)读队头元素:ReadFront(q,x)初始条件:队q存在且非空。操作结果:读队头元素，存人变量x，队列不变。下一页返回上一页4.1队列的定义和基本运算(4)显示队列中元素ShowQueue(q)初始条件:队列q存在，且非空。操作结果:显示队列中所有元素。(5)判队空操作:QEmpty(q)初始条件:队q存在。操作结果:若队空则返回为0，否则返回为1。(6)判队满操作:QFull(q)初始条件:队q存在。操作结果:若队满则返回为0，否则返回为1。(7)求队列长度Qlen(q)初始条件:队列q存在。操作结果:返回队列的长度。返回上一页4.2队列的存储实现及运算实现4.2.1顺序队列1.顺序队列顺序队列是用内存中一组连续的存储单元顺序存放队列中各元素。所以可以用一维数组Q[MAXLEN]作为队列的顺序存储空间，其中MAXLEN为队列的容量，队列元素从Q[0]单元开始存放，直到Q[MAXLEN-1]单元。因为队头和队尾都是活动的，因此，除了队列的数据以外，一般还设有队首(front)和队尾(rear)两个指针。顺序队可以用G++语言定义:下一页返回4.2队列的存储实现及运算实现下一页返回上一页4.2队列的存储实现及运算实现设:队头指针:p->front指向队头元素前面一个位置队尾指针:p->rear指向队尾元素。(1)判队空:当p->front=p->rear=-1时表示队空。(2)入队:在无溢出的情况下，队尾指针加1，新元素即可入队。(3)出队:在队列非空的情况下允许出队，出队时队头指针加1，队头元素即可输出。下一页返回上一页4.2队列的存储实现及运算实现(4)队列的长度:m=(p->rear)-(p->front);(5)判队满:m=MAXLEN;判队空:m=0。如图4-2所示，随着入队、出队操作的进行，整个队列会整体向后移动，队尾指针虽然已经移到了最后，而队列却末真满的“假溢出”现象，使得队列的空间没有得到有效的利用。2.循环队列为了解决上述队列的“假溢出”现象，要做移动操作，当移动数据较多时会影响队列的操作速度。一个更有效的方法是将队列的数据区Q[0..MAXLEN-1]看成是首尾相连的环，即将表示队首的元素Q[0]与表示队尾的元素Q[MAXLEN-1]连接起来，形成一个环形表，这就成了循环队列，如图4-3所示。下一页返回上一页4.2队列的存储实现及运算实现图4-4是循环队列操作示意图。因为是头尾相接的循环结构，所以将入队时的队尾指针加1操作修改为:p->rear=(p->rear+1)%MAXLEN;将出队时的队头指针加1操作修改为:p->front=(p->front+1)%MAXLEN;判断队空、队满有以下两种常用的方法。(1)规定:当front==rear时，表示循环队列为空;当front==(rear+1)%MAXLEN时，表示循环队列为满。(2)在定义结构体时，附设一个存储循环队列中元素个数的变量n，当n==0时表示队空;当n==MAXLEN时为队满。下一页返回上一页4.2队列的存储实现及运算实现循环队列的结构体类型定义如下:3.循环队列的基本运算(1)置空队下一页返回上一页4.2队列的存储实现及运算实现(2)入队下一页返回上一页4.2队列的存储实现及运算实现(3)出队下一页返回上一页4.2队列的存储实现及运算实现(4)判队空4.2.2链队列1.链队列的结构队列的链式存储结构称为链队列(或链队)，实际上它是一个带有头指针(front和尾指针(rear)的单链表。为了处理方便，也可以给链队列附加一个头结点。链队列为空的条件是front=rear，即队列的头指针和尾指针均指向表头结点，如图4-5所示。下一页返回上一页4.2队列的存储实现及运算实现图4-5所示队列中头指针front和尾指针rear是两个独立的指针变量，从结构性上考虑，有时也将两个指针封装在一个结构中。2.链队的描述下一页返回上一页4.2队列的存储实现及运算实现3.头指针和尾指针封装在一个结构中的链队列如图4-6所示为头指针和尾指针封装在一个结构中的链队列。4.链队的基本运算:(1)入队(进队)下一页返回上一页4.2队列的存储实现及运算实现(2)出队下一页返回上一页4.2队列的存储实现及运算实现(3)读队头元素下一页返回上一页4.2队列的存储实现及运算实现(4)显示队列中元素返回上一页4.3队列应用举例队列是一种应用广泛的数据结构，凡具有“先进先出”需要排队处理的问题，都可以使用队列来解决。1.队列在输入、输出管理中的应用在计算机进行数据输入、输出处理时，由于外部设备的速度远远低于CPU数据处理的速度，此时可以设定一个“队列缓冲区”进行缓冲。当计算机要输出数据时，将计算机的数据按块(例如每块5128)逐个添加到“队列缓冲区”的尾端，而外部设备则按照其输出速度从队首逐个取出数据块输出。这样，虽然输出数据速度较慢，但却能保证与计算机输出的数据有完全相同的次序，而不致发生输出次序混乱或数据丢失。下一页返回4.3队列应用举例2.对CPU的分配管理一般的计算机系统只有一个CPU，如果在系统中有多个进程都满足运行条件，就可以用一个就绪队列来进行管理。当某个进程需要运行时，它的进程名就被插人到就绪队列的尾端。如果此队列是空的，CPU会立即执行该进程;如果此队列非空，则该进程需要排在队列的尾端进行等待。CPU总是首先执行排在队首的进程，一个进程分配的一段时间执行完了，又将它插人到队尾等待，CPU转而为下一个出现在队首的进程服务。如此，按“先进先出”的原则一直进行下去，直到执行完的进程从队列中逐个删除掉。3.优先队列(PriorityQueue)在实际应用中，有时往往需要根据任务的优先级别来决定先做那些最重要的事情，此时必须对这种“先进先出”的规则进行适当的修改。下一页返回上一页4.3队列应用举例假设每个元素都有一个相当于权的数据项，那么就可以根据权值的大小来决定元素出队的顺序。也就是说，在队列中哪一个优先级最高，哪一个就优先出队。这种按优先级高低来决定出队顺序的队列，称为优先队列。优先队列的一个典型的应用就是批处理操作系统中的作业处理。每个作业都有一个优先级，系统在处理文件的时候，并不是根据一般队列的“先进先出”原则，而是根据文件优先级的高低来选择处理对象的。在优先队列中的每一个元素都有一个被称为权的数据项，权的大小决定了元素的优先级。实现优先队列有以下两种方法。(1)按权的大小进行插入，使整个队列始终保持按优先级次序排列的状态，而删除操作则和普通队列一样，只删除队首元素。下一页返回上一页4.3队列应用举例(2)插入操作和普通队列一样，只在队尾进行插入，而删除操作则是根据元素的优先级来进行的，即只能删除优先级最高的元素。限于篇幅，有关优先队列具体算法的实现，在此不作介绍。4.双队列(Double-endsQueue)操作系统的工作调度所采用的则是双队列，这种队列的两端都可以存取数据，其结构如图4-7所示。如果将图4-7所示队列切成左、右两部分，则成了两个独立的栈，所以双队列就是将两个栈的栈底结合起来而构成的。与队列相同的是，双队列也需要两个指针分别指向结构的两端。CPU的调度在多入使用的计算机系统中是一种重要的概念，其调度的方法也可分为:输入限制性双队列和输出限制性双队列等形式。下一页返回上一页4.3队列应用举例输入限制性双队列由双向队列数据输入、从队头输出数据、从队尾输出数据三部分组成，可以由用户按照提示自由选择“从队头输出”或“从队尾输出”，以模拟各种可能的输出结果。(1)向队列数据输人InQueue()下一页返回上一页4.3队列应用举例(2)队头输出数据OutQueue_front()下一页返回上一页4.3队列应用举例(3)从队尾输出数据OutQueue_rear()下一页返回上一页4.3队列应用举例5.采用队列求解迷宫问题使用一个队列Qu记录走过的方块，该队列的结构如下:这里使用的队列Qu不是环形队列(因为要利用出队的元素找路径)，因此在出队时不会将出队元素真正从队列中删除，因为要利用它输出路径。搜索从(1,1)到(M-2,N-2)路径的步骤如下。(1)首先将(1,1)入队。下一页返回上一页4.3队列应用举例(2)在队列Qu不为空时循环:出队一次(由于不是环形队列，该出队元素仍在队列中)，称该出队的方块为当前方块，front为该方块在Qu中的下标。①如果当前方块是出口，则输出路径并结束。②否则，按顺时针方向找出当前方块的四个方位中可走的相邻方块(对应的mg数组值为0)，将这些可走的相邻方块均插人到队列Qu中，其pre设置为本搜索路径中上一方块在Qu中的下标值，也就是当前方块的front值，并将相邻方块对应的mg数组值置为-1，以避免重复搜索。(3)若队列为空仍未找到出口，即不存在路径。实际上，本算法的思想是从(1,1)开始，利用队列的特点，一层一层向外扩展可走的点，直到找到出口为止，这个方