数据结构-队列.ppt

第二章队列吉林大学计算机学院谷方明[e-mail]例子：电话号码向计算机专业的同学要电话号码，他（她）不会直接给你的，原因你懂的。他（她）会告诉你一串加密过的数字，同时告诉你解密的规则。规则是这样的：首先将第1个数删除，紧接着将第2个数放到这串数的末尾，再将第3个数删除并将第4个数放到这串数的末尾…，直到剩下最后一个数，把这个数也删除。按删除的顺序将删除的数连在一起，就是电话号了。例如：586591461.队列的定义队列（queue）是一种操作受限的线性表，它的所有插入都在表的一端进行，所有的删除都在表的另一端进行。例子食堂窗口进程调度队列的特性：先进先出。栈也称作后进先出表(FirstInFirstOut，FIFO)。队头（front）：进行删除的一端；队尾（rear）：进行插入的一端；空队列：没有元素的队列。插入：入队删除：出队术语a1a2a3a4a5队尾队头入队出队队列的基本操作（1）队列初始化（2）入队(插入）（3）出队（删除）（4）读取队首元素（5）判断队列是否空（6）确定队列中元素个数（7）置空队列2.队列的顺序存储按顺序存储方式存放队列元素，称为顺序队。存放队列元素的数组：Tqlist[MaxQSize]front队首元素的下标rear队尾元素的下标加1队列空：front==rear队列满：rear==MaxQSize……012MaxQsize-1front=0rear=0初始状态插入队尾元素：rear=rear+1front=0rear=1……a0012MaxQsize-1a0进队front=0……a0a1a2012MaxQsize-1a1a2进队rear=3删除队首元素：front=front+1front=1……a1a2012MaxQsize-1a0出队rear=3front=3……012MaxQsize-1a1a2出队rear=3假溢出012MaxQsize-1rear=nfront=n-3……an-3an-2无法利用的空间x循环队列front=n-3……an-3an-2012MaxQsize-1rear=n-1n-3rear=n-1an-3an-20.1...front=n-3n-2插入元素：rear顺时针移动一位front=n-3……an-3an-2012MaxQsize-1rear=0xn-3an-3rear=0an-20.1n-1...front=n-3n-2xrear=(rear+1)MODMaxQSize删除元素：front顺时针移动一位front=(front+1)MODMaxQSize;rear0front=9.1...CD删除Crearfront=00.1...D循环队列front指定队首位置，删除一个元素就将front顺时针移动一位；rear指向元素要插入的位置，插入一个元素就将rear顺时针移动一位；count存放队列中元素的个数，当count等于MaxQSize时，不可再向队列中插入元素。队空：count=0队满：count=MaxQSize顺序队列类AQueue的类声明templateclassTclassAQueue{private:intfront;//队首所在数组元素下标intrear;//新元素要插入的位置（下标）intcount;//队列中元素个数T*QArray;//存放队列元素的数组intSize;//存放队列的数组规模public:AQueue(intMaxQueueSize=10);//构造函数~AQueue(){delete[]QArray;}//析构voidQInsert(constT&item);//向队尾插入元素itemvoidQDelete(T&item);//删除队首元素并将该元素值保存至itemTQFront()const;//存取队首元素值boolisEmpty()const{returncount==0;//检测队列是否为空boolisFull()const{returncount==Size;}//检测队列是否为满voidQClear(){front=rear=count=0;}//清空队列}；插入算法ADL描述算法QInsert(A,item)//在队列A中将元素item插入队尾QI1.[队列满？]IFcountsizeTHEN(PRINT“队列已满无法插入”.RETURN.)QI2.[元素插入]A[rear]item.//将新元素插入队尾QI3.[更新]rearMOD(rear1,size).//更新队尾下标countcount1.//更新队列长度▐C++实现templateclassTvoidAQueueT::QInsert(constT&item){QArray[rear]=item;rear=(rear+1)%Size;}删除算法ADL描述算法QDelete(A.item)//删除队列A的队首元素，并将其元素值赋给变量itemQD1.[队列空？]IFcount0THEN(PRINT“队列空无法删除”.RETURN.)QD2.[出队]itemA[front].//将队首元素保存至itemQD3.[更新]frontMOD(front1,size).//更新队首元素下标countcount-1.//更新队列长度▐C++实现templateclassTvoidAQueueT::QDelete(T&item){item=QArray[front];front=(front+1)%Size;}取队首算法ADL描述算法QFront(A.item)//读取队列A的队首元素值，并将其赋给变量itemQF1.[队列空？]IFcount0THEN(PRINT“队列空无法读取”.RETURN.)QF2.[存取]itemA[front].//将队首元素保存至item▐C++实现templateclassTTAQueueT::QFront()const{returnQArray[front];}验证：#includeaqueue.hintmain(){intn,i,x;AQueueints(100);cinn;for(i=1;i=n;i++)s.QInsert(i);for(i=1;i=n;i++){s.QDelete(x);coutxendl;}}0123456a0123456FR(a)创建一个队列FR(b)插入元素a队列运行示意图abc01234560123456FR(c)插入元素b、cFR(d)取出元素a、b、chidefg0123456hijdefg0123456RF(e)插入元素d、e、f、g、h、iFR(f)插入元素j3.队列的链接存储templateclassTclassNode{Tdata;Node*next;};ana1a2∧frontrear…链队LQueue的类定义templateclassTclassLQueue{private:NodeT*front,*rear;//指向队首和队尾的指针public:LQueue(void){front=rear=NULL;}//构造函数~LQueue(void){QClear();}//析构函数voidQInsert(constT&item);//向队尾插入元素itemvoidQDelete(T&item);//删除队首元素并将该元素值保存至itemTQFront()const;//存取队首元素值boolisEmpty()const{returnfront==0;};//检测队列是否为空voidQClear();//清空队列}；插入算法ADL描述算法QInsert(item)//将元素item插入队尾QI1.[创建新结点]sAVAIL.data(s)item.next(s)NULL.//为新结点申请空间，令其字段值为item，指针域为空QI2.[队空？]IFfrontNULLTHENfronts.//若队列为空，令队首指针指向sELSEnext(rear)s.//若队列非空，令表尾结点的next指针指向sQI3.[更新队尾指针]rears.//更新表尾指针▐C++实现voidLQueueT::QInsert(constT&item){NodeT*p=newNodeT;p.data=item;p.next=0;if(rear){rear-next=p;rear=p;}else{front=rear=p;}}删除算法ADL描述算法QDelete(item)//删除队首结点并将其字段值存于itemQD1.[队列空？]IFfrontNULLTHEN(PRINT“队列为空”.RETURN.)QD2.[出队]qfront.itemdata(q).//令指针q指向队首，并保存其字段值frontnext(front).//令队首指针指向原队首结点之后继结点AVAILq.//释放原队首结点的存储空间QD3.[出队后队列空？]IFfrontNULLTHENrearNULL.//若删除队首结点后队列为空，则令队尾指针修为空▐C++实现templateclassTvoidLQueueT::QDelete(T&item){NodeT*p;if(front){item=front-data;p=front;front=front-next;deletep;if(front==0)rear=0;}}取队首算法ADL描述算法QFront(item)//读取队首元素值，并将其赋给变量itemQF1.[队列空？]IFfrontNULLTHEN(PRINT“队列空无法读取”.RETURN.)QF2.[存取]itemdata(front).//将队首元素保存至item▐C++实现templateclassTTLQueueT::QFront()const{if(front)returnfront-data;}验证：#include“lqueue.hintmain(){intn,i,x;LQueueints;cinn;for(i=1;i=n;i++)s.QInsert(i);for(i=1;i=n;i++){s.QDelete(x);coutxendl;}}顺序队列与链式队列的比较在空间复杂性上，顺序队列必须初始就申请固定的空间，当队列不满时，必然造成空间的浪费；链式队列所需空间是根据需要随时申请的，其代价是为每个元素提供空间以存储其next指针域。在时间复杂性上，对于队列的基本操作（入队、出队和存取），顺序队列和链式队列的时间复杂性均为O(1).STL中关于栈的实现#includequeuequeueints;//不用声明大小s.push(x);s.front();//取队首s.pop();//只弹出队首，与front合用课后练习poj.org注册数据较大时，使用scanf和printfpoj1363railspoj3250BadHairDay