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

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

1、第5章队列队列和栈一样，也是一种重要的线性结构。它们都是操作受限制的线性表，其特殊性在于限制线性表的插入和删除等操作的位置。队列在操作系统和事务管理等软件设计中应用广泛，如键盘输入缓冲区问题就是利用队列的思想实现的。本章的学习内容包括队列的定义、队列的顺序存储、链式存储及应用.5.1队列的定义队列也是一种限定性线性表，允许在表的一端进行插入操作，在表的另一端进行删除操作。本节主要介绍队列的定义和队列的抽象数据类型。5.1.1队列的定义队列是一种特殊的线性表，它包含一个队头（front）和一个队尾（rear）。其中，队头只允许删除元素，队尾只允许插入元素。队列的特点是先进入队列的元素先出来

2、，即先进先出（FIFO）。5.1.2队列的抽象数据类型1．数据对象集合2．基本操作集合5.2队列的顺序表示及实现队列有两种存储表示：顺序存储和链式存储。采用顺序存储结构的队列被称之为顺序队列，采用链式存储结构的队列被称之为链式队列。5.2.1顺序队列的表示顺序队列通常采用一维数组进行存储。其中，连续的存储单元依次存放队列中的元素。同时，使用两个指针分别表示数组中存放的第一个元素和最后一个元素的位置。其中，指向第一个元素的指针被称为队头指针front，指向最后一个元素的位置的指针被称为队尾指针rear。5.2.1顺序队列的表示5.2.1顺序队列的表示顺序队列的类型定义如下：#defineQ

3、ueueSize40/*队列的容量*/typedefstructSqueue{DataTypequeue[QueueSize];intfront,rear;/*队头指针和队尾指针*/}SeqQueue;5.2.1顺序队列的表示（1）队列的初始化操作。voidInitQueue(SeqQueue*SQ)/*将顺序队列初始化为空队列只需要把队头指针和队尾指针同时置为0*/{SQ->front=SQ->rear=0;}5.2.1顺序队列的表示（2）判断队列是否为空。intQueueEmpty(SeqQueueSQ)/*判断队列是否为空，队列为空返回1，否则返回0*/{if(SQ.front==

4、SQ.rear)return1;elsereturn0;}5.2.1顺序队列的表示（3）入队操作。intEnterQueue(SeqQueue*SQ,DataTypex)/*将元素x插入到顺序队列SQ中，插入成功返回1，否则返回0*/{if(SQ->rear==QueueSize)return0;SQ->queue[SQ->rear]=x;SQ->rear=SQ->rear+1;return1;}5.2.1顺序队列的表示（4）出队操作。intDeleteQueue(SeqQueue*SQ,DataType*e){if(SQ->front==SQ->rear)return0;else{*e

5、=SQ->queue[SQ->front];SQ->front=SQ->front+1;return1;}}5.2.1顺序队列的表示例5_1编程实现顺序队列的入队操作和出队操作，并将出队结果输出。5.2.2顺序队列的“假溢出”按照以上顺序存储的方法，有可能会造成“假溢出”。5.2.3顺序循环队列的表示1．顺序循环队列2．顺序循环队列的队空和队满判断5.2.3顺序循环队列的表示（1）增加一个标志位。设这个标志位为flag，初始化为flag=0，当入队列成功flag=1，出队列成功flag=0，则队空的判断条件：front==rear&&flag==0，队满的判断条件：front==rear

6、&&flag==1。5.2.3顺序循环队列的表示（2）少用一个存储空间。队空的判断条件front==rear，front==(rear+1)%QueueSize表示队满。入队的操作：rear=（rear+1）%QueueSize，Q[rear]=x。出队的操作：front=（front+1）%QueueSize。5.2.4顺序循环队列的实现顺序循环队列的主要操作包括初始化操作、判断队列是否为空、入队操作、出队操作、取队头元素和清空队列。5.2.4顺序循环队列的实现（1）初始化操作。voidInitQueue(SeqQueue*SCQ){SCQ->front=SCQ->rear=0;}5.

7、2.4顺序循环队列的实现（2）判断队列是否为空。intQueueEmpty(SeqQueueSCQ){if(SCQ.front==SCQ.rear)return1;elsereturn0;}5.2.4顺序循环队列的实现（3）入队操作。intEnterQueue(SeqQueue*SCQ,DataTypee){if(SCQ->front==(SCQ->rear+1)%QueueSize)return0;SQ->queue[SCQ->r