05.队列

队列队列的概念•排队只能排在尾部,排在对头的先得到服务;•“插队”是不允许的.换言之,插入和删除只能在线性表的两头分别进行;•插入的一端称为队尾,删除的一端称为队头;•其特点是:先进先出(FIFO)队列(Queues)是生活中“排队”的抽象队列队列的基本概念队列定义存储结构运算规则实现方式逻辑结构只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表。队尾插入队头删除与线性表相同，仍为一对一关系。顺序队列或链队列，以循环顺序队列更常见。只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。基本操作：入队或出队，建空队列，判队空或队满等操作。队列的定义队列（queue）是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)——允许插入的一端队头(front)——允许删除的一端在队尾进行的插入操作称为入队在队头进行的删除操作称为出队队列的特点：先进先出a1a2a3…………………….an入队出队frontrear队列Q=(a1,a2,……,an)队列的抽象数据类型ADTQueue数据元素集合：具有相同性质数据元素的一个有限序列，且只能在称为队尾的一端进行插入操作和在队头的一端进行删除操作。基本操作：初始化队列(InitQueue)求队列长度(QueueLength)入队(EnQueue)：在队尾插入新的数据元素出队(DeQueue)：删除队头的数据元素判队空(QueueEmpty)操作示例QueueTypeMyQueue;InitQueue(MyQueue);EnQueue(MyQueue,1);//MyQueue中有数据1EnQueue(MyQueue,2);//MyQueue中有数据12EnQueue(MyQueue,3);//MyQueue中有数据123DeQueue(MyQueue);//MyQueue中有数据23DeQueue(MyQueue);//MyQueue中有数据3DeQueue(MyQueue);//MyQueue为空队列的链接存储结构与实现如何用链式结构表示队列？如何存储队列元素怎样表示队列的逻辑结构怎样指示队列的队头和队尾位置pFront43123615空24队链39pRearstructQNode{//结点结构DataTypedata;QNode*next;}*front,*rear;typedefstruct{//队列结构QNode*front;QNode*rear;}LinkQueue;ana1a2^front头结点队头rear队尾将队头指针映射到单链表的表头位置将队尾指针映射到单链表的表尾位置ana1a2^Q.frontQ.rearintInitQueue(LinkQueue&Q){//构造只有一个空头结点的链式队列//头、尾指针均指向头结点Q.front=Q.rear=newQNode;if(Q.front==NULL){cout“出错”;return0;}Q.front-next=NULL;return1;}初始化链队列^Q.frontQ.rearInitQueue(Q)操作步骤：①生成新结点②在尾结点之后插入新结点③更新尾指针入队操作QNode*t=newQNode;②③a3a1a2^Q.frontQ.reart①item^Q.rear=t;Q.rear-next=t;入队操作intEnQueue(LinkQueue&Q,DataTypeitem){//单链表的尾插法QNode*t=newQNode;//①生成新结点if(t==NULL){cout“出错”;return0;}t-data=item;t-next=NULL;Q.rear-next=t;//②在尾结点后插入新结点Q.rear=t;//③更新尾指针return1;}②③a3a1a2^Q.frontQ.reart①item^操作步骤：①判断队列是否为空，若空则产生下溢出错误，退出算法。否则执行第②步。②删除队头结点。③若被删结点是队列的尾结点，则更新队尾指针指向头结点。出队操作a1Q.frontQ.rearif(Q.front==Q.rear)a2^Q.frontQ.rearQ.front-next=t-next;a2^^Q.frontQ.rearQ.rear=Q.front;t出队操作intDeQueue(LinkQueue&Q,DataType&item){//删除单链表的表头元素//①判空if(Q.front==Q.rear){cout“队空”;return0;}QNode*t=Q.front-next;item=t-data;Q.front-next=t-next;//②删除队头结点if(Q.rear==t)//③若删除尾结点须更新尾指针Q.rear=Q.front;deletet;return1;}#defineQueueSize100structSqQueue{//顺序队列的数据类型DataTypeitems[QueueSize];intfront;//队头元素的下标位置intrear;//队尾元素的后继位置};队列的顺序存储结构与实现012345612152436434862数据入队方向数据出队方向队尾数组长度队头frontrear空队列frontrearA,B,C,D进队ABCDfrontrearA,B出队CDfrontrearE,F,G进队CDEFGCDEFGfrontrearH进队,溢出顺序队列的“假溢出”问题当移动到数组中下标最大的位置后，队列的空间就用尽了。此时，即使数组下标较小的位置处还有空闲空间，也不能进行入队操作。rear=0front=-1012空队rear=1front=00a112a1入队rear=3front=0a1a2a3a2、a3入队，队满rear=3front=1a2a3出队1次rear=3front=3出队2次，队空队列上溢：真上溢(rear-front=Max):队列真正满时再入队假上溢：rear已指向队尾，但队列前端仍有空位置解决假上溢的方法：•方法一：非循环队列——每次删除队头一个元素后，把整个队列往前移一个位置（造成时间浪费）•方法二：循环队列非循环队列必须始终追踪队列的两端我们可以把队列的队首放在数组的位置0将元素添加到队列只是意味着增加指示队列队尾的计数器从队列删除元素开销很大，因为元素删除时剩余的元素将沿着数组向上移动。当队列拥有大量数据时，该进程将十分缓慢循环队列把数组的首尾两个存储单元看成位置相邻的单元，即允许队列直接从数组中下标最大的位置前进到下标最小的位置。（设数组长度为Max）0Max-11frontrear循环数组取下一相邻单元下标运算数组第一个单元的下标为0与下标1的单元相邻（0+1）％Max＝1数组最后一个单元的下标为Max－1其下一相邻的单元的下标为0(Max-1+1)％Max＝0任一位置x(0xMax-1)x相邻的单元的下标为x+1(x+1)％Max=x+1下标运算：（X＋1）％Maxfront=5rear=707Q={A,B}front=5rear=007Q={A,B,C}数据入队前数据入队后front=5rear=407Q=A,B,C,D,E,F,Gfront=5rear=507Q=A,B,C,D,E,F,G,HH数据入队前数据入队后队满front=4rear=507Q={H}front=5rear=507Q={}H数据出队后数据出队前队空J4J5J3rearfront初始状态队空：front==rear队满：front==rear解决方案：1.另外设一个标志以区别队空、队满2.设置一个计数器3.少用一个元素空间：队空：front==rear队满：(rear+1)%Max==front012345rearfront012345J4J5J6rearfrontJ3J8J7012345区别循环队列空、满状态设置一个标志位标识前一个操作是入队，还是出队操作。初始标志位tag置为0；执行入队操作后，把标志位置为1；执行出队操作后，把标志位置为0。队空：front==rear&&tag==0队满：front==rear&&tag==1设置一个计数器计数队列中的元素数，同时还能起到标志位的作用。初始计数器count置为0；执行入队操作后，使计数器count增一；执行出队操作后，使计数器count减一。队空：count==0队满：count0&&front==rear少用一个存储单元队空：front==rear队满：(rear+1)%QueueSize==front队列长度：(rear–front+QueueSize)%QueueSize07front=0rear=0队空07front=1rear=0队满循环队列入队操作intEnQueue(SqQueue&Q,DataTypeitem){if((Q.rear+1)%QueueSize==Q.front){cout“队满”;return0;}//①判队满Q.items[Q.rear]=item;//②新元素放尾指针位置Q.rear=(Q.rear+1)%QueueSize;//③尾指针后移return1;}rearfront3210a3a245itemrear循环队列出队操作intDeQueue(SqQueue&Q,DataType&item){if(Q.rear==Q.front){cout“队空”;return0;}//①判队空item=Q.items[Q.front];//②删除队头元素Q.front=(Q.front+1)%QueueSize;//③头指针后移return1;}frontfronta2a43210a345rearitema2循环队列和链队列的比较时间性能:循环队列和链队列的基本操作都需要常数时间O(1)。空间性能:循环队列：必须预先确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题。链队列：没有队列满的问题，只有当内存没有可用空间时才会出现队列满，但是每个元素都需要一个指针域，从而产生了结构性开销。队列