资源描述：
《数据结构第6课队列ppt课件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、队列数据结构之三1队列的基本概念队列(Queue)：也是运算受限的线性表。只允许在表的一端进行插入，而在另一端进行删除。队首(front)：允许进行删除的一端称为队首。队尾(rear)：允许进行插入的一端称为队尾。例如：排队购物，先进入队列的成员总是先离开队列。6.1队列基本概念先进先出a1,a2,…,an出队入队队尾队首6.2队列的顺序表示和实现利用一维数组依次存放从队首到队尾的各个元素，称为顺序队列。其类型定义如下：#defineMAX100structqueue{intqueue_a[MAX];intfront;intrear;};6.2
2、队列的顺序存储结构设立一个队首指针front，一个队尾指针rear。◆初始化：front=rear=0。◆入队：将新元素插入rear所指的位置，然后rear加1◆出队：返回被删元素，然后删去front所指的元素，front加1。◆队列为空：front=rear。◆队满：rear=MAX或front=rear。(a)空队列Q.frontQ.rear入队3个元素a3a2a1Q.frontQ.rear(c)出队3个元素Q.frontQ.rear(d)入队2个元素a5a4Q.frontQ.rear图3-6队列示意图顺序队列中存在“假溢出”现象。因为在入
3、队和出队操作中，头、尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。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)。在循环队列中进行出队、入队操作时，
4、队首、队尾指针仍要加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,
5、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循环队列循环队列为空
6、：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)/*将数
7、据元素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.f
8、ront=(q.front+1)%MAX;//队首指针向前移动returnOK;}循环队列的基本操作1队列的链式存储表示队列的链式存储结构简称为链队列
