数据结构(牛小飞)5栈.ppt
栈模型,栈(Stack),小结和作业,栈的应用,复习,栈的链式实现,栈的数组实现,复习-线性表的逻辑结构,Da1,a2,ai,an,R|ai-1,ai D,i=2,.,n,复习-顺序线性表,public class MyArrayList private AnyType theItems;/存储空间基址 private int theSize;/表的大小 private static final int DEFAULT_CAPACITY=10;/数组容量 成员方法,复习-单链表,private static class Node public AnyType data;public Node next;成员方法；,复习-双向链表,复习-线性表的基本操作,1、取出第i个数据元素的值,2、插入或删除第i个数据元素,3、第1个和最后1个数据元素往往是注意的焦点,栈模型,栈是线性表的特例。,栈(stack)是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶(top)。,(a1,a2,a3,an-1,an),表头(栈底),表尾(栈顶),栈模型,栈的基本操作：push(进栈)：pop(出栈)：,插入操作,删除最后插入的元素,(a1,a2,a3,an-1,an),表头,表尾,栈模型,栈模型：通过push向栈输入，通过pop和top从栈中输出,2,栈模型：只有栈顶元素可以访问,将n个数a1,a2,an-1,an按照下标的次序进栈，然后再出栈,(),(a1),(a1,a2),(a1,a2,a3),(a1,a2,a3,),(a1,a2,a3,an-1),(a1,a2,a3,an-1,an),压栈过程,出栈过程,(),(a1),(a1,a2),(a1,a2,a3),(a1,a2,a3,),(a1,a2,a3,an-1),(a1,a2,a3,an-1,an),an,an-1,a1,a2,a3,所以，栈又叫做先进后出(Last In First Out)表。,栈模型,练习,1、有个元素按照6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列:A)5,4,3,6,2,1 B)4,5,3,1,2,6 C)3,4,6,5,2,1 D)2,3,4,1,5,6,2.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列：A、1，3，2，4 B、2，3，4，1 C、4，3，1，2 D、3，4，2，1,栈的数组实现,栈的逻辑形态,空栈：topOfStack=-1,栈的数组实现,栈的逻辑形态,对每一个栈的数据结构，用一个数组theArray以及栈顶位置topOfStack来描述。,A,进栈,栈的数组实现,栈的基本操作：进栈，出栈,B,C,出栈,E,D,C,B,A,栈的数组实现,public class ArrayStack private AnyType theArray;/存储空间基址 private int topOfStack;/栈顶 private static final int DEFAULT_CAPACITY=10;/数组容量 成员方法：,构造函数,isEmpty,push,pop,java语言描述：,ArrayStack,原形：ArrayStack(),作用：形成一个空栈,public ArrayStack()/空栈初始化 ensureCapacity(DEFAULT_CAPACITY);topOfStack=-1;,isEmpty,bool isEmpty(),/retern topOfStack=-1;,原形：boolean isEmpty(),作用：测试栈中是否有数据元素,if(topOfStack=-1)return true;return false;,pop,原形：public AnyType pop(),作用：将栈顶的数据元素从栈中删除，并将其值 赋给变量popVal。,A,B,过程:,popVal=B=theArraytopOfStack,pop,public AnyType pop()throws StackEmptyException,if(isEmpty()throw new StackEmptyException(Stack pop);,AnyType popVal;popVal=theArraytopOfStack;topOfStack-;return popVal;,push,原形:void push(AnyType x),作用:把元素x插入栈顶,过程:,A,B,public void push(AnyType x),if(topOfStack+1=DEFAULT_CAPACITY)ensureCapacity(topOfStack+10);,/theArray+topOfStack=x;,topOfStack+;,theArraytopOfStack=x;,push,栈的链式实现,单链表,栈顶,栈底,栈空?,S为空,栈满?,似乎无限,栈中数据元素的个数?,链式栈的逻辑形态,栈的链式实现,public class SingleLinkedStack,栈的链式实现,java语言描述：,private Node top;/栈顶元素,public void makeEmpty()top=null;,public SingleLinkedStack()top=null;theSize=0;,public boolean isEmpty()return top=null;,private int theSize;,public AnyType pop(),public void push(AnyType x),pop,top=top.next;,popVal=top.data;,public AnyType pop()throws StackEmptyException,if(isEmpty()throw new StackEmptyException(Stack pop);,AnyType popVal;,return popVal;,theSize-;,push,Node newNode=new Node(x);,newNode.next=top;,top=newNode;,theSize+;,public void push(AnyType x),所有的语句可以简化为：top=new Node(x,top);,栈的应用,栈是一个十分重要的数据结构，应用很广泛,函数的调用：,A,sa1call bsa2,sb1call csb2,sc1sc2,B,C,平衡符号(括号匹配),问题：在程序语言的语法检查阶段，涉及到的语法错误，如括号的匹配，即：有一个左括号，就要有一个右括号，左括号和右括号要成对出现。即()是合法的，而()是非法的。,算法：,做一个空栈。读入字符直到文件结尾。,平衡符号(括号匹配),如果字符是一个开放字符，则将其推入栈中。如果字符是一个封闭字符，则当栈空时报错。否则，将栈元素弹出。如果弹出的符号不是对应的开放字符，则报错。在文件结尾，如果栈非空报错。,平衡符号(括号匹配),(,(,),栈是否为空？,pop,push(x),if(x!=pop)error,文件结尾处，栈非空，报错。,后缀表达式,6*(5+(2+3)*8+3),后缀式：6523+8*+3+*,6,5,2,3,遇到第1个+时的操作：2+3=5,5,后缀表达式,(2+3)*8+5+3)*6,后缀式：6523+8*+3+*,6,5,2,遇到第1个*时的操作：5*8=40,5,40,8,后缀表达式,(2+3)*8+5+3)*6,后缀式：6523+8*+3+*,6,5,遇到第2个+时的操作：40+5=45,40,45,3,后缀表达式,(2+3)*8+5+3)*6,后缀式：6523+8*+3+*,6,遇到第3个+时的操作：45+3=48,45,48,3,后缀表达式,(2+3)*8+5+3)*6,后缀式：6523+8*+3+*,6,遇到第2个*时的操作：48*6=288,48,288,中缀到后缀的转换,1、只允许操作,，（，）,2、坚持普通的优先级法则,转换规则的前提：,1、,都是二元运算,x OPTR y=z,2、,的优先级要高于,3、,的优先级相同,4、,的优先级相同,优先级的概念：,中缀到后缀的转换,算术表达式求值,如何处理括号？,1、左括号和右括号分别表示一个表达式的开始和结束,2、如果一个运算符的其中一个操作数是括号表达式，则，必须先计算出该表达式。,3(7 2),(7 2)3,算术表达式求值,优先级表：,左,右,中缀表达式a+b*c+(d*e+f)*g,基本规则：1.读到一个操作数时，立即输出该数，操作符不立即输出。2.比较栈顶操作符与遇到的输入操作符之间的优先级，如果栈顶操作符的优先级高，则出栈。否则，压栈。3.遇到（，压栈，直到遇到）出栈。,中缀到后缀的转换,中缀表达式a+b*c+(d*e+f)*g,输出序列,栈,a,+,b,*,*的优先级比+高，故*入栈；,c,*的优先级比+高，*弹出放入输出序列中；,*,+的优先级同+，按运算方向，+出栈，+入栈；,+,+,中缀到后缀的转换,中缀表达式a+b*c+(d*e+f)*g,输出序列,栈,a,b,(的优先级比+高，故(入栈；,c,除非出现)，否则(不会弹出，故*入栈；,*,+的优先级比*小，故*弹出，+入栈；,+,+,(,d,*,e,*,+,f,中缀到后缀的转换,中缀表达式a+b*c+(d*e+f)*g,输出序列,栈,a,b,读到)，将直到(的栈元素都弹出；,c,*的优先级比+大，故，*入栈；,*,+,+,(,d,e,*,f,+,+,*,g,*,+,中缀到后缀的转换,中缀表达式a+b*c+(d*e+f)*g,后缀表达式为abc*+de*f+g*+,中缀到后缀的转换,算术表达式求值,1、设立操作符栈OPTR，将运算符#压栈,2、从左至右扫描表达式，取一个字符c,2.1、如果c是操作数，则将c压栈(OPND),设立操作数栈OPND,2.2、如果c是运算符，取OPTR的栈顶e,、ec，将c压栈OPTR,、ec，OPTR出栈，OPND出栈两次，得到两个操作数a,b，进行e运算后，将结果压栈OPND，重复2.2,、e=c，OPTR 出栈,3、重复2直到表达式为空,算术表达式求值,4、如果OPTR不空，重复以下步骤：,4.1、出栈e,4.3、OPND出栈两次，得到两个操作数 a,b，进行e运算后，将结果压栈OPND,4.2、如果e=#，break,5、OPND出栈result,6、如果OPTR和OPND都为空，则输出result，否则，输出 错误,方法调用,A,sa1call bsa2,sb1call csb2,sc1sc2,B,C,小 结,链式栈,栈的基本概念,特殊的线性表,主要的操作：入栈、出栈,先进后出,栈的应用,顺序栈,栈空和栈满的判定条件,栈顶指针和栈顶元素的关系,不带头结点的单链表,栈空的条件,栈顶指针和栈顶元素的关系,作业,作业：p75,3.22,
