CH5队列的.ppt

第五章 队列;引言：在日常生活中经常会遇到为了维护社会正常秩序而需要排队的情境，在计算机程序设计中也经常出现类似问题。数据结构队列与生活中的排队极为相似，也是按先到先办的原则行事的，并且严格限定：既不允许加塞儿，也不允许中途离队。;举例1：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。 举例2：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。 举例3：在Windows这类多任务的操作系统环境中，每个应用程序响应一系列的“消息”，像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。 ; 一、队列的定义、操作;比较：;2、队列中的基本概念;3、队列中的基本运算; 二、队列的顺序存储;;队头指针：front总是指向当前队头元素的前一个位置。 队尾指针：rear指向当前队尾元素的位置。 初始状态：front=rear= -1 入队运算： rear ++; /*尾指针加1 */ queue[rear]=x; /* x入队 */ 出队运算： front ++; /* 头指针加1 */;5、顺序队列中入队的算法描述;6、顺序队列中出队的算法描述; 三、队列的链式存储;typedef struct node { int data; struct node *next; }JD; typedef JD * Link; Link front=NULL; Link rear=NULL;;3、队列链表的特点--- 插入（进队）只能在表尾的位置上进行，与rear有关； 删除（出队）只能在表头位置上进行，与front有关。;4、队列链表的操作运算;步骤2：判断队尾指针rear是否为空。;②若rear不为NULL.;rear-next=new; rear=new;;“B”;top=front; front=front-next; temp=top-data; free(top);;5、队列链表的入队运算---;6、队列链表的出队运算---; 引言： 在顺序队列中，当队尾指针已经指向了队列的最后一个位置时，此时若有元素入列，就会发生“溢出”。虽然队尾指针已经指向最后一个位置，但事实上队列中还有3个空位置。也就是说，队列的存储空间并没有满，但队列却发生了溢出，我们称这种现象为假溢出。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。解决这个问题有两种可行的方法： ;（1）采用平移元素的方法，当发生假溢出时，就把整个队列的元素平移到存储区的首部，然后再插入新元素。这种方法需移动大量的元素，因而效率是很低的。 （2）将顺序队列的存储区假想为一个环状的空间当发生假溢出时，将新元素插入到第一个位置上，这样做，虽然物理上队尾在队首之前，但逻辑上队首仍然在前。入列和出列仍按“先进先出”的原则进行，这就是循环队列。 很显然，方法二中不需要移动元素，操作效率高，空间的利用率也很高。 ; 1、循环队列定义 为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。; 这种循环意义下的加1操作可以描述为： if(i+1==MAXQSIZE) i=0; else i++; 利用模运算可简化为： i=(i+1)%MAXQSIZE; ;在循环队列中，每插入一个新元素时，就把队尾指针沿顺时针方向移动一个位置。即： q-rear=q-rear+1; if(q-rear= =MAXNUM) q-rear=0; 在循环队列中，每删除一个元素时，就把队头指针沿顺时针方向移动一个位置。即： q-front=q-front+1; if(q-front= =MAXNUM) q-front=0; ;如图所示，为循环队列的三种状态，图3-11（a）为队列空时，有q-front= =q-rear；图3-11（b）为队列满时，也有q-front= =q-rear；因此仅凭q-front= =q-rear不能判定队列是空还是满。 ; ;循环队列的结构定义： typedef struct {Elemtype queue[MAXNUM]; int front; /*队头指示器*/ int rear; /*队尾