数据结构-第四章队列

第四章队列☞

3.1什么是队列

3.2链队列

3.3顺序队列

3.4循环队列栈队列一、什么是队列队列：限定仅在一端进行插入，而在另一端进行删除操作的线性表。a1a2a3…………an出队列入队列队尾rear

队头front允许删除的一端称为队头(front)

允许插入的一端称为队尾(rear)

队列中没有元素时称为空队列二、队列的特点根据队列的定义可知，最先放入队列的元素最先出队列。

特点

：先进先出

也就是说，队列是一种后进先出的线性表，简称为FIFO(First

InFirstOut)表。例1：有一个队列，进队列序列为A、B、C，试给出所有可能的出队列序列。

队列只可能产生的输出序列ABC三、队列的抽象数据类型ADTQueue{数据对象：D＝{ai|ai

∈ElemSet,i=1,2,...,n,n≥0}数据关系：R＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

约定an

端为队尾，a1

端为队头。基本操作：

InitQueue(&Q)//操作结果：构造一个空队列Q

。

DestroyQueue(&Q)

//操作结果：队列Q被销毁。

ClearQueue(&Q)

//操作结果：将Q清为队列

QueueEmpty(Q)//操作结果：若队列Q为空队列，则返回TRUE，否则FALSE。

QueueLength(Q)

//操作结果：返回Q的元素个数，即队列的长度。

GetHead(Q,&e)

//操作结果：用e返回Q的队头元素。

EnQueue(&Q,e)

//操作结果：插入元素e为新的队尾元素。

DeQueue(&Q,&e)

//操作结果：删除Q的队头元素，并用e返回其值。}//ADTStack

3.1什么是队列☞

3.2链队列

3.3顺序队列

3.4队列的应用举例栈队列显然，仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由头指针和尾指针唯一确定。

链队列：用链表来存储队列

队头指针为

Q.front

队尾指针为

Q.reara2an∧a1frontrear头结点队头结点队尾结点Qtypedefstruct

QNode

{

QElemTypedata;

struct

QNode*next;}

QNode,*QueuePtr;队尾队头front

rearQtypedefstruct{

QueuePtr

front;//队头指针

QueuePtrrear;//队尾指针}LinkQueue;LinkQueueQ;StatusInitQueue(LinkQueue&Q)StatusDestroyQueue(LinkQueue&Q)StatusEnQueue(LinkQueue&Q,QElemTypee)StatusDeQueue(LinkQueue&Q,QElemType&e)二、链队列的基本操作voidInitQueue(LinkQueue&Q)frontrear一个空队列：{Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);

Q.front->next=NULL;}QStatusDestroyQueue(LinkQueue&Q)队尾队头front

rear{

QueuePtrp;while(Q.front){p=Q.front->next;free(Q.front);Q.front=p;

}//从前到后，逐个摘下结点并释放结点所用的内存空间

returnOK;}StatusEnQueue(LinkQueue&Q,QElemTypee){//往队尾插入一元素

p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->data=e; p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}队尾队头front

rearQe=2p2StatusDeQueue(LinkQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;

p=Q.front->next; e=p->data;Q.front->next=p->next;

if(Q.rear==p) Q.rear=Q.front;

free(p);returnOK;}队尾front

rearQp

3.1什么是队列

3.2链队列☞3.3顺序队列

3.4队列的应用举例栈队列顺序队列：用数组存储的队列由于队列的操作是尾入头出，所以为了操作方便，设置front

和rear25936870123456789frontrear#defineMAXQSIZE100typedefstruct{QElemType*base;//数组名}SqQueue;

intfront;

//头指针（数组下标）

intrear;//尾指针SqQueueQ；2593687012345678955basefrontrearQ空队列什么样？？012345678900basefrontrear初始建立队列时:Q.front=Q.rear=0

QInitQueue(Q)EnQueue(Q,2)？？012345678901basefrontrear元素e入队：Q.base[Q.rear++]=e;2Q52EnQueue(Q,e)EnQueue(Q,5)？？012345678903basefrontrear元素e出队：e=Q.base[Q.front++];

2Q53DeQueue(Q,e)e=21DeQueue(Q,e)？？

StatusDeQueue(SqQueue*Q,QElemType*e){/*若队列不空,则删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR*/if((*Q).front==(*Q).rear)/*队列空*/returnERROR;*e=(*Q).base[(*Q).front];(*Q).front=(*Q).front+1;returnOK;}DeQueue(Q,e)012345678901basefrontrear2QQueueLength(Q)5316234512Q.rear-Q.front队中元素的个数??QueueEmpty(Q)判断队空??Q.rear==Q.front340队最多放几个元素??MAXQSIZE-1//空增长MAXQSIZE//满增长注意：Q.rear所指的位置不存放队列元素012345678901basefrontrearQ234919当Q.rear==MAXQSIZE-1,但Q.front>0时，（队列中元素个数未“满”）若再有元素入队，会使下标出界，此时的溢出称为假上溢假上溢：循环队列(3循环队列.cpp)01234567891011121314示意图：设MAXQSIZE为15，（下标从0～14）Q.front=(Q.front+1)%MAXQSIZE//出队时Q.front++Q.rear++Q.rear=(Q.rear+1)%MAXQSIZE//入队时队中元素个数n=(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE//在Q.rear《Q.front时，保证为正数frontghkeabdrear0123456frontghkeabdrearrearrearrearfrontfrontfrontfrontfrontfront入队出队队满队空讨论：队空与队满的描述只凭Q.front==Q.rear

不能判断队列是“空”还是“满”

处理方法：少用一个空间，约定队头在队尾的下一个就算“满”rear0123456front循环队列空：Q.front==Q.rear循环队列满：

((Q.rear+1)%MAXQSIZE==Q.front//循环队列StatusInitQueue(SqQueue&Q){Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;returnOK;}012345600basefrontrearQ//循环队列intQueueLength(SqQueueQ){return;}(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE//循环队列StatusEnQueue(SqQueue&Q,QElemTypee){if((Q.rear+1)%MAXQSIZE==Q.front)//队满

returnERROR;Q.base[Q.rear]=e;Q.rear=;returnOK;