资源描述：
《数据结构第07讲-队列-C.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第3章栈和队列3.1栈3.2栈的应用举例3.3栈与递归的实现3.4队列3.4.1抽象数据类型队列的定义3.4.2链队列——队列的链式表示和实现3.4.3循环队列——队列的顺序表示和实现3.4.1抽象数据类型队列的定义1.队列的定义简称队，是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表。2.队列的特点由于队列的插入和删除操作分别是在各自一端进行，每个元素必然按照进入的次序离队，所以又把队列称为先进先出表(FirstInputFirstOutput，简称FIFO）。相关术语：表中允许插入的一端称为队尾(Rear)，允许删除的一
2、端称为队头(Front)向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除元素称为离队或出队，元素离队后，其后继元素就成为新的队首元素3.队列的常见应用1）图形的广度优先搜索法；2）优先队列；3）操作系统中的工作调度；4）用于“spooling”；先将输出数据写在磁盘上，再由打印机把先存入者先处理的顺利将数据输出。4.队列的类型定义ADTQueue{数据对象：D＝{ai
3、ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R＝{
4、ai-1,ai∈D,i=2,…,n}约定其中a1端为队列头，an端为
5、队列尾。基本操作：}ADTQueue队列的常用操作1）InitQueue(&Q)操作结果：构造空队列Q2）DestroyQueue(&Q)条件：队列Q已存在；结果：队列Q被销毁3）QueueLength(Q)初始条件：队列Q已存在操作结果：返回Q的元素个数，即队长4）GetHead(Q,&e)初始条件：Q为非空队列操作结果：用e返回Q的队头元素5）EnQueue(&Q,e)初始条件：队列Q已存在操作结果：插入元素e为Q的新的队尾元素6）DeQueue(&Q,&e)初始条件：Q为非空队列操作结果：删除Q的队头元素，用e返回值7）ClearQueue(&
6、Q)条件：队列Q已存在；结果：将Q清空第3章栈和队列3.1栈3.2栈的应用举例3.3栈与递归的实现3.4队列3.4.1抽象数据类型队列的定义3.4.2链队列——队列的链式表示和实现3.4.3循环队列——队列的顺序表示和实现3.4.2链队列——队列的链式表示和实现队列的物理存储可以用顺序存储结构，也可用链式存储结构。相应地，队列的存储方式也分为两种，即顺序队列和链式队列。1.链队列的类型定义#defineMAXQSIZE100//最大队列长度typedefstructQnode{QElemTypedata;stuctQnode*next;}QNode,
7、*QuenePtr;typedefstruct{QuenePtrfront;//队头指针QuenePtrrear;//队尾指针}LinkQueue;2.队列运算指针变化状况a）空队列Q．frontQ．rear∧a)x∧Q．frontQ．rearb)Q．frontQ．rearxy∧c)Q．frontQ．rearxy∧d)b）元素X入队列c）Y入队列d）X出队列3.队列在抽象类型中的几种操作举例例1：构造一个空队列StatusInitQueue(LinkQueue&Q){//构造空队列QQ.front=Q.rear=(QueuePtr)malloc(si
8、zeof(QNode));If(!Q.front)exit(OVERFLOW);//存储分配失败Q.front->next=NULL;returnOK;}//InitQueue;Q．frontQ．rear∧例2：销毁空队列StatusDestoryQueue(LinkQueue&Q){//销毁队列Qwhile(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}returnOK;}//DestoryQueue;例3：入队列StatusEnQueue(LinkQueue&Q,QElem
9、Typee){p=(QueuePrt)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);//存储分配失败p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}∧a1anQ.frontQ.rear∧eP例4：出队列StatusDeQueue(LinkQueue&Q,QElemType&e){If(Q.front==Q.rear)returnERROR;p=Q.front->next;Q.front->next=p->next;e=p->data;if(Q.r
10、ear==p)Q.rear=Q.front;free(p);returnOK;}//DeQueue;Q．fr
