零基础学数据结构第5章队列_计算机软件及应用_IT计.ppt

第5章 队列 与栈一样，队列也是一种操作受限的线性表。队列在操作系统和事务管理等软件设计中应用广泛，如键盘输入缓冲区问题就是利用队列的思想实现的。 本章重点和难点： 1、队列的顺序表示与实现 2、队列的链式表示与实现 5.1 队列的定义与抽象数据类型 队列只允许在表的一端进行插入操作，在表的另一端进行删除操作。 5.1.1 什么是队列 队列（queue）是一种先进先出（first in first out，缩写为FIFO）的线性表，它只允许在表的一端进行插入，另一端删除元素。这与我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端称为队头（front），允许删除的一端称为队尾（rear）。 5.1 队列的定义与抽象数据类型 假设队列为q=（a1，a2，…，ai，…，an），那么a1为队头元素，an为队尾元素。进入队列时，是按照a1，a2，…，an的顺序进入的，退出队列时也是按照这个顺序退出的。也就是说，当先进入队列的元素都退出之后，后进入队列的元素才能退出。即只有当a1，a2，…，an-1都退出队列以后，an才能退出队列。 5.1 队列的定义与抽象数据类型 5.1.2 队列的抽象数据类型 1．数据对象集合 队列的数据对象集合为{a1，a2，…，an}，每个元素都具有相同的数据类型DataType。 队列中的数据元素之间也是一对一的关系。除了第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。 5.1 队列的定义与抽象数据类型 2．基本操作集合 （1）InitQueue(Q)：初始化操作，建立一个空队列Q。 （2）QueueEmpty(Q)：若Q为空队列，返回1，否则返回0。 （3）EnQueue(Q,e)：插入元素e到队列Q的队尾。 （4）DeQueue(Q,e)：删除Q的队首元素，并用e返回其值。 （5）Gethead(Q,e)：用e返回Q的队首元素。 （6）ClearQueue(Q)：将队列Q清空。 5.2 队列的顺序存储及实现 5.2.1 顺序队列的表示 顺序队列通常采用一维数组依次存放从队头到队尾的元素。同时，使用两个指针分别指示数组中存放的第一个元素和最后一个元素的位置。其中，指向第一个元素的指针被称为队头指针front，指向最后一个元素的指针被称为队尾指针rear。 元素a、b、c、d、e、f、g依次进入队列后的状态如图5.2所示。元素a存放在数组下标为0的存储单元中，g存放在下标为6的存储单元中，队头指针front指向第一个元素a，队尾指针rear指向最后一个元素g的下一位置。 5.2 队列的顺序存储及实现 在使用队列前，先初始化队列，此时，队列为空，队头指针front和队尾指针rear都指向队列的第一个位置，即front=rear=0，如图5.3所示。 每一个元素进入队列，队尾指针rear就会增1，若元素a、b、c依次进入空队列，front指向第一个元素，rear指向下标为3的存储单元，如图5.4所示。 5.2 队列的顺序存储及实现 当一个元素出队列时，队头指针front增1，队头元素即a出队后，front向后移动一个位置，指向下一个位置，rear不变，如图5.5所示。 5.2 队列的顺序存储及实现 5.2.2 顺序队列的“假溢出” 在对顺序队列进行插入和删除操作的过程中，可能会出现“假溢出”现象。经过多次插入和删除操作后，实际上队列还有存储空间，但是又无法向队列中插入元素，我们将这种溢出称为“假溢出”。 例如，在图5.2所示的队列中插入3个元素h、i、j，然后删除2个元素a，b之后，就会出现如图5.6所示的情况。当插入元素j后，队尾指针rear将越出数组的下界而造成“假溢出”。 5.2 队列的顺序存储及实现 5.2.3 顺序循环队列的表示 1．顺序循环队列 为了充分利用存储空间，消除这种“假溢出”现象，当队尾指针rear和队头指针front到达存储空间的最大值（假定队列的存储空间为QueueSize）的时候，让队尾指针和队头指针转化为0，这样就可以将元素插入到队列还没有利用的存储单元中。例如，在图5.6中，插入元素j之后，rear将变为0，可以继续将元素插入到下标为0的存储单元中。这样就把顺序队列使用的存储空间构造成一个逻辑上首尾相连的循环队列。 5.2 队列的顺序存储及实现