数据结构第3章

第3章栈和队列BasicSortingAlgorithms3.1栈（Stack）

第三章栈和队列3.2队列（Queue）1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式3.2队列1.定义与同线性表相同，仍为一对一关系。顺序队或链队，以循环顺序队更常见。只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。3.存储结构4.运算规则5.实现方式2.逻辑结构只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表（头删尾插）基本操作有入队或出队，建空队列，判队空或队满等操作。队列（Queue）是仅在表尾进行插入操作，在表头进行删除操作的线性表。表尾即an端，称为队尾

；表头即a1端，称为队头。它是一种先进先出（ＦＩＦＯ）的线性表。例如：队列Q=(a1,a2,a3,……….,an-1,an)插入元素称为入队；删除元素称为出队。队头队尾教材P89对队列有更详细定义：队列的抽象数据类型定义见教材Ｐ89队列的存储结构为链队或顺序队

（常用循环顺序队）53.2.2队列的顺序存储结构及其基本运算的实现非循环队列的基本运算循环队列的基本运算顺序队列的表示和实现6可以采用顺序存储结构存储一个队列，其中使用一个数组data和两个整数型变量。数组data顺序存储队列中所有元素，两个整型变量front和rear分别作为队首指针和队尾指针。顺序队列类SqQueueClass的定义如下（本小节的所有算法均包含在此类中）：classSqStackClass{constintMaxSize=100;//最多元素个数publicstring[]data;//存放队中的元素publicintfront,rear;//队头和队尾指针publicSqStackClass()//构造函数，用于初始化队列{data=newstring[MaxSize];front=rear=x;//通常情况下，循环队列x为0，非循环队列x为-1}//顺序队的基本运算};7非循环队列，初始化时置front=rear=-1队空的条件为front==rearrear==Maxsize-1入队：元素e进队的操作是先将队尾指针rear增1，然后将e放在队尾处出队：出队操作是先将队头指针front增1，然后取出队头处的元素（1）非循环队列的基本运算8若队列满足front==rear条件，则返回true；否则返回false。对应算法如下：publicboolQueueEmpty(){return(front==rear);}1)判断队列是否为空QueueEmpty()9元素进队只能从队尾进，不能从队头或中间位置进队。在进队运算中，在队列不满的条件下，先将队尾指针rear增1，然后元素e放到该位置处。对应算法如下：publicboolPush(stringx){if(rear==MaxSize-1)//队满上溢出，返回falsereturnfalse;rear++;//队尾指针增1data[rear]=x;returntrue;}2)进队运算enQueue(e)10元素出队只能从队头出，不能从队头或中间位置出队。在出队运算中，在队列不为空的条件下，将队首指针front增1，并将该位置的元素值赋给e。对应算法如下：publicbooldeQueue(refstringe){if(front==rear)//队空下溢出时，返回falsereturnfalse;front++;e=data[front];returntrue;}3)出队列deQueue(e)3.2队列1.存在问题设数组维数为M，则：当front=-1,rear=M时，再有元素入队发生溢出

——真溢出当front-1,rear=M时，再有元素入队发生溢出

——假溢出问：什么叫“假溢出”？如何解决？答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。2.解决方案循环队列基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;实现：利用“模”运算入队：sq[rear]=x;

rear=(rear+1)%M;出队：front=(front+1)%M;x=sq[front];

0M-11frontrear…...…...假溢出a3a2a10123M-1rearfront循环队列（臆造）顺序队列a3a2a1frontrear0123..N-1循环队列新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！解决方案有三：①加设标志位，让删除动作使其为1,插入动作使其为0,则可识别当前front=rear②使用一个计数器记录队列中元素个数(即队列长度)③人为浪费一个单元，令队满特征为

front=(rear+1)%M；循环队列012345rearfrontJ4J5J6123405J9J8J7rearfrontJ4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：front==rear队满：front==rear解决方案：少用一个元素空间：队空：front==rear队满：(rear+1)%M==front队空条件

:front=rear(初始化时：front=rear)队满条件：

front=(rear+1)%M(M=maxsize)队列长度（即数据元素个数）：L=（M＋rear－front）%M

选用空闲单元法：即front和rear之一指向实元素，另一指向空闲元素

问3：在具有n个单元的循环队列中，队满时共有多少个元素？n-1个6

问1:左图中队列maxsizeM=？J2J3 J1J4

J5frontrear问2：左图中队列长度L=？5方案三:17若队列满足front==rear条件，则返回true；否则返回false。对应算法如下：publicboolQueueEmpty(){return(front==rear);}1)判断队列是否为空QueueEmpty(q)18在进队运算中，在队列不满的条件下，先将队尾指针rear循环增1，然后元素e放到该位置处。对应算法如下：publicboolenQueue(stringe){if((rear+1)%MaxSize==front)//队满上溢出returnfalse;rear=(rear+1)&MaxSize;//队尾指针增1data[rear]=x;returntrue;}2)进队运算enQueue(q,e)19在出队运算中，在队列不为空的条件下，将队首指针front循环增1，并将该位置的元素值赋给e。对应算法如下：publicbooldeQueue(refstringe){if(front==rear)//队空下溢出时，返回falsereturnfalse;front=(front+1)%MaxSize;e=data[front];returntrue;}3)出队列deQueue(q,e)例【3.7】对于循环队列来说，如果知道队头指针和队尾指针中的元素个数，则可以计算出队尾指针。也就是说，可以用队列中的元素个数代替队尾指针。设计出循环队列的进队、出队、判队空和求队中元素个数的算法。20解：本例的循环队列包含data数组、队头指针rear和队中的元素个数count字段。初始时front和count均置为0。队空的条件为count==0；队满的条件为count==MaxSize；元素e进队操作是，先根据队头指针和元素个数求出队尾指针rear，将rear循环增1，然后将元素e放置在rear处；出队操作是，先将队首指针循环增1，然后取出该位置的元素。设计对应的循环队列类SqQueueClass2如下：21ClassSqQueueClass2{constintMaxSize=5;privatestring[]data;//存放队中的元素privateintfront;//队头指针privateintcount;//队列中的元素个数publicSqQueueClass2(){data=newstring[MaxSize]；//构造函数，用于队列初始化front=0;count=0;}//顺序队基本运算算法22publicboolQueueEmpty()//判断队列是否为空{return(count==0);}publicboolenQueue(stringe)//进队算法{intrear;rear=(front+count)%MaxSize;if(count==MaxSize)returnfalse;rear=(rear+1)%MaxSize;data[rear]=e;count++;returntrue;}23publicintGetCount()//求队列中的元素个数{returncount;}publicbooldeQueue(refstringe)//出队算法{if(count==0)returnfalse;front=(front+1)%MaxSize;e=data[front];count--;returntrue;}}243.2.3队列的链式存储结构及其基本运算的实现链队列的表示实现链队列的基本运算链队列示意图讨论：空队列的特征？Q(队尾)(队首)fronta1a2a3^rearpfront^rear③怎样实现入队和出队操作？入队（尾部插入）：rear.next=S;rear=S;出队（头部删除）：front.next=p.next;②队列会满吗？front=rear一般不会，因为删除时有free动作。除非内存不足！（1）链队列的表示和实现26队列的链式存储结构也是通过由结点构成的单链表实现的，此时只允许在单链表的表首进行删除操作和在单链表表尾进行插入操作。因此需要使用两个指针：队首指针front和队尾指针rear。用front指向队首结点，用rear指向队尾结点。用于存储队列的单链表称为链队。链队数据结点类LinkNode的定义如下：classLinkNode//链队数据结点类{publicstringdata;//结点数据字段publicLinkNodenext;//指向下一个结点

};27链队结点类LinkQueue的定义如下：classLinkQueue//链队结点类{publicLinkQueuefront;//指向队头结点publicLinkQueuerear;//指向队尾结点

};链队类LinkQueueClass的定义如下：classLinkQueueClass//链队结点{LinkQueueQ=newLinkQueue();publicLinkQueueClass()//构造函数，用于初始化{Q.front=null;Q.rear=null;}//链队的基本运算算法};28若队列满足rear==null条件，则返回true；否则返回false。对应算法如下：publicboolQueueEmpty(){return(rear==null);}1)判断队列是否为空QueueEmpty(q)29创建data域为e的数据结点p。若原队列为空，则将链队结点的两个域均指向p结点，否则，将p结点链到单链表的末尾，并让链队结点的rear域指向它。对应算法如下：publicboolenQueue(stringe){LinkNodep=newLinkNode();p.data=e;p.next=null;if(Q.rear==null)//若链队为空，则新结点是队首结点，又是队尾结点Q.front=Q.rear=p;else{Q.rear.next=p;//将p结点链到队尾，并将rear指向它Q.rear=p;}}2)进队运算enQueue(e)30若原队列不为空，则将第一个数据结点的data域值赋给e,并删除它。若出队前队列只有一个结点，则需将链队结点的两个域均置为null，表示队列已为空。对应算法如下：publicbooldeQueue(refstringe){LinkNodep;if(Q.rear==null)//队列为空returnfalse;p=Q.front;if(Q.front==Q.rear)//p指向第一个数据结点Q.front=Q.rear=null;//队列中只有一个结点时elseQ.front=Q.front.next;//队列中有多个结点时e=p.data;p=null;returntrue;}3)出队列deQueue(e)例【3.8】采用一个不带头结点，只有一个尾结点指针rear的循环单链表存储队列，设计出这种链队的进队、出队、判队空和求队中元素个数的算法。31解：用只有尾结点指针rear的循环单链表作为队列存储结构，其中每个结点的类型为LinkNode。当这样的链队列中没有结点时，队列为空，即rear==null；进队在链表的表尾进行，出队在链表的表头进行。这样的链队类LinkQueueClass2的定义如下：ClassLinkQueueClass2{LinkNoderear;//链队队尾指针publicLinkQueueClass2()//构造函数，用于初始化{rear=null;}publicboolQueueEmpty()//判队空运算算法{return(rear==null);}32publicvoidenQueue(stringe)//进队运算算法{L