数据结构与算法(C++)讲队列

1/72EssentialofLectureSeven：一、队列的定义二、队列的存储结构三、队列基本操作的实现四、队列的应用难点2/72课前实战：程序阅读题请简述下面算法的功能ProcDemo(varS2:Seqstack;varS1:Seqstack){//Seqstack是顺序栈类型Seqstacktmp;DataTypex;//DataType是栈中元素的类型Initstack(tmp);Initstack(S2);while(notstackempty(S1)){//栈S1非空x=pop(S1);push(tmp,x);}while(notstackempty(tmp)){x=pop(tmp);push(S1,x);push(S2,x);}}3/72一、队列的定义queue只允许在一端插入元素，另一端删除元素的线性表允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)特点：先进先出(FIFO)队尾队头a1a2a3……an-1an出队列入队列4/721．intLength()const初始条件：队列已存在。操作结果：返回队列元素个数。2．boolEmpty()const初始条件：队列已存在。操作结果：如队列为空，则返回true，否则返回false3．voidClear()初始条件：队列已存在。操作结果：清空队列。队列的基本操作一、队列的定义queue5/72一、队列的定义（queue）4．voidTraverse(void(*Visit)(constElemType&))const初始条件：队列已存在。操作结果：依次对队列的每个元素调用函数(*visit)5．StatusCodeOutQueue(ElemType&e)初始条件：队列非空。操作结果：删除队头元素，并用e返回其值。队列的基本操作a2an……a16/72一、队列的定义（queue）6．StatusCodeGetHead(ElemType&e)const初始条件：队列非空。操作结果：用e返回队头元素。队列的基本操作a1a2an……7/72a1a2anan-1……7．StatusCodeInQueue(constElemType&e)初始条件：队列非空。操作结果：插入元素e为新的队尾。一、队列的定义（queue）队列的基本操作x8/72一、队列的定义（queue）双端队列deque插入和删除限定在线性表的两端进行的线性表a1a2anan-1……插入删除插入删除9/72一、队列的定义（queue）输入（出）受限的双端队列允许在一端进行插入和删除操作，在另一端只允许进行删除（插入）操作。a1a2anan-1……插入删除插入删除a1a2anan-1……插入删除10/72选择题1:已知输入序列为abcd经过输出受限的双端队列后能得到的输出序列有()A.dacbB.cadbC.dbcaD.bdac2:若以1234作为双端序列的输入序列,则既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列是()A.1234B.4132C.4231D.421311/721、链队列二、队列的存储结构队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题队空条件为front==rearfrontrear12/72templateclassElemTypeclassLinkQueue{protected://链队列实现的数据成员:NodeElemType*front,*rear;//队头队尾指针//辅助函数:voidInit();//初始化队列链队列类的实现二、队列的存储结构13/72public://抽象数据类型方法声明及重载编译系统默认方法声明:LinkQueue();//无参数的构造函数virtual~LinkQueue();//析构函数intLength()const;//求队列长度boolEmpty()const;//判断队列是否为空voidClear();//将队列清空voidTraverse(void(*Visit)(constElemType&))const;//遍历队列StatusCodeOutQueue(ElemType&e);//出队操作StatusCodeGetHead(ElemType&e)const;//取队头操作StatusCodeInQueue(constElemType&e);//入队LinkQueue(constLinkQueueElemType©);//复制构造函数LinkQueueElemType&operator=(constLinkQueueElemType©);//重载赋值};14/722、顺序队列frontrear空队列frontrearA入队AfrontrearB入队ABfrontrearC,D入队ABCDfrontrearA出队BCDfrontrearB出队CDfrontrearE,F,G入队CDEFGCDEFGfrontrearH入队,溢出15/72二、队列的存储结构2、顺序队列入队时将新元素按rear指示位置加入再将队尾指针先进一rear=rear+1。出队时将下标为front的元素取出,再将队头指针先进一front=front+1。队满时再进队将溢出出错；队空时再出队将队空处理。解决办法之一：将队列元素存放数组首尾相接，形成循环(环形)队列。16/7201234567front01234567front01234567frontrearAABCrearrear空队列A入队B,C入队0123456701234567A出队B出队01234567D,E,F,G,H,I入队frontBCrearAfrontBCrearfrontCrearDEFGHI3、循环队列CircularQueue17/72当J入队时，队满，此时front==rear但，队空时，front==rear可知，由此无法判断队列空和满。解决方法：（1）另设一个标识符或count统计。（2）少用一个元素空间，约定队头在队尾指针的下一个位置时作为队满的标志。3、循环队列18/72队列存放数组被当作首尾相接的表处理。队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。队头指针进1:front=(front+1)%maxSize;队尾指针进1:rear=(rear+1)%maxSize;队列初始化：front=rear=0;队空条件：front==rear;队满条件：(rear+1)%maxSize==front3、循环队列19/72templateclassElemTypeclassSqQueue{protected:intfront,rear;//队头队尾intmaxSize;//队列最大元素个数ElemType*elem;//元素存储空间//辅助函数:boolFull()const;//判断栈是否已满voidInit();//初始化队列循环队列类的实现20/72public://抽象数据类型方法声明及重载编译系统默认方法声明:SqQueue(intsize=DEFAULT_SIZE);//构造函数virtual~SqQueue();//析构函数intLength()const;//求队列长度boolEmpty()const;//判断队列是否为空voidClear();//将队列清空voidTraverse(void(*Visit)(constElemType&))const;//遍历队列StatusCodeOutQueue(ElemType&e);//出队操作StatusCodeGetHead(ElemType&e)const;//取队头操作StatusCodeInQueue(constElemType&e);//入队SqQueue(constSqQueueElemType©);//复制构造函数SqQueueElemType&operator=(constSqQueueElemType©);//赋值语句重载};21/72templateclassElemTypeboolSqQueueElemType::Full()const//操作结果：如队列已满，则返回true，否则返回false{returnLength()==maxSize-1;}templateclassElemTypevoidSqQueueElemType::Init()//操作结果：初始化队列{rear=front=0;}22/72templateclassElemTypeintSqQueueElemType::Length()const//操作结果：返回队列长度{return(rear-front+maxSize)%maxSize;}templateclassElemTypevoidSqQueueElemType::Traverse(void(*Visit)(constElemType&))const//操作结果：依次对队列的每个元素调用函数(*visit){for(intcurPosition=front;curPosition!=rear;curPosition=(curPosition+1)%maxSize){//对队列每个元素调用函数(*visit)(*Visit)(elem[curPosition]);}}23/72templateclassElemTypeStatusCodeSqQueueElemType::OutQueue(ElemType&e)//操作结果：如果队列非空，那么删除队头元素，并用e//返回其值，函数返回SUCCESS,否则函数返回//UNDER_FLOW，{if(!Empty()){//队列非空e=elem[front];//用e返回队头元素front=(front+1)%maxSize;//指向下一元素returnSUCCESS;}else{//队列为空returnUNDER_FLOW;}}24/72templateclassElemTypeStatusCodeSqQueueElemType::InQueue(constElemType&e)//操作结果：如果队列已满，返回OVER_FLOW,//否则插入元素e为新的队尾，返回SUCCESS{if(Full()){//队列已满returnOVER_FLOW;}else{//队列未满，入队成功elem[rear]=e;//插入e为新队尾rear=(rear+1)%maxSize;//rear指向新队尾returnSUCCESS;}}25/721）解决计算机主机与外设不匹配的问题；2）离散事件的模拟----模拟实际应用中的各种排队现象；3）用于处理程序中具有先进先出特征的过程；主要有：三、队列的应用26/72四、队列的应用(a+b)i例如：显示二项式的系数i=111i=2121i=31331i=41464127/72四、队列的应用111s=1t=12s+t1例如：显示二项式的系数28/72四、队列的应用例如：显示二项式的系数1211s=1t=23s+ts=tt=13s+t129/72四、队列的应用例如：显示二项式的系数13311s=1t=34s+ts=tt=36s+ts=tt=14s+t130/72四、队列的应用最小优先队列：出队操作删除最小的数据元素值最大优先队列：出队操作删除最大的数据元素值。简单实现方法：入队时不排在队尾，而是插入在队列的适当位置，使队列的元素有序。从队列类派生，重载入队操作即可。优先队列31/72四、队列的应用templateclassElemTypeclassMinPriorityLinkQueue:publicLinkQueueElemType//链队列的派生类{public:StatusCodeIn