零基础学数据结构-第5章-队列备课讲稿.ppt

《零基础学数据结构-第5章-队列备课讲稿.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、零基础学数据结构-第5章-队列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。队列中的数据元素之间也是一对一的关系。除了第一个元素

2、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顺序队列的表示顺序队列通常采

3、用一维数组依次存放从队头到队尾的元素。同时，使用两个指针分别指示数组中存放的第一个元素和最后一个元素的位置。其中，指向第一个元素的指针被称为队头指针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，如

4、图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所示的

5、队列中插入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的存储单元中。这样就把顺序队列使用的存储空

6、间构造成一个逻辑上首尾相连的循环队列。5.2队列的顺序存储及实现当队尾指针rear达到最大值QueueSize-1时，前提是队列中还有存储空间，若要插入元素，就要把队尾指针rear变为0；当队头指针front达到最大值QueueSize-1时，若要将队头元素出队，要让队头指针front变为0。这可通过取余操作实现队列的首尾相连。例如，假设QueueSize=10，当队尾指针rear=9时，若要将新元素入队，则先令rear=（rear+1）%10=0，然后将元素存入队列的第0号单元，通过取余操作实现了队列的逻辑上的首尾相连。5.2队列的顺序存储及实现2．顺序循环队列的队空和队满

7、判断但是，在顺序循环队列在队空和队满的情况下，队头指针front和队尾指针rear同时都会指向同一个位置，即front==rear，如图5.7所示。即队列为空时，有front=0，rear=0，因此front==rear。队满时也有front=0，rear=0，因此front==rear。5.2队列的顺序存储及实现为了区分这队空还是队满，通常有两个方法：（1）增加一个标志位。设这个标志位为flag，初始时，有flag=0；当入队列成功，则flag=1；出队列成功，有flag=0。则队列为空的判断条件为：