数据结构课件PPT110章全 第三章 栈和队列1.ppt

《数据结构课件PPT110章全 第三章 栈和队列1.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章栈和队列3.1栈3.1.1抽象数据类型栈的定义3.1.2栈的表示和实现3.2栈的应用举例3.2.1数制转换3.2.2括号匹配的检验3.2.3行编辑程序3.2.4迷宫求解3.2.5表达式求值3.3栈与递归的实现3.4队列3.4.1抽象数据类型队列的定义3.4.2链队列——队列的链式表示和实现3.4.3循环队列——队列的顺序表示和实现3.5离散事件模拟3.1.1栈3.1.1栈的定义及基本运算栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空

2、栈。假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。例、一叠书或一叠盘子。栈的抽象数据类型的定义如下：P45anan-1a2a1……栈顶栈底3.1.2顺序栈由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端

3、点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top来表示top7654321-1top用来指示当前栈顶的位置，通常称top为栈顶指针。顺序栈的类型定义如下：#defineSTACK_INIT_SIZE#defineSTACKINCREMENTtypedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;设S是SqStack类型的指针变量。若栈底位置在向量的低端，即s–>base是栈底元素，那么栈顶指针s–>top是正向增加的，即进栈时需将s–>top加1，退栈时

4、需将s–>top减1。s–>top==s->base表示空栈，s–>top-s->base==stacksize表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。1、初始化栈算法：1.[构建栈]1.1分配空间并检查空间是否分配失败，若失败则返回错误1.2设置栈底和栈顶指针1.3设置栈大小2.[算法结束]2、取栈顶元素算法：1.[取元素]1.1判断

5、栈是否是空栈，若是空栈则返回错误1.2通过栈顶指针获取栈顶元素2.[算法结束]3、入栈算法：1.[初值]获取入栈元素e2.[入栈]2.1判断栈空间是否存在，若无空间则重新分配更大的空间，并调整栈底，栈顶指针以及栈大小。2.2元素e压入栈中的栈顶位置2.3栈顶指针增加13.[算法结束]4、退栈算法：1.[退栈]1.1判断栈是否为空，为空则返回错误。1.2获取栈顶元素e1.3栈顶指针减12.[算法结束]3.1.3链栈栈的链式存储结构称为链栈，它是运算是受限的单链表，插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单

6、链表那样附加头结点。栈顶指针就是链表的头指针。链栈的类型说明如下：typedefstructstacknode{datatypedatastructstacknode*next}stacknode;typedefstruct{structstacknode*top;}linkstack;voidinitstack(linkstack*p){p–>top=null;}intstackempty(linkstack*p){returnp–>top==null;}Voidpush(linkstack*p,datatypex){stacknode*q;

7、q=(stacknode*)malloc(sizeof(stacknode));q–>data=x;q–>next=p–>top;p–>top=q;}Elemtypepop(linkstack*p){Elemtypex;stacknode*q=p–>top;if(stackempty(p))error(“stackunderflow.”);x=q–>data;p–>top=q–>next;free(q);returnx;}Datatypestacktop(linkstack*p){if(stackempty(p))error(“stackise

8、mpty.”);returnp–>top–>data;}3.2栈的应用举例由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几