数据结构队列.ppt

《数据结构队列.ppt》由会员分享，可在线阅读，更多相关《数据结构队列.ppt（41页珍藏版）》请在第壹文秘上搜索。

1、1第五章第五章 队列队列5.1 何谓队列何谓队列队列数据结构规定：在有序列表中数据的输出、输入是分别由不同端进行处理，输出端称为前端(front)，输入端称为后端(rear)，这样会使得先存入的数据会先被取出，也就是具有先进先出FIFO的特性。2队列的应用也很多，下面列出几个较常见的：1.图形的广度优先搜索法。2.优先队列，此种队列在取出元素时是根据所存元素的某项特性值或优先权而取出具最小或最大数值的元素。3.操作系统中的工作调度，若工作的优先权相同，则采用先到先做的原则。4.用于“spooling” (假脱机，信息暂存,当信息需进一步处理时，对其进行暂时存贮)，先将输出数据写在磁盘上，再由打

2、印机把先存入者先处理的顺序将数据输出。队列和堆栈一样也可使用两种结构：数组结构和链表结构。 3抽象数据类型Queue元素：无限制，由应用决定结构：保持元素先进先出的特性。操作：(1)void Init(Queue &Q)/初始化生成一个空栈(2)void Addqueue(Element e,Queue &Q)/入队操作(3)void Delqueue(Elment &e,Queue &Q)/出队操作(4)Element Top(Queue Q)/读队首元素值(5)bool Empty(Queue Q)/判队列空操作(6)bool Full(Queue Q)/判队列满操作45.2用数组仿真队列

3、用数组仿真队列 队列本身是有序列表，若使用数组的结构来存储队列的结构，则队列结构数组的声明如下:struct queueint queueMaxSize；int front；int rear；其中MaxSize是该队列的最大容量。因为队列的输出、输入分别从前后端来处理，因此需要两个变量front和rear分别记录队列前后端的索引值，front会随着数据输出而变动，而rear则是随着数据输入而改变。 5初始化队列void init(queue &q)q.front=-1;q.rear=-1; 6判断队列空empty函数bool empty(queue q)return(q.front=q.rea

4、r);7判断队列满full函数bool full(queue q)return (q.rear =maxsize-1); 8当我们将数据存入队列时称为“addqueue” ，addqueue的处理主要有两个步骤：(1)将队尾指针往前移：rear+1； (2)若尾指针rear小于等于队列的最大索引值MaxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据。 9入队addqueue函数void addqueue(queue &q,char x)q.rear +;q.data q.rear =x; 10从队列中取出数据项称为“delqueue” ，delqueue的操作可分为4个步

5、骤：(1)检查队列中是否有数据存在。 (2)若头指针front等于尾指针rear，则表示队列中无数据。(3)若头指针front不等于尾指针rear，则将队列头指针往前移front+1。(4)取出队头指针所指的数组元素内容。 11出队delqueue函数void delqueue(queue &q,char &x)q.front +;x=q.data q.front ; 12显示队列数据print函数void print(queue q)int i;for(i=q.front +1;i=q.rear ;i+)coutsetw(4)q.data i;coutdata =x;New-next =NU

6、LL;if(q.rear =NULL)q.front =q.rear =New;elseq.rear -next =New;q.rear =New; 18数据输出是从队列的前端front处理，其步骤如下：步骤1：先保留对头指针front所指的位置步骤2：将头指针front指向下一个节点步骤3：取出之前保留头指针所指的节点内容步骤4：释放原队列前端所指的节点内容 19出队delqueue函数void delqueue(queue &q,char &x)node *p;p=q.front ;q.front =q.front -next ;x=p-data ;delete p; 20显示队列prin

7、t函数void print(queue q)node *p;p=q.front ;while(p!=NULL)coutsetw(4)data ;p=p-next ;coutendl; 215.45.4环状队列环状队列 我们在5.2节中提到，当队尾指针rear等于MaxSize-1时，不论队列是否有空间，都无法再将数据存于队列中。如果要将数据往队列前端移动以挪出空间，需要花费很多时间。为解决这样的问题，我们使用环状队列，控制队列前尾指针front、rear来充分运用队列中的空间。环状队列的概念如下图：图略（P126） 22当插入数据时，尾指针rear会往箭头方向前进，而输出数据时，头指针fron

8、t也会往箭头方向前进，可看出队列空间的利用是按照逆时针方向循环，直到rear往前移动到等于front时，表示队列己满,无法输入数据。从上图看来，虽然环状队列看似一个封闭的圆环，但事实上环状队列仍然是一个线性数组，和一般队列比较起来，主要是前后端使用技巧的差异。在此需特别注意的是，环状队列中的头指针所指的数组位置并没有内容值存在，输出的值为front的下一个元 素 ， 故 环 状 队 列 实 际 上 所 能 使 用 的 空 间 为MaxSize-1。 23当尾指针rear等于MaxSize-1时需回到队列的最前端，故当输入数据时，rear所指的数组元素索引值采用下列的计算方法：(rear+1)m

9、od MaxSize若尾指针rear不断前进直到等于头指针front时，那么表示队列己满，但如果队列为空时rear也等于front，为区分这两种状况，必须使用不同的条件来加以判断。当队列为满：(rear+1)mod MaxSize=front当队列空：front=rear 这两个条件所代表的意义是不一样的。 24初始化环状队列void init(queue &q)q.front=0;q.rear=0; 25判断环状队列空empty函数bool empty(queue q)return(q.front=q.rear);26判断环状队列满full函数bool full(queue q)return

10、 (q.rear+1)%maxsize=q.front ); 27当我们将数据存入队列时称为“addqueue” ，addqueue的处理主要有两个步骤：(1)将队尾指针往前移：rear+1； (2)若尾指针rear小于等于队列的最大索引值MaxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据。 28环状队列入队addqueue函数void addqueue(queue &q,char x)q.rear=(q.rear +1)%maxsize;q.data q.rear =x; 29从队列中取出数据项称为“delqueue” ，delqueue的操作可分为4个步骤：(1)检

11、查队列中是否有数据存在。 (2)若头指针front等于尾指针rear，则表示队列中无数据。(3)若头指针front不等于尾指针rear，则将队列头指针往前移front+1。(4)取出队头指针所指的数组元素内容。 30环状队列出对队delqueue函数void delqueue(queue &q,char &x)q.front=(q.front +1)%maxsize;x=q.data q.front ;31显示环状队列数据print函数void print(queue q)int i;if (q.front q.rear )for(i=q.front +1;i=q.rear ;i+)couts

12、etw(4)q.data i;elsefor(i=q.front+1 ;imaxsize;i+)coutsetw(4)q.data i;for(i=0;i=q.rear ;i+)coutsetw(4)q.data i;coutendl;3255 双向队列双向队列 前面所提到的队列为单向队列，即从队列后端进行输入、前端进行输出。顾名思义，双向队列即可从前后端进行队列数据的输出及输入，如下图所示：这样的结构最常用于计算机的CPU调度。所谓“CPU调度”是在多人使用一个CPU的情况下，由于CPU在同一时间只能执行一项工作，故将每个人欲处理的工作先存于队列中，待CPU闲置时再从队列中取出一项待执行的工

13、作进行处理。而在双向队列两端均可输出、输入的结构下，正好符合在CPU调度处理上的不同请求。双向队列的设计有很多种，在此我们根据输出、输入方向的限制，将其分为两种：1.输入限制性双向队列 2.输出限制性双向队列 335.5.1 输入限制性双向队列输入限制性双向队列 “输入限制性双向队列”是限制只能在队列的一端(后端)进行输入，而数据的输出则可在队列的两端(前后端)操作。程序实例：已知一队列，欲使用“输入限制性双向队列”方式进行数据输出。程序源代码： 34#include #include #define MaxSize 10int queue MaxSize ;int front = -1;in

14、t rear = -1;void addqueue (int value)rear= (rear+1) % MaxSize; if (front=rear)coutThe queue is full! !; elsequeuerear = value;int rear_delqueue () int temp;if (front = rear)return -1;temp=queuerear;rear-;if (rear0 & front!=-1)rear=MaxSize-1;return temp;35int front_delqueue ()if (front = rear)return

15、-1; front+ ; if (front = MaxSize)front =0; return queue front ;void main ( ) int select; int output_queue 5 ;int input_queue5=5,4,3,2,1;int temp,Position=0,i;for (i=0;i5;i+)addqueue (input_queuei);coutThe original queue order :;for (i=0;i5;i+)cout input_queuei; coutendl;36 while (front != rear) cout

16、(1) From Front-endendl;cout(2) From Rear-end endl;cout;cinselect;switch (select)case 1:temp=front_delqueue ( );output_queue Position+ =temp;break;case 2:temp=rear_delqueue() ;output_queuePosition+ =temp;break; coutendlThe output order:; for (i=0;i5;i+)coutoutput_queuei; coutendl;375.5.25.5.2输出限制性双向队列输出限制性双向队列 “输出限制性双向队列”恰好与“输入限制性双向队列”相反，它所限制的是只能在队列的一端(前端)进行输出，而数据的输入则是可以在队列的两端（前后端）操作。所以也会有两种情况：程序实例：已知一队列，欲使用“输出限制性双向队列”方式进行数据输出。程序源代码： 38#include #include struct queue_node int data; struct queue_no