数据结构解说演示课件

第3章 队列,与栈一样，队列也是一种操作受限的线性表。队列在操作系统和事务管理等软件设计中应用广泛，如键盘输入缓冲区问题就是利用队列的思想实现的。 本章重点和难点： 1、队列的顺序表示与实现 2、队列的链式表示与实现,3.1 队列的定义与抽象数据类型,队列只允许在表的一端进行插入操作，在表的另一端进行删除操作。3.1.1 什么是队列 队列（queue）是一种先进先出（first in first out，缩写为FIFO）的线性表，它只允许在表的一端进行插入，另一端删除元素。这与我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端称为队头（front），允许删除的一端称为队尾（rear）。因此又称队列为先进先出（FIFO）表。,3.1 队列的定义与抽象数据类型,假设队列为q=（a1，a2，ai，an），那么a1为队头元素，an为队尾元素。进入队列时，是按照a1，a2，an的顺序进入的，退出队列时也是按照这个顺序退出的。也就是说，当先进入队列的元素都退出之后，后进入队列的元素才能退出。即只有当a1，a2，an-1都退出队列以后，an才能退出队列。,3.1 队列的定义与抽象数据类型,2基本操作集合（1）置空队列InitQueue(Q)：初始化操作，建立一个空队列Q。（2）判队列空QueueEmpty(Q)：若Q为空队列，返回1，否则返回0。（3）入队列EnQueue(Q,x)：若队列不满，插入元素x到队列Q的队尾。（4）出队列DeQueue(Q)：若队列不空，删除队头元素，并返回该元素。（5）取队头Gethead(Q)：若队列不空，返回队头元素。（,3.2 队列的顺序存储及实现,3.2.1 顺序队列的表示 顺序队列通常采用一维数组依次存放从队头到队尾的元素。同时，使用两个指针分别指示数组中存放的第一个元素和最后一个元素的位置。其中，指向第一个元素的指针被称为队头指针front，指向最后一个元素的指针被称为队尾指针rear。 元素a、b、c、d、e、f、g依次进入队列后的状态如图3.2所示。元素a存放在数组下标为0的存储单元中，g存放在下标为6的存储单元中，队头指针front指向第一个元素a，队尾指针rear指向最后一个元素g的下一位置。,3.2 队列的顺序存储及实现,在使用队列前，先初始化队列，此时，队列为空，队头指针front和队尾指针rear都指向队列的第一个位置，即front=rear=0，如图3.3所示。 每一个元素进入队列，队尾指针rear就会增1，若元素a、b、c依次进入空队列，front指向第一个元素，rear指向下标为3的存储单元，如图3.4所示。,3.2 队列的顺序存储及实现,当一个元素出队列时，队头指针front增1，队头元素即a出队后，front向后移动一个位置，指向下一个位置，rear不变，如图3.3所示。,3.2 队列的顺序存储及实现,3.2.2 顺序队列的“假溢出” 在对顺序队列进行插入和删除操作的过程中，可能会出现“假溢出”现象。经过多次插入和删除操作后，实际上队列还有存储空间，但是又无法向队列中插入元素，我们将这种溢出称为“假溢出”。 例如，在图3.2所示的队列中插入3个元素h、i、j，然后删除2个元素a，b之后，就会出现如图3.6所示的情况。当插入元素j后，队尾指针rear将越出数组的下界而造成“假溢出”。,3.2 队列的顺序存储及实现,3.2.3 顺序循环队列的表示 1顺序循环队列 为了充分利用存储空间，消除这种“假溢出”现象，当队尾指针rear和队头指针front到达存储空间的最大值（假定队列的存储空间为QueueSize）的时候，让队尾指针和队头指针转化为0，这样就可以将元素插入到队列还没有利用的存储单元中。例如，在图3.6中，插入元素j之后，rear将变为0，可以继续将元素插入到下标为0的存储单元中。这样就把顺序队列使用的存储空间构造成一个逻辑上首尾相连的循环队列。,3.2 队列的顺序存储及实现,当队尾指针rear达到最大值QueueSize-1时，前提是队列中还有存储空间，若要插入元素，就要把队尾指针rear变为0；当队头指针front达到最大值QueueSize-1时，若要将队头元素出队，要让队头指针front变为0。这可通过取余操作实现队列的首尾相连。例如，假设QueueSize=10，当队尾指针rear=9时，若要将新元素入队，则先令rear=（rear+1）%10=0，然后将元素存入队列的第0号单元，通过取余操作实现了队列的逻辑上的首尾相连。,3.2 队列的顺序存储及实现,2顺序循环队列的队空和队满判断 但是，在顺序循环队列在队空和队满的情况下，队头指针front和队尾指针rear同时都会指向同一个位置，即front=rear，如图3.7所示。即队列为空时，有front=0，rear=0，因此front=rear。队满时也有front=0，rear=0，因此front=rear。,3.2 队列的顺序存储及实现,为了区分这队空还是队满，通常有两个方法：（1）增加一个标志位。设这个标志位为flag，初始时，有flag=0；当入队列成功，则flag=1；出队列成功，有flag=0。则队列为空的判断条件为：front=rear&flag=0，队列满的判断条件为：front=rear&flag=1。（2）少用一个存储单元。队空的判断条件为front=rear，队满的判断条件为front=(rear+1)%QueueSize。那么，入队的操作语句为：rear=（rear+1）%QueueSize，Qrear=x。出队的操作语句为：front=（front+1）%QueueSize。少用一个存储单元的顺序循环队列队满情况如图3.8所示。,3.2 队列的顺序存储及实现,顺序循环队列类型描述如下： #define QueueSize 100/*队列的容量*/ typedef struct DataType dataQueueSize; int front,rear; /*队头指针和队尾指针*/ CirQueue; 其中，data用来存储队列中的元素，front和rear分别表示队头指针和队尾指针。,3.2 队列的顺序存储及实现,3.2.4 顺序循环队列的基本运算 顺序循环队列的基本运算算法实现如下。 （1）置空队列。 void InitQueue(CirQueue *Q) /*顺序循环队列的初始化*/ Q -front=Q -rear=0; ,3.2 队列的顺序存储及实现,（2）判断队列是否为空int QueueEmpty(CirQueue *Q) return Q -front = Q -rear ;(3)判对满int QueueFull(CirQueue *Q) return (Q -rear+1)%QueueSize = Q -front ;,3.2 队列的顺序存储及实现,（4）入队 int EnQueue(CirQueue *Q , DataType x) if(QueueFull(Q) printf(“Queue overflow”); else Q-dataQ-rear=x; Q-rear=(Q-rear+1)%QueueSize; ,3.2 队列的顺序存储及实现,（5）取队头元素 DataType GetFront (CirQueue *Q) if(QueueEmpty(Q) printf(“Queue empty”); exit(0); else return Q-dataQ-front; ,3.2 队列的顺序存储及实现,（6）出队列DataType DeQueue(CirQueue *Q) DataType x; if(QueueEmpty(Q) printf(“Queue empty”); exit(0); else x=Q-dataQ-front; /*将要删除的元素赋值给x*/ Q-front=(Q-front+1)%QueueSize; return x; ,3.2 队列的顺序存储及实现,3.2.3 顺序循环队列举例 P77,3.3 队列的链式存储及实现,采用链式存储的队列被称为链式队列或链队列。3.3.1 链式队列的表示1链式队列 链式队列通常用链表实现。一个链队列显然需要两个分别指示队头和队尾的指针（分别称为队头指针和队尾指针）才能唯一确定。这里，与单链表一样，为了操作上的方便，我们给链队列添加一个头结点，并令队头指针front指向头结点，用队尾指针rear指向最后一个结点。,3.3 队列的链式存储及实现,链式队列的类型描述如下：/*结点类型定义*/typedef struct QNode DataType data; struct QNode * next; QueueNode;/*队列类型定义*/typedef struct QueueNode * front; /队头指针 QueueNode * rear; /队尾指针LinkQueue; /队列类型LinkQueue Q; /定义一链对列Q,3.3 队列的链式存储及实现,一个不带头结点的链式队列和带头结点的链队列分别如图3.12、图3.13所示。,3.3 队列的链式存储及实现,对于带头结点的链式队列，当队列为空时，队头指针front和队尾指针rear都指向头结点。如图3.14所示。 链式队列中，插入和删除操作只需要移动队头指针和队尾指针，这两种操作的指针变化如图3.13、图3.16和图3.17所示。图3.13表示在队列中插入元素a的情况，图3.16表示队列中插入了元素a，b，c之后的情况，图3.17表示元素a出队列的情况。,3.3 队列的链式存储及实现,3.3.2 链式队列的基本运算链式队列的基本运算算法实现如下。（1）初始化队列。void InitQueue(LinkQueue *Q) /*初始化链式队列*/ Q-front=(QueueNode*)malloc(sizeof(QueueNode); Q-rear =Q-front; Q -rear-next=NULL;/*把头结点的指针域置为null*/,3.3 队列的链式存储及实现,（2）判断队列是否为空。int QueueEmpty(LinkQueue *Q) return Q-rear=Q-front; /头尾指针相等队列为空,3.3 队列的链式存储及实现,（3）将元素x入队。先为新结点申请一个空间，然后将x赋给数据域，并使原队尾元素结点的指针域指向新结点，队尾指针指向新结点，从而将结点加入队列中。操作过程如图3.20所示。,将元素x入队的算法实现如下。void EnQueue(LinkQueue *Q, DataType x)/*将元素x插入到链式队列尾部*/ QueueNode *p=(QueueNode*)malloc(sizeof(QueueNode); p-data=x; /将元素值赋值给结点的数据域 p-next=NULL; /将结点的指针域置为空 Q-rear-next=p;/将原来队列的队尾指针指向p Q-rear=p;/将队尾指针指向p,3.3 队列的链式存储及实现,3.3 队列的链式存储及实现,（4）取队头元素。DataType GetFront (LinkQueue *Q) if(QueueEmpty(Q) printf(“Queue underflow”); exit(0); else return Q-front-next-data;,3.3 队列的链式存储及实现,（5）出队列。DataType DeQueue(LinkQueue *Q) QueueNode *p; if(QueueEmpty(Q) /判断链式队列是否为空 return 0; else p=Q-front;/使指针p指向头结点 Q-front=Q-front-next; /头指针指向原队列头结点 free(p); /释放原头结点 return(Q-front-data); /返回原对头结点的数据 ,3.3 队列的链式存储及实现,3.3 队列的链式存储及实现,2链式循环队列 将链式队列的首尾相连就构成了链式循环队列。在链式循环队列中，可以只设置队尾指针，如图3.18所示。当队列为空时，如图3.19所示，队列LQ为空的判断条件为LQ.rear-next=LQ.rear。,3.3.3 链式队列举例 【例3_7】P81,3.3 队列的链式存储及实现,入队列图,出队列图,队列是只允许在表的一端进行插入操作，在另一端进行删除操作的线性表。 队列有两种存储方式：顺序存储和链式存储。采用顺序存储结构的 队列称为顺序队列，采用链式存储结构的队列称为链式队列。 顺序队列存在“假溢出”的问题，顺序队列的“假溢出”不是因为存储空间不足而产生的，为了避免“假溢出”，可用循环队列表示顺序队列。 为了区分循环队列的队空还是队满，有3种方案：设置一个标志位，少用一个存储单元，设置一个计数器。 循环队列P75，例题P80,3.4 小结,1栈 1栈的定义： 栈是限定仅在表的一端进行插入和删除操作的线性表。 我们把插入和删除的一端称为栈顶（TOP），另一端称为栈底（BOTTOM）,不包含任何元素的栈称为空栈。栈又称为后进先出（Last in first out）的线性表，简称LIFO结构。 2栈的存储结构 由于栈也是线性表，因此线性表的存储结构对栈也使用，通常有顺序栈和链栈两种存储结构，这两种存储结构的不同，即使得实现栈的基本运算的算法也有所不同。 （1）顺序存储结构 其实栈的顺序存储还是挺方便的，因为他只准栈顶进出元素，所以不存在线性表插入和删除时需要移动元素的问题。不过它有一个很大,3.4 小结,的缺陷，就是必须事先确定数组存储空间大小，不够用了，就需要编程手段来扩展数组的容量，非常麻烦， （2）链式存储结构 如果栈的使用过程中元素变化不可预测，有时很小，有时非常大，那么最好是用链栈【存储空间不固定可伸缩】。2 队列 1队列的定义 队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列是一种先进先出(first in first out)的线性表，简称FIFO。允许插入的一端称为队尾（rear），允许删除的一端称为队头(Front)。 队列是一种运算受限的线性表，它的运算限制与栈不同，是两头都有,3.4 小结,限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)。 2队列的存储结构 队列也是线性表，所以有两种存储方式，顺序存储和链式存储。 （1）顺序存储结构（顺序队列） 缺点，存储空间不够用的时候需要开发人员通过编程手段来扩展数组容量。 衍生循环队列：头尾相接的顺序存储结构成为循环队列。 （2）链式存储结构（链队） 队列的链式存储结构，其实也就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。,3.4 小结,总结： 栈（stack）是限定在表的一端进行插入和删除操作的线性表。 队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。它们均可使用线性表的顺序存储结构来实现，但都存在着顺序存储的一些弊端（空间不够用）。因此它们各自有各级的技巧来解决这个问题， 对于栈来说，如果是两个相同数据类型的栈，则可以用数组的两端作为栈底的方法来让两个栈共享数据，这就可以最大化地利用数组的空间。 对于队列来说，为了避免数组插入和删除时需要移动数据，于是就引入了循环队列，使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗。 他们也都可以通过链式存储结构来实现，实现原则上与线性表基本相同。,3.4 小结,例如，一个算术表达式为 9 - (2+4*7)/5+3# 这种算术表达式中的运算符总是出现在两个操作数之间，这种算术表达式被称为中缀表达式。计算机编译系统在计算一个算术表达式之前，要将中缀表达式转换为后缀表达式，然后对后缀表达式进行计算。后缀表达式就是算术运算符出现在操作数之后，并且不含括号。 计算机在求算术表达式的值时分为两个步骤： （1）将中缀表达式转换为后缀表达式； （2）依据后缀表达式计算表达式的值。,3.5 栈和队列的典型应用,1将中缀表达式转换为后缀表达式 要将一个算术表达式的中缀形式转化为相应的后缀形式，首先了解下算术四则运算的规则。算术四则运算的规则是： （1）先乘除，后加减； （3）同级别的运算从左到右进行计算； （2）先括号内，后括号外。 上面的算术表达式转换为后缀表达式为： 9247 *+5/-3 +,3.5 栈和队列的典型应用,转换后的后缀表达式具有以下两个特点： （1）后缀表达式与中缀表达式的操作数出现顺序相同，只是运算符先后顺序改变了； （2）后缀表达式不出现括号。 正因为后缀表达式的以上特点，所以编译系统不必考虑运算符的优先关系。仅需要从左到右依次扫描后缀表达式的各个字符，遇到运算符时，直接对运算符前面的两个操作数进行运算即可。,3.5 栈和队列的典型应用,如何将中缀表达式转换为后缀表达式呢？ 我们约定#作为后缀表达式的结束标志。则中缀表达式转换为后缀表达式的算法描述如下： （1）初始化栈，并将#入栈； （2）当读到数字时，直接将其入队列 ，并读入下一字符； （3）当读到运算符时，将栈中所有优先级高于或等于该运算符的运算符弹出，并入队列，再将当前运算符入栈； （4）当读入左括号时，即入栈； （5）当读入右括号时，将靠近栈顶的第一个左括号上面的运算符全部依次弹出， 送至队列中，在删除栈中的左括号。,3.5 栈和队列的典型应用,运算符的优先关系如表3.1所示。 表3.1 运算符的优先关系,3.5 栈和队列的典型应用,初始化一个空栈，用来对运算符进行出栈和入栈操作。中缀表达式9 - (2+4*7)/5+3#转换为后缀表达式的具体过程如图P84所示（为了便于描述，在要转换表达式的末尾加一个#作为结束标记）。,3.5 栈和队列的典型应用,2求后缀表达式的值 将中缀表达式转换为后缀表达式后，就可以计算利用后缀表达式的值了。计算后缀表达式的值的规则如下：依次读入后缀表达式中的每个字符，如果是操作数，则将操作数进入栈；如果是运算符，则将处于栈顶的两个操作数出栈，然后利用当前运算符进行运算，将运行结果入栈，直到整个表达式处理完毕。 利用上述规则，后缀表达式的9247 *+5/-3 +的值的运算过程如图P85所示。,3.5 栈和队列的典型应用,