DS03_栈和队列04_队列.ppt

《DS03_栈和队列04_队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章栈和队列3.1栈3.2栈的应用举例3.3栈与递归的实现3.4队列3.4.1抽象数据类型队列的定义3.4.2链队列——队列的链式表示和实现3.4.3循环队列——队列的顺序表示和实现3.4.1抽象数据类型队列的定义队列的定义所有的插入只能在表的一端(队尾)进行，而所有的删除只能表的另一端(队头)进行的线性表。队列的特点最先入队的最先出队，所以又把队列称为先进先出表(FirstInputFirstOutput，简称FIFO）。队尾(Rear):表中允许插入的一端队头(Front):允许删除的一端入队：将一个数据插入到队尾的操作出队：读取队头结点数据并删除该结点的操作队列的抽象数据类型定义ADT

2、Queue{数据对象：D＝{ai

3、ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R＝{

4、ai-1,ai∈D,i=2,…,n}约定其中a1端为队列头，an端为队列尾。基本操作：……}//ADTQueue;队列的基本操作：1）InitQueue(&Q)操作结果：构造空队列Q2）DestroyQueue(&Q)条件：队列Q已存在；结果：队列Q被销毁3）ClearQueue(&Q)条件：队列Q已存在；结果：将Q清空4）QueueEmpty(Q)条件：队列Q已存在；结果：若Q为空队列，则返回TRUE，否则返回FALSE5）QueueLength(Q)初始条件：队列Q已存在

5、操作结果：返回Q的元素个数，即队长6）GetHead(Q,&e)初始条件：Q为非空队列操作结果：用e返回Q的队头元素7)EnQueue(&Q,e)初始条件：队列Q已存在操作结果：插入元素e为Q的新的队尾元素8）DeQueue(&Q,&e)初始条件：Q为非空队列操作结果：删除Q的队头元素，用e返回值9）QueueTraverse(Q,visit())从队头到队尾，依次对Q的每个数据元素调用函数visit()第3章栈和队列3.1栈3.2栈的应用举例3.3栈与递归的实现3.4队列3.4.1抽象数据类型队列的定义3.4.2链队列——队列的链式表示和实现3.4.3循环队列——队列的顺序表示和实现与栈类似

6、，队列的物理存储可以用顺序存储结构，也可用链式存储结构。相应地，队列的存储方式也分为两种，即顺序队列和链式队列。3.4.2链队列——队列的链式表示和实现队列运算指针变化状况a）空队列Q.frontQ.rear∧a)x∧Q.frontQ.rearb)Q.frontQ.rearxy∧c)Q.frontQ.rearxy∧d)b）元素x入队c）y入队d）x出队链队列的类型定义链队的结点定义typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;为了方便起见，将链队列设计为一个结构体类型typedefstruct{QueueP

7、trfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;队列的基本操作--构造一个空队列voidInitQueue(LinkQueue&Q){//构造一个空队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;}Q．frontQ．rear∧销毁空队列voidDestroyQueue(LinkQueue&Q){//销毁队列Q(无论空否均可)，释放所有结点while(Q.front){Q.rear=Q.front->next;fr

8、ee(Q.front);Q.front=Q.rear;}}Q.frontQ.rearxy∧c)入队列StatusEnQueue(LinkQueue&Q,QElemTypee){p=(QueuePrt)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);//存储分配失败p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}epfronta1an∧rear∧rear出队列StatusDeQueue(LinkQueue&Q,QElemType&e){If(Q.front==Q.rear)returnERRO

9、R;//队空，报错p=Q.front->next;Q.front->next=p->next;e=p->data;//出队前只有一个结点if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}fronta1a2an∧rearp第3章栈和队列3.1栈3.2栈的应用举例3.3栈与递归的实现3.4队列3.4.1抽象数据类型队列的定义3.4.2链队列——队列的链式表示和