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

3.1 3.1 栈（栈（StackStack）3.2 3.2 队列队列 （Queue)Queue)第三章第三章 栈和队列栈和队列1.定义定义2.逻辑结构逻辑结构3.存储结构存储结构4.运算规则运算规则5.实现方式实现方式1.定义定义2.逻辑结构逻辑结构3.存储结构存储结构4.运算规则运算规则5.实现方式实现方式13.2 3.2 队列队列只能在表的一端进行插入运算，在表的只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。另一端进行删除运算的线性表。1.1.1.1.定义定义定义定义一、概念：一、概念：例如：队列例如：队列 Q=(a1 ,a2 ,a3 ,，an)在队尾插入元素称为在队尾插入元素称为入队入队入队入队；在队首删除元素称为在队首删除元素称为出队出队出队出队。队头元素队头元素队尾元素队尾元素允许插入的一端为队尾，允许删除的一允许插入的一端为队尾，允许删除的一端为队头。端为队头。2与线性表相同，仍为一对一关系。与线性表相同，仍为一对一关系。顺序队顺序队或或链队链队，以，以循环顺序队循环顺序队更常见。更常见。只能在只能在队首队首和和队尾队尾运算，且访问结点运算，且访问结点时依照时依照先进先出（先进先出（FIFOFIFO）的原则。的原则。关键是掌握关键是掌握入队入队和和出队出队操作，具体实操作，具体实现依顺序队或链队的不同而不同。现依顺序队或链队的不同而不同。3.3.存储结构：存储结构：存储结构：存储结构：4.4.运算规则：运算规则：运算规则：运算规则：5.5.实现方式实现方式实现方式实现方式 ：2.2.2.2.逻辑结构：逻辑结构：逻辑结构：逻辑结构：3二、队列的抽象数据类型定义二、队列的抽象数据类型定义ADT Queue 数据对象数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系数据关系：R1|ai-1,aiD,i=2,.,n 约定a1 端为队列头，an 端为队列尾。基本操作：基本操作：ADT Stack4（1 1）初始化队列）初始化队列 InitQueue(&Q)InitQueue(&Q)（2 2）入队）入队 EnQueue(&Q,e)EnQueue(&Q,e)（3 3）出队）出队 DeQueue(&Q,&e)DeQueue(&Q,&e)（4 4）获取队头元素内容）获取队头元素内容 GetHead(Q,&e)GetHead(Q,&e)（5 5）判断队列是否为空）判断队列是否为空 QueueEmpty(Q)QueueEmpty(Q)基本操作基本操作:建队列、判断队列是否为空、入队、建队列、判断队列是否为空、入队、出队、读队头元素值，等等。出队、读队头元素值，等等。5链链队列队列类型定义：类型定义：typedef struct QueuePtr front;/队头指针 QueuePtr rear;/队尾指针 LinkQueue;结点结点类型定义：类型定义：typedef struct QNode QElemType data;/元素 struct QNode *next;/指向下一结点的指针 Qnode,*QueuePtr;关于整个链队的关于整个链队的总体描述总体描述链队中任一链队中任一结点的结构结点的结构三、队列的表示和实现三、队列的表示和实现1.1.单链队列单链队列/-队列的链式存储结构队列的链式存储结构-6a1anQ.frontQ.rearQ.frontQ.rear空队列空队列为了操作方便，添加一个头结点，令头指针指向头结点。为了操作方便，添加一个头结点，令头指针指向头结点。Q.front=Q.rear7 Status InitQueue(LinkQueue&Q)/构造一个空队列 Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);/存储分配失败 Q.front-next=NULL;return OK;/-基本操作的算法描述基本操作的算法描述-建队操作建队操作建队操作建队操作构造空队列构造空队列构造空队列构造空队列Q Q Q Q8Q(队尾队尾)(队首队首)fronta1a2a3rearp链队会满吗？链队会满吗？一般不会，因为删除时有一般不会，因为删除时有freefree动作。除动作。除非内存不足！非内存不足！入队（尾部插入）：入队（尾部插入）：rear-next=S;rear=S;出队（头部删除）：出队（头部删除）：p=front-next;front-next=p-next;free(p);Se链队列的入队和出队操作链队列的入队和出队操作9 Status EnQueue(LinkQueue&Q,QElemType e)/插入元素e为Q的新的队尾元素 p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);/存储分配失败 p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;10 Status DeQueue(LinkQueue&Q,QElemType&e)/若队列不空，则删除Q的队头元素，/用 e 返回其值，并返回OK；否则返回ERROR if(Q.front=Q.rear)return ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;/一定要考虑 free(p);return OK;11队列的顺序存储结构如下图所示：队列的顺序存储结构如下图所示：附设两个指针附设两个指针front和和rear分别指示队列头元素的位分别指示队列头元素的位置和队列尾元素的下一个位置置和队列尾元素的下一个位置约定：约定：初始化建空队列时，令初始化建空队列时，令front=rear=0front=rear=0；2.2.顺序队列顺序队列12（2 2）空队列的特征？空队列的特征？约定：约定：front=rearfront=rear问题：（问题：（1 1）怎样实现入队和出队操作？）怎样实现入队和出队操作？核心语句如下：核心语句如下：入队入队(尾部插入尾部插入)：Qrear=e;rear+;Qrear=e;rear+;出队出队(头部删除头部删除)：e=Qfront;front+;e=Qfront;front+;（3 3）队列会满吗？）队列会满吗？极易装满！极易装满！因为数组通常有长度限制，而其因为数组通常有长度限制，而其前端空间无法释放。有假溢出现象。前端空间无法释放。有假溢出现象。如图：如图：13解决假溢出的途径解决假溢出的途径 采用循环队列采用循环队列在顺序队中，当尾指针已经到了数组的上界，在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但实际上数组中还有空不能再有入队操作，但实际上数组中还有空位置，这就叫位置，这就叫“假溢出假溢出”。讨论：什么叫讨论：什么叫“假溢出假溢出”？如何解决？如何解决？将存储队列元素的一维数组首尾相接，将存储队列元素的一维数组首尾相接，形成一个环状。形成一个环状。14a3a2a10123N-1rearfront循环队列（臆造）循环队列（臆造）循环队列（臆造）循环队列（臆造）顺序队列顺序队列顺序队列顺序队列a3a2a1frontrear 0 1 2 3 .N-115新问题：新问题：在循环队列中，队空时在循环队列中，队空时 front=rear；队满时也；队满时也会有会有 front=rear；判决条件将出现；判决条件将出现二义性二义性！解决方案有二：解决方案有二：使用一个计数器记录队列中元素个数（即队列长度）；使用一个计数器记录队列中元素个数（即队列长度）；人为浪费一个单元，约定：队列头指针在队列尾指针的人为浪费一个单元，约定：队列头指针在队列尾指针的 下一位置上作为队列呈下一位置上作为队列呈“满满”状态的标志。则队满特征可状态的标志。则队满特征可改为改为front=(rear+1)%N front=(rear+1)%N（N N为最大队列长度）为最大队列长度）；实际中常选用方案实际中常选用方案2 2（人为人为浪费一个单元）浪费一个单元）16建队核心语句：Q.base=(QElemType*)malloc(sizeof(QElemType）*MAXQSIZE);/分配空间关于整个顺序关于整个顺序队的总体描述队的总体描述#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base;/队列的基址 int front;/队头指针 int rear;/队尾指针 SqQueue/-循环队列循环队列队列的顺序存储结构队列的顺序存储结构-17队空条件队空条件:front=rear (初始化时：初始化时：front=rear)队满条件队满条件：front=(rear+1+1)%N (N=MAXQSIZE)队列长度：队列长度：L=（Nrearfront）%N J2 J3J1 J4 J5frontrear问问3 3：在具有在具有N N个单元的循个单元的循环队列中，队满时共有多少环队列中，队满时共有多少个元素？个元素？N-1个个6 问问1 1：左图中队列左图中队列MAXQSIZE MAXQSIZE N=N=？问问2 2：左图中队列左图中队列长度长度L=L=？518例例1.1.一循环队列如下图所示，若先删除一循环队列如下图所示，若先删除4 4个元素，接个元素，接着再插入着再插入4 4个元素，请问队头和队尾指针分别指向哪个个元素，请问队头和队尾指针分别指向哪个位置位置?J2 J3J1 J4 J5front=1rear=0解：解：由图可知，队头和队尾指针的初态分别为由图可知，队头和队尾指针的初态分别为front=1front=1和和rear=0rear=0。删除删除4 4个元素后个元素后front=5front=5；再插入再插入4 4个元素后，个元素后，rear=(0+4)%6=4rear=(0+4)%6=4 front=5J6 J5J7J8 J9rear=4rear=0front=519例例2.Q0102.Q010是一个循环队列，初始状态为是一个循环队列，初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明状态变化情况，若不能入队，请指出其元素，并说明理由。理由。d,e,b,g,h d,e,b,g,h 入队入队d,e d,e 出队出队i,j,k,l,m i,j,k,l,m 入队入队b b 出队出队n,o,p n,o,p 入队入队20讨论：循环队列的基本操作如何实现？讨论：循环队列的基本操作如何实现？以建队、入队和出队三种基本操作为例以建队、入队和出队三种基本操作为例1）初始化一个空队列）初始化一个空队列算法要求：生成一空队列算法要求：生成一空队列算法操作：为队列分配基本容量空间算法操作：为队列分配基本容量空间 设置队列为空队列，其特征即：设置队列为空队列，其特征即：front=rear=0（也可为任意单元，如（也可为任意单元，如1，2，）21建队的完整算法：建队的完整算法：Status InitQueue(SqQueue&Q)/初始化空循环队列 Q Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType）);/分配空间 if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;/置空队列 return OK;/InitQueue;/InitQueue;22算法说明：向循环队列的算法说明：向循环队列的队尾插入队尾插入一个元素一个元素分分 析析：(1)插入前应当先判断队列是否满？插入前应当先判断队列是否满？if(Q.rear+1)%MAXQSIZE)=Q.front)return ERROR;(2）插入动作）插入动作 Q.base Q.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;2）入队操作入队操作队列尺寸队列尺寸先存放元素，后移先存放元素，后移动队尾指针动队尾指针23Status EnQueue(SqQueue&Q,QElemType e)/向循环队列 q 的队尾加入一个元素 e if(Q.rear+1)%MAXQSIZE=Q.front )return ERROR;/队满则上溢 Q.base Q.rear =e;/新元素e入队 Q.rear=(Q.rear+1)%MAXQSIZE;/指针后移 return OK;/EnQueue;入队操作完整算法入队操作完整算法243 3）出队操作）出队操作算法说明：删除队头元素，返回其值算法说明：删除队头元素，返回其值 e 分分 析：析：（1）在删除前应当判断队列是否空？在删除前应当判断队列是否空？if(Q.front=Q.rear)return ERROR;（2）删除动作分析：）删除动作分析：前面约定指针前面约定指针frontfront指向队首元素的位置，故指向队首元素的位置，故：e=Q.base Q.front ;Q.front=(Q.front+1)%MAXQSIZE;队列尺寸队列尺寸先取出元素，后先取出元素，后移动队头指针移动队头指针25Status DeQueue(SqQueue&Q,QElemType&e)/若队列不空，删除循环队列q的队头元素，/由 e 返回其值，并返回OK if(Q.front=Q.rear)return ERROR;/队列空 e=Q.base Q.front ;Q.front=(Q.front+1)%MAXQSIZE;return OK;/DeQueue出队操作完整算法出队操作完整算法26例例3：编写一个算法，利用栈和队列的基本运算将指：编写一个算法，利用栈和队列的基本运算将指定队列中的内容进行逆转。定队列中的内容进行逆转。分析：假设为循环队列。建立一个临时栈分析：假设为循环队列。建立一个临时栈temps，将指，将指定队列定队列Q中的所有元素出队并入栈到中的所有元素出队并入栈到temps中，这样队中，这样队列列Q为空，再将为空，再将temps中的所有元素出栈并入队到中的所有元素出栈并入队到Q队队中，这样中，这样Q队列中的内容发生了逆转。算法如下：队列中的内容发生了逆转。算法如下：void reverse(SqQueue&Q)QElemType x;SqStack temps;InitStack(temps);27 while(!QueueEmpty(Q)/初始化初始化temps栈栈 DeQueue(Q,x);Push(temps,x);While(!StackEmpty(temps)Pop(temps,x);EnQueue(Q,x);28本章小结本章小结线性表、栈、队的异同点：线性表、栈、队的异同点：相相相相同同同同点点点点：逻逻辑辑结结构构相相同同，都都是是线线性性的的；都都可可以以用用顺顺序序存存储储或或链链式式存存储储；栈栈和和队队列列是是两两种种特特殊殊的的线线性性表表，即即受受限限的线性表的线性表（只是对插入、删除运算加以限制）。（只是对插入、删除运算加以限制）。运算规则不同：运算规则不同：线性表可任意存取；线性表可任意存取；栈是后进先出表栈是后进先出表LIFOLIFO；队列是先进先出表队列是先进先出表FIFOFIFO。用途不同，用途不同，线性表比较通用；堆栈用于函线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散数调用、递归和简化设计等；队列用于离散事件模拟、事件模拟、OSOS作业调度和简化设计等。作业调度和简化设计等。不同点：不同点：不同点：不同点：29第第3章作业章作业3.3 3.4 3.6 3.10 3.12 3.3 3.4 3.6 3.10 3.12 3.3 3.4 3.6 3.10 3.12 3.3 3.4 3.6 3.10 3.12 3.16 3.17 3.16 3.17 3.16 3.17 3.16 3.17 3.29 3.323.29 3.323.29 3.323.29 3.3230