队列的定义、表示、实现.ppt

1,3.1栈（Stack）3.2队列（Queue),第三章栈和队列,1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式,1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式,2,3.2队列,只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。,1.定义,一、概念：,例如：队列Q=(a1,a2,a3,，an),在队尾插入元素称为入队；在队首删除元素称为出队。,队头元素,队尾元素,允许插入的一端为队尾，允许删除的一端为队头。,3,与线性表相同，仍为一对一关系。,顺序队或链队，以循环顺序队更常见。,只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。,关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。,4,二、队列的抽象数据类型定义,ADTQueue数据对象：Dai|aiElemSet,i=1,2,.,n,n0数据关系：R1|ai-1,aiD,i=2,.,n约定a1端为队列头，an端为队列尾。,基本操作：,ADTStack,5,（1）初始化队列InitQueue(/队头指针QueuePtrrear;/队尾指针LinkQueue;,结点类型定义：typedefstructQNodeQElemTypedata;/元素structQNode*next;/指向下一结点的指针Qnode,*QueuePtr;,关于整个链队的总体描述,链队中任一结点的结构,三、队列的表示和实现,1.单链队列,/-队列的链式存储结构-,7,a1,an,Q.frontQ.rear,Q.frontQ.rear,空队列,为了操作方便，添加一个头结点，令头指针指向头结点。,Q.front=Q.rear,8,StatusInitQueue(LinkQueue,/-基本操作的算法描述-,建队操作构造空队列Q,9,链队会满吗？,一般不会，因为删除时有free动作。除非内存不足！,入队（尾部插入）：rear-next=S;rear=S;出队（头部删除）：p=front-next;front-next=p-next;free(p);,链队列的入队和出队操作,10,StatusEnQueue(LinkQueue,11,StatusDeQueue(LinkQueue,12,队列的顺序存储结构如下图所示：,附设两个指针front和rear分别指示队列头元素的位置和队列尾元素的下一个位置,约定：初始化建空队列时，令front=rear=0；,2.顺序队列,13,（2）空队列的特征？约定：front=rear,问题：（1）怎样实现入队和出队操作？核心语句如下：,入队(尾部插入)：Qrear=e;rear+;出队(头部删除)：e=Qfront;front+;,（3）队列会满吗？极易装满！因为数组通常有长度限制，而其前端空间无法释放。有假溢出现象。如图：,14,解决假溢出的途径,采用循环队列,在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但实际上数组中还有空位置，这就叫“假溢出”。,讨论：什么叫“假溢出”？如何解决？,将存储队列元素的一维数组首尾相接，形成一个环状。,15,16,新问题：在循环队列中，队空时front=rear；队满时也会有front=rear；判决条件将出现二义性！解决方案有二：使用一个计数器记录队列中元素个数（即队列长度）；人为浪费一个单元，约定：队列头指针在队列尾指针的下一位置上作为队列呈“满”状态的标志。则队满特征可改为front=(rear+1)%N（N为最大队列长度）；,实际中常选用方案2（人为浪费一个单元）,17,建队核心语句：Q.base=(QElemType*)malloc(sizeof(QElemType）*MAXQSIZE);/分配空间,关于整个顺序队的总体描述,#defineMAXQSIZE100/最大队列长度typedefstructQElemType*base;/队列的基址intfront;/队头指针intrear;/队尾指针SqQueue,/-循环队列队列的顺序存储结构-,18,队空条件:front=rear(初始化时：front=rear)队满条件：front=(rear+1)%N(N=MAXQSIZE)队列长度：L=（Nrearfront）%N,问3：在具有N个单元的循环队列中，队满时共有多少个元素？,N-1个,6,问1：左图中队列MAXQSIZEN=？,问2：左图中队列长度L=？,5,19,例1.一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置?,解：由图可知，队头和队尾指针的初态分别为front=1和rear=0。,删除4个元素后front=5；,再插入4个元素后，rear=(0+4)%6=4,rear=4,20,例2.Q010是一个循环队列，初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。d,e,b,g,h入队d,e出队i,j,k,l,m入队b出队n,o,p入队,21,讨论：循环队列的基本操作如何实现？以建队、入队和出队三种基本操作为例,1）初始化一个空队列,算法要求：生成一空队列算法操作：为队列分配基本容量空间设置队列为空队列，其特征即：front=rear=0（也可为任意单元，如1，2，）,22,建队的完整算法：,StatusInitQueue(SqQueue,23,算法说明：向循环队列的队尾插入一个元素分析：(1)插入前应当先判断队列是否满？if(Q.rear+1)%MAXQSIZE)=Q.front)returnERROR;(2）插入动作Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;,2）入队操作,队列尺寸,先存放元素，后移动队尾指针,24,StatusEnQueue(SqQueue,入队操作完整算法,25,3）出队操作,算法说明：删除队头元素，返回其值e分析：（1）在删除前应当判断队列是否空？if(Q.front=Q.rear)returnERROR;（2）删除动作分析：前面约定指针front指向队首元素的位置，故：e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;,队列尺寸,先取出元素，后移动队头指针,26,StatusDeQueue(SqQueue/DeQueue,出队操作完整算法,27,例3：编写一个算法，利用栈和队列的基本运算将指定队列中的内容进行逆转。,分析：假设为循环队列。建立一个临时栈temps，将指定队列Q中的所有元素出队并入栈到temps中，这样队列Q为空，再将temps中的所有元素出栈并入队到Q队中，这样Q队列中的内容发生了逆转。算法如下：,voidreverse(SqQueue,28,while(!QueueEmpty(Q)/初始化temps栈DeQueue(Q,x);Push(temps,x);While(!StackEmpty(temps)Pop(temps,x);EnQueue(Q,x);,29,本章小结,线性表、栈、队的异同点：相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链式存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入