队列的定义表示实现ppt课件.ppt

《队列的定义表示实现ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、13.1栈（Stack）3.2队列（Queue)第三章栈和队列1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式23.2队列只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。1.定义一、概念：例如：队列Q=(a1,a2,a3,…，an)在队尾插入元素称为入队；在队首删除元素称为出队。队头元素队尾元素允许插入的一端为队尾，允许删除的一端为队头。3与线性表相同，仍为一对一关系。顺序队或链队，以循环顺序队更常见。只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。关键是掌握入队和出队操作，具体实现依顺序队或链队

2、的不同而不同。3.存储结构：4.运算规则：5.实现方式：2.逻辑结构：队列链队列：队列的链式表示和实现循环队列：队列的顺序表示和实现4（1）初始化队列InitQueue(&Q)（2）入队EnQueue(&Q,e)（3）出队DeQueue(&Q,&e)（4）获取队头元素内容GetHead(Q,&e)（5）判断队列是否为空QueueEmpty(Q)二、基本操作:建队列、判断队列是否为空、入队、出队、读队头元素值，等等。5链队列类型定义：typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;结点类型定义：typedefstr

3、uctQNode{QElemTypedata;//元素structQNode*next;//指向下一结点的指针}Qnode,*QueuePtr;关于整个链队的总体描述链队中任一结点的结构三、队列的表示和实现1.单链队列//-----队列的链式存储结构-----和单链表唯一的区别是多了一个队尾指针为什么要使用队首指针和队尾？？？如果固定队头，那么每次出队后，后面若干条数据都会往前挪。增加了开销量和浪费。为此，将买票窗口活动起来（即增加一个队首指针），出队后，后面的队列不需要移动。队列可以看成：“很窄的单向胡同”。“多台电脑共用一台打印机设备（优先级相等）”头指针和尾指针避免了删除时的挪动。7a

4、1∧an…Q.frontQ.rearQ.frontQ.rear∧空队列为了操作方便，添加一个头结点，令头指针指向头结点。Q.front==Q.rear队空的条件：Q.front=Q.rear;(有头结点）Q.front=NULL;(无头结点)8StatusInitQueue(LinkQueue&Q){//构造一个空队列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);//存储分配失败Q.front->next=NULL;//头结点的next域为空returnOK;}//-----基本操作的算法描

5、述-----建队操作——构造空队列Q9Q(队尾)(队首)fronta1a2a3^rearp链队会满吗？一般不会，因为删除时有free动作。除非内存不足！入队（尾部插入）：rear->next=S;rear=S;出队（头部删除）：p=front->next;//P指向第一个元素front->next=p->next;free(p);Se^链队列的入队和出队操作10StatusEnQueue(LinkQueue&Q,QElemTypee){//插入元素e为Q的新的队尾元素p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);//存储分配失败

6、p->data=e;//将值e赋给新节点；p->next=NULL;//新节点的next域为空；Q.rear->next=p;//原队尾节点指针指向新节点；Q.rear=p;//队尾指针指向新节点returnOK;}11StatusDeQueue(LinkQueue&Q,QElemType&e){//若队列不空，则删除Q的队头元素，//用e返回其值，并返回OK；否则返回ERRORif(Q.front==Q.rear)returnERROR;//判空p=Q.front->next;//p指向队头节点e=p->data;//将队头元素赋给eQ.front->next=p->next;//头结点指

7、向下一个节点if(Q.rear==p)//如果删除的是队尾节点Q.rear=Q.front;//修改队尾指针，让其指向头//结点。一定要考虑free(p);returnOK;}队列的顺序存储结构(循环队列，重点）typedefstruct{QElemType*base;//初始化动态分配空间基址intfront;//头指针，若队列不空，指向队列首元素intrear;//尾指针，若队列不空，//指向队列尾元素的