数据结构牛小飞5 栈

1、栈模型栈模型栈栈(stack)小结和作业小结和作业栈的应用栈的应用复习复习栈的链式实现栈的链式实现栈的数组实现栈的数组实现复习复习- -线性表的逻辑结构线性表的逻辑结构da1, a2, , ai ,anr |ai-1 ,ai d, i=2,.,n 复习复习- -顺序线性表顺序线性表a0 a1 a2l.theitemsl.thesizepublic class myarraylistanytype extends comparable private anytype theitems; /存储空间基址存储空间基址 private int thesize; /表的大小表的大小 private st

2、atic final int default_capacity = 10; /数组容量数组容量 成员方法成员方法复习复习- -单链表单链表private static class node public anytype data;public node next;成员方法；a0a1a2la0a1a2l复习复习- -双向链表双向链表a2a3a1la2a3a1l复习复习- -线性表的基本操作线性表的基本操作1、取出第i个数据元素的值2、插入或删除第i个数据元素3、第1个和最后1个数据元素往往是注意的焦点栈模型栈模型栈是线性表的特例。栈是线性表的特例。 栈(stack)是限制插入和删除只能在一个位置

3、上进行的表，该位置是表的末端，叫做栈顶(top)。(a1, a2, a3, an-1, an)表头(栈底)表尾(栈顶)栈模型栈模型 栈的基本操作：栈的基本操作：push(进栈进栈)：pop(出栈出栈)：插入操作插入操作删除最后插入的元素删除最后插入的元素(a1, a2, a3, an-1, an )表头表尾栈模型栈模型stackpushpoptop栈模型：通过push向栈输入，通过pop和top从栈中输出41362top栈模型：只有栈顶元素可以访问将n个数a1, a2,an-1,an按照下标的次序进栈，然后再出栈() (a1)(a1, a2)(a1, a2,a3)(a1, a2,a3,)(a1

4、, 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)anan-1a1a2a3所以，栈又叫做先进后出(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，下面哪一个序列不可能是这

5、个栈的输出序列： a、 1，3，2，4 b、2，3，4，1 c、 4，3，1，2 d、3，4，2，1栈的数组实现栈的数组实现a0 a1 a2l.theitemsl.thesizea0a1a2topofstack 栈顶栈的逻辑形态栈的逻辑形态空栈：topofstack =-1topofstack a0a1a2a3栈的数组实现栈的数组实现topofstack 栈的逻辑形态栈的逻辑形态对每一个栈的数据结构，用一个数组thearray以及栈顶位置topofstack来描述。 a进栈栈的数组实现栈的数组实现栈的基本操作：进栈，出栈栈的基本操作：进栈，出栈topofstack topofstack bto

6、pofstack ctopofstack 出栈edcbatopofstack topofstack topofstack 栈的数组实现栈的数组实现public class arraystack private anytype thearray; /存储空间基址存储空间基址 private int topofstack; /栈顶栈顶 private static final int default_capacity = 10; /数组容量数组容量 成员方法：成员方法：构造函数构造函数 isemptypushpopjava语言描述：语言描述：arraystack 原形： arraystack (

7、) 作用： 形成一个空栈 public arraystack( ) /空栈初始化 ensurecapacity(default_capacity); topofstack=-1; topofstack isempty bool isempty ( ) /retern topofstack=-1; 原形：boolean isempty ( ) 作用：测试栈中是否有数据元素 if(topofstack=-1) return true;return false;pop 原形：public anytype pop( ) 作用：将栈顶的数据元素从栈中删除，并将其值 赋给变量popval。 abtopof

8、stack 过程:popval=b=thearraytopofstacktopofstack poppublic anytype pop() throws stackemptyexception if( isempty( ) ) throw new stackemptyexception(stack pop );anytype popval;popval=thearraytopofstack;topofstack-;return popval;push 原形: void push(anytype x) 作用: 把元素x插入栈顶 过程: atopofstack topofstack bpubli

9、c void push(anytype x)if(topofstack+1=default_capacity) ensurecapacity(topofstack+10); /thearray+topofstack=x;topofstack+;thearraytopofstack=x;push栈的链式实现栈的链式实现单链表a0a1a2la0a1a2s栈顶栈底栈空?s为空栈满?似乎无限栈中数据元素的个数?链式栈的逻辑形态链式栈的逻辑形态栈的链式实现栈的链式实现public class singlelinkedstack 栈的链式实现栈的链式实现java语言描述：语言描述：private node

10、 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 )popa0a1a2toptop=top.next;popval=top.data;public anytype pop( ) throws stackemptyexception

11、if( isempty( ) ) throw new stackemptyexception(stack pop );anytype popval;return popval;topthesize-;pushtopa1a2a3node newnode=new node(x);xnewnodenewnode.next=top;top=newnode;thesize+;toppublic void push(anytype x ) 所有的语句可以简化为：所有的语句可以简化为：top = new node(x,top);栈的应用栈的应用栈是一个十分重要的数据结构，应用很广泛 函数的调用 ：asa1c

12、all bsa2sb1call csb2sc1sc2bc平衡符号平衡符号(括号匹配括号匹配)问题： 在程序语言的语法检查阶段，涉及到的语法错误，如括号的匹配，即：有一个左括号，就要有一个右括号，左括号和右括号要成对出现。即( )是合法的，而( )是非法的。算法：做一个空栈。读入字符直到文件结尾。平衡符号平衡符号(括号匹配括号匹配)如果字符是一个开放字符，则将其推入栈中。如果字符是一个封闭字符，则当栈空时报错。否则，将栈元素弹出。如果弹出的符号不是对应的开放字符，则报错。在文件结尾，如果栈非空报错。平衡符号平衡符号(括号匹配括号匹配)topofstack () topofstack topofs

13、tack 栈是否为空？栈是否为空？poppush(x)if(x!=pop) error文件结尾处，文件结尾处，栈非空，报错。栈非空，报错。后缀表达式后缀表达式6*(5+(2+3)*8+3)后缀式：6523+8*+3+*topofstack 6523遇到第1个+时的操作：2+3=55topofstack topofstack 后缀表达式后缀表达式(2+3)*8+5+3)*6后缀式：6523+8*+3+*652遇到第1个*时的操作：5*8=405 40topofstack 8topofstack topofstack 后缀表达式后缀表达式(2+3)*8+5+3)*6后缀式：6523+8*+3+*6

14、5遇到第2个+时的操作：40+5=4540topofstack topofstack 45topofstack 3后缀表达式后缀表达式(2+3)*8+5+3)*6后缀式：6523+8*+3+*6遇到第3个+时的操作：45+3=48topofstack topofstack 45topofstack 483后缀表达式后缀表达式(2+3)*8+5+3)*6后缀式：6523+8*+3+*6遇到第2个*时的操作：48*6=288topofstack topofstack 48288topofstack 中缀到后缀的转换中缀到后缀的转换1、只允许操作, , , ，（，）2、坚持普通的优先级法则转换规则的

15、前提：转换规则的前提：1、, , , 都是二元运算x optr y = z 2、 , 的优先级要高于, 3、 , 的优先级相同4、 , 的优先级相同优先级的概念：优先级的概念：中缀到后缀的转换中缀到后缀的转换算术表达式求值算术表达式求值如何处理括号？1、左括号和右括号分别表示一个表达式的开始和结束2、如果一个运算符的其中一个操作数是括号表达式，则，必须先计算出该表达式。3 (7 2)(7 2) 3算术表达式求值算术表达式求值优先级表优先级表：+()#+(?#?=左右中缀表达式a+b*c+(d*e+f)*g基本规则：基本规则：1.读到一个操作数时，立即输出该数，操作符不立即输出。读到一个操作数时

16、，立即输出该数，操作符不立即输出。2.比较栈顶操作符与遇到的输入操作符之间的优先级，如比较栈顶操作符与遇到的输入操作符之间的优先级，如果栈顶操作符的优先级高，则出栈。否则，压栈。果栈顶操作符的优先级高，则出栈。否则，压栈。3.遇到（，压栈，直到遇到）出栈。遇到（，压栈，直到遇到）出栈。中缀到后缀的转换中缀到后缀的转换中缀表达式a+b*c+(d*e+f)*g输出序列输出序列栈栈a+b*的优先级比的优先级比+高，故高，故*入栈；入栈；c*的优先级比的优先级比+高，高，*弹出放入输出序列中；弹出放入输出序列中；*+的优先级同的优先级同+，按运算方向，按运算方向，+出栈，出栈，+入栈；入栈；+中缀到后

17、缀的转换中缀到后缀的转换中缀表达式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、从左至右扫描表达式，取一个字符c2.1、如果c是操作数，则将c压栈(opnd)设立操作数栈opnd2.2、如果c是运算符，取optr的栈顶e2.2.1、ec，optr出栈，opnd出栈两次，得到两个操作数a, b，进行e运算后，将结果压栈opnd，重复2.22.2.3、e=c，optr 出栈3、 重复2直到表达式为空算术表达式求值算术表达