第3章栈和队列

2,第3章栈和队列,学习目标与要求：熟练掌握栈的顺序存储表示和基本操作的实现。熟练掌握栈的链式存储表示和基本操作的实现。能够利用栈设计算法解决简单的应用问题。熟练掌握队列的顺序存储表示和基本操作的实现。熟练掌握队列的链式存储表示和基本操作的实现。能够利用队列设计算法解决简单的应用问题。,3,3.1栈,3.1.1栈的引例把餐馆中洗净的一叠盘子看作一个栈。通常情况下，最先洗净的盘子总是放在最下面，后洗净的盘子放在先洗净的盘子上面，最后洗净的盘子总是放在最上面；使用时，总是先从顶上取走，也就是说，后洗净的盘子先取走，先洗净的盘子后取走，即所谓的“先进后出”。栈的应用非常广泛，对高级语言中表达式的处理就是通过栈来实现的。,4,3.1.2栈的定义及基本操作,栈(Stack)是限定只能在表的一端进行插入和删除操作的线性表。当栈中无数据元素时，称为空栈。根据栈的定义可知，后入栈的元素先于先入栈的元素出栈，因此栈被称为是一种后进先出的线性表，简称LIFO(LastInFirstOut)表。图3.1表示了栈的这种特点。,5,3.1.2栈的定义及基本操作,栈的基本操作如下。(1)Init_Stack(s)：初始化操作。构造一个空栈。(2)Stack_Empty(s)：判栈空操作。若栈s为空栈，函数返回值为1；否则，返回值为0。(3)Push_Stack(s,x)：入栈操作。在栈s的顶部插入一个新元素x。(4)Gettop_Stack(s)：读栈顶元素操作。若栈非空，函数返回栈顶元素；若栈空，函数返回值为0。(5)Pop_Stack(s)：出栈操作。删除栈s的顶部元素，并返回栈顶元素；若栈空，函数返回值为0。(6)Clear_Stack(s)：栈置空操作。将栈s置为空栈。(7)StackLength(s)：求栈的长度操作。返回栈s中的元素个数。,6,3.1.3栈的顺序存储表示和操作的实现,用C语言描述顺序栈的数据类型如下：#definedatatypechar#defineMAXSIZE100typedefstructdatatypedataMAXSIZE;inttop;SEQSTACK;定义一个指向顺序栈的指针：SEQSTACK*s;,7,3.1.3栈的顺序存储表示和操作的实现,在上述存储结构上基本操作的实现如下。1.初始化空栈2.判栈空操作3.入栈操作4.取栈顶元素操作5.出栈操作6.置空操作7.测栈的长度,8,3.1.3栈的顺序存储表示和操作的实现,对于栈的顺序存储结构的两点说明如下：(1)对于顺序栈，入栈时，首先判断栈是否满，栈满的条件为：s-top=MAXSIZE-1，栈满时不能入栈，否则出现空间溢出，引起错误，这种现象称为上溢。(2)出栈和读栈顶元素操作时，要先判断栈是否为空，为空时不能操作，否则产生错误(或称为下溢)。通常栈空常作为一种控制转移的条件。,9,3.1.4栈的链式存储表示和操作的实现,用C语言描述链栈的数据类型如下：typedefstructStacknodedatatypedata;structStacknode*next;LINKSTACK;定义一个栈顶指针：LINKSTACK*top;,10,3.1.4栈的链式存储表示和操作的实现,链栈的基本操作实现如下。1.初始化空栈2.判栈空操作3.入栈操作4.取栈顶元素操作5.出栈操作,11,3.1.4栈的链式存储表示和操作的实现,下面给出调用链栈上述基本操作的主函数。main()LINKSTACK*top;charch;Init_Stack(,12,3.2栈的应用,【例3.1】将一个非负十进制整数转换成八进制数，使用非递归算法实现。参见教材P53【例3.2】实现简单算术表达式的求值问题，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，例如，若要计算“3+5”则输入35+；乘方运算符用“”表示；每次运算在上一次运算结果的基础上进行。参见教材P54,13,3.3队列,3.3.1队列的引例和栈一样，队列也是一种特殊的线性表。这里我们来看一个简单的事件排队问题，用户可以输入和保存一系列事件，每个新事件只能在队尾插入；每次先处理队头事件，即先输入和保存的事件，当队头事件处理完毕后，它就会从事件队列中被删除；还可以查询事件队列中剩余的事件。,14,3.3.2队列的定义及基本操作,队列(Queue)是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。在表中，允许插入的一端称作“队列尾(tail)”，允许删除的另一端称作“队列头(front)”。向队尾添加元素称为“入队”，删除队头元素称为“出队”。图3.4表示了队列的这种特点。,15,3.3.2队列的定义及基本操作,队列的基本操作如下。(1)Init_Queue(q)：队列初始化操作。构造一个空队列。(2)Queue_Empty(q)：判队空操作。若队列q为空队列，函数返回值为1；否则返回值为0。(3)Add_Queue(q，x)：入队列操作。在队列q的尾部插入一个新元素x。(4)Gethead_Queue(q)：读队头元素操作。若队列不空，返回队头元素；若队列空，函数返回值为0。(5)Del_Queue(q)：出队列操作。若队列不空，删除队头元素，并返回该队头元素；若队列空，函数返回值为0。(6)Clear_Queue(q)：队列置空操作。将队列q置为空队列。(7)QueueLength(q)：求队列的长度操作。返回队列q中的元素个数。,16,3.3.3队列的顺序存储表示和操作的实现,队列是一种特殊的线性表，因此队列可采用顺序存储结构存储，也可以使用链式存储结构存储。利用一组地址连续的存储单元依次存放队列中的数据元素，这种形式的队列称为顺序队列。用C语言描述顺序队列的数据类型如下：#definedatatypechar#defineMAXSIZE100/*队列的最大容量*/typedefstructdatatypedataMAXSIZE;/*队列的存储空间*/intfront,rear;/*队头队尾指针*/SEQQUEUE;定义一个指向顺序队列的指针变量：SEQQUEUE*q;,17,3.3.3队列的顺序存储表示和操作的实现,现将循环队列的基本操作的准则总结如下。循环队列的初始化条件：q-front=q-rear=0。循环队列满条件：(q-rear+1)%MAXSIZE=q-front。循环队列空条件：q-front=q-rear。循环队列的基本操作实现如下。1.初始化队列2.判队空操作3.入队列操作4.读队头元素操作5.出队列操作6.置空操作7.求队列长度操作,18,3.3.4队列的链式存储表示和操作的实现,队列也可以采用链式存储结构表示，这种链式存储结构的队列称为链队列。队列中结点的结构和单链表的结点结构一样。用C语言描述链队列的数据类型如下：#definedatatypechartypedefstructQueuenodedatatypedata;structQueuenode*next;Linknode;/*链队列结点的类型*/typedefstructLinknode*front,*rear;LINKQUEUE;/*将头尾指针封装在一起的链队列*/定义一个指向链队列的指针：LINKQUEUE*q;,19,3.3.4队列的链式存储表示和操作的实现,图3.9列出了链队列元素入队、出队的情况。,20,3.3.4队列的链式存储表示和操作的实现,链队列的基本运算如下。1.初始化队列2.判队空操作3.入队列操作4.读队头元素操作5.出队列操作,21,3.4队列的应用,【例3.3】编写一个简单的事件处理表。用户可以输入和保存一系列事件；当一个事件处理完毕后，它就会从事件处理表中删除；还可以查询事件处理表中剩余的事件。参见教材P64,22,本章小结,(1)栈是一种限定其插入、删除操作只能在线性表的一端进行的特殊结构。由于在栈中的数据元素具有后进先出的特点，所以，人们又将它称为LIFO线性表。栈可以用顺序存储结构和链式存储结构表示。(2)队列是一种限定其插入在线性表的一端进行，删除则在线性表的另一端进行的特殊结构。由于在队列中的数据