数据结构第6课队列.

队列数据结构之三1队列的基本概念•队列(Queue)：也是运算受限的线性表。•只允许在表的一端进行插入，而在另一端进行删除。队首(front)：允许进行删除的一端称为队首。队尾(rear)：允许进行插入的一端称为队尾。例如：排队购物，先进入队列的成员总是先离开队列。6.1队列基本概念a1,a2,…,an出队入队队尾队首6.2队列的顺序表示和实现利用一维数组依次存放从队首到队尾的各个元素，称为顺序队列。其类型定义如下：#defineMAX100structqueue{intqueue_a[MAX];intfront;intrear;};6.2队列的顺序存储结构设立一个队首指针front，一个队尾指针rear。◆初始化：front=rear=0。◆入队：将新元素插入rear所指的位置，然后rear加1◆出队：返回被删元素，然后删去front所指的元素，front加1。◆队列为空：front=rear。◆队满：rear=MAX或front=rear。(a)空队列Q.frontQ.rear(b)入队3个元素a3a2a1Q.frontQ.rear(c)出队3个元素Q.frontQ.rear(d)入队2个元素a5a4Q.frontQ.rear图3-6队列示意图顺序队列中存在“假溢出”现象。因为在入队和出队操作中，头、尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。6.2队列的顺序存储结构设q[0,6]是一个静态顺序队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。a,b,c,d入队a,b,c出队i,j,k,l,m入队d,i出队n,o,p,q,r入队习题一6.3循环队列为充分利用向量空间，克服上述“假溢出”现象的方法是：将为队列分配的空间看成为一个首尾相接的圆环，并称这种队列为循环队列(CircularQueue)。在循环队列中进行出队、入队操作时，队首、队尾指针仍要加1，朝前移动。只不过当队首、队尾指针指向上界(MAX-1)时，其加1操作的结果是指向下界0。这种加1操作可以描述为：if(i+1==MAX)i=0;elsei++;//其中：i代表队首指针(front)或队尾指针(rear)用取余运算可简化为：i=(i+1)%MAX;例：设有循环队列qu[0，5]，其初始状态是front=rear=0，各种操作后队列的头、尾指针的状态变化情况如下图所示。6.3循环队列123450(a)空队列frontrear123450(b)d,e,b,g入队frontdebgrear123450(c)d,e出队bgfrontrear123450(d)i,j,k入队bgfrontijkrear123450(e)b,g出队ijkrearfront123450(f)r,p,s,t入队ijkfrontrprear循环队列操作及指针变化情况6.3循环队列入队时尾指针向前追赶头指针出队时头指针向前追赶尾指针故队空和队满时头尾指针均相等。因此，无法通过front=rear来判断队列“空”还是“满”。解决的方法是：约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满。即：rear所指的单元始终为空（浪费一个空间）。6.3循环队列循环队列为空：front=rear循环队列满：(rear+1)%MAX=front假设q[0,5]是一个循环队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。d,e,b,g,h入队d,e出队i,j,k,l,m入队b出队n,o,p,q,r入队习题二循环队列的基本操作1循环队列的初始化queueinit_CirQueue(void){queueq;q.front=q.rear=0;return(q);}2入队操作intinsert_CirQueue(queueq,inte)/*将数据元素e插入到循环队列Q的队尾*/{if((q.rear+1)%MAX==q.front)returnERROR;/*队满，返回错误标志*/q.qa[q.rear]=e;//元素e入队q.rear=(q.rear+1)%MAX;//队尾指针向前移动returnOK;/*入队成功*/}循环队列的基本操作3出队操作intdelete_CirQueue(queueq,int*x)//将循环队列Q的队首元素出队{if(q.front+1==q.rear)returnERROR;//队空，返回错误标志*x=q.qa[q.front];//取队首元素q.front=(q.front+1)%MAX;//队首指针向前移动returnOK;}循环队列的基本操作1队列的链式存储表示队列的链式存储结构简称为链队列。需要两类不同的结点：数据元素结点，队列的队首指针和队尾指针的结点。6.4队列的链式表示和实现数据元素结点定义：structqnode{intdata;qnode*next;};数据元素结点data指针结点frontrear指针结点类型定义：structlink_queue{qnode*front,*rear;};2链队运算及指针变化链队的操作实际上是单链表的操作，只不过是删除在表头进行，插入在表尾进行。链队运算及指针变化如图3-9所示。(a)空队列frontrear∧(b)x入队x∧frontrear队列操作及指针变化(c)y再入队y∧frontrearx(d)x出队y∧xfrontrear3链队列的基本操作⑴链队列的初始化link_queue*init_linkqueue(void){link_queue*q;qnode*p;p=newqnode;/*开辟头结点*/p-next=NULL;q=newlink_queue;/*开辟链队的指针结点*/q.front=q.rear=p;return(q);}⑵链队列的入队操作在已知队列的队尾插入一个元素e，即修改队尾指针(q.rear)。intinsert_CirQueue(link_queue*q,inte)/*将数据元素e插入到链队列q的队尾*/{p=newqnode;if(!p)returnERROR;/*申请新结点失败，返回错误标志*/p-data=e;p-next=NULL;/*形成新结点*/q.rear-next=p;q.rear=p;/*新结点插入到队尾*/returnOK;}⑶链队列的出队操作intdelete_queue(link_queue*q,int*x){qnode*p;if(q.front==q.rear)returnERROR;/*队空*/p=q.front-next;/*取队首结点*/*x=p-data;q.front-next=p-next;/*修改队首指针*/if(p==q.rear)q.rear=q.front;/*当队列只有一个结点时应防止丢失队尾指针*/deletep;returnOK;}⑷链队列的撤消voiddestroy_linkqueue(link_queue*q)/*将链队列Q的队首元素出队*/{while(q.front!=NULL){q.rear=q.front-next;/*令尾指针指向队列的第一个结点*/deleteq.front;/*每次释放一个结点*//*第一次是头结点，以后是元素结点*/q.front=q.rear;}}在现实生活中Queue的应用很广泛。1、播放器上的播放列表2、数据流对象，异步的数据传输结构(文件IO，管道通讯，套接字等)3、还有一些解决对共享资源的冲突访问，比如打印机的打印队列等。消息队列等。交通状况模拟，呼叫中心用户等待的时间的模拟等等。可以肯定地说：任何与时间相关的操作，基本上都会牵扯到队列。队列的应用举例•队列的基本用途•保存暂时不用的数据或存储地址•可简化程序设计例.用队列进行迷宫求解用队列进行迷宫求解的基本思想是：从迷宫的入口[1][1]出发，向四周搜索，记下所有一步能到达的坐标点；然后依次从每一点出发，向四周搜索，记下所有从入口点出发，经过两步可以到达的坐标点……依次进行下去，一直到达迷宫的出口处[4][4]。然后从出口处沿搜索路径回溯直到入口点，这样就找到了从入口到出口的一条最短路径。01100000101011100110000010101010474101-11115492548354744262335332432122112序号行列前驱由于先到达的点要先向下搜索，故引进一个“先进先出”数据结构——队列来保存已到达的点的坐标。到达迷宫的出口点(4,4)后，为了能够从出口点沿搜索路径回溯直至入口，对于每一点，在记下点的坐标的同时，还要记下到达该点的前驱点。【例】汽车加油站随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。通常汽车加油站的结构基本上是：入口和出口为单行道，加油车道可能有若干条。每辆车加油都要经过三段路程，第一段是在入口处排队等候进入加油车道；第二段是在加油车道排队等候加油；第三段是进入出口处排队等候离开。实际上，这三段都是队列结构。若用算法模拟这个过程，就需要设置加油车道数加2个队列。队列的应用【例】模拟打印机缓冲区在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。【例】CPU分时系统在一个带有多个终端的计算机系统中，同时有多个用户需要使用CPU运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把CPU分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将CPU分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使CPU正常工作。【例】打印杨辉三角形11i=112121331314641415101051516152015616杨辉三角形元素入队顺序161520156115101051146411331121111161520156115101051146411331121111000000011FR0110121FR011FR0110FR01101FR011012FR0110121FR