数据结构牛小飞5栈

1、栈模型,栈(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 da

2、ta; 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向栈输入，通过po

3、p和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、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,

5、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); topOfSt

6、ack=-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( isE

7、mpty( ) ) 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;,topOfSt

8、ack+;,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; ,p

9、rivate 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

10、=top;,top=newNode;,theSize+;,public void push(AnyType x ) ,所有的语句可以简化为： top = new Node(x,top);,栈的应用,栈是一个十分重要的数据结构，应用很广泛,函数的调用 ：,A,sa1 call b sa2,sb1 call c sb2,sc1 sc2,B,C,平衡符号(括号匹配),问题： 在程序语言的语法检查阶段，涉及到的语法错误，如括号的匹配，即：有一个左括号，就要有一个右括号，左括号和右括号要成对出现。即( )是合法的，而( )是非法的。,算法：,做一个空栈。读入字符直到文件结尾。,平衡符号(括号匹配),如果

11、字符是一个开放字符，则将其推入栈中。如果字符是一个封闭字符，则当栈空时报错。否则，将栈元素弹出。如果弹出的符号不是对应的开放字符，则报错。在文件结尾，如果栈非空报错。,平衡符号(括号匹配),(,(,),栈是否为空？,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+

12、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、 , 的优

13、先级相同,优先级的概念：,中缀到后缀的转换,算术表达式求值,如何处理括号？,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,

14、*,*的优先级比+高，故*入栈；,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,*,+,中缀到后缀的转换,中

15、缀表达式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,2.2.1、ec，将c压栈OPTR,2.2.2、ec，OPTR出栈，OPND出栈两次，得到两个操作数a, b，进行e运算后，将结果压栈OPND，重复2.2,2.2.3、e=c，OPTR 出栈,3、 重复2直到表达式为空,算术表达式求值,4、如果OPTR不空，重复以下步骤：,4.1、出栈e,4.3、OPND出栈两次，得到两个操作数 a, b，进行e运算后，将结果压栈O