3-数据结构与算法-北京大学2008-张铭-栈和队列

数据结构与算法第3章栈与队列本章由赵海燕主写://张铭，王腾蛟，赵海燕高等教育出版社，2008.6。“十一五”国家级规划教材“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6操作受限的线性表栈（Stack）运算只在表的一端进行队列（Queue）运算只在表的两端进行“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.63.1栈后进先出（LastInFirstOut）一种限制访问端口的线性表栈存储和删除元素的顺序与元素到达的顺序相反也称为“下推表”栈的主要元素栈顶（top）元素：栈的唯一可访问元素•元素插入栈称为“入栈”或“压栈”（push）•删除元素称为“出栈”或“弹出”（pop）栈底：另一端“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6栈的示意图每次取出（并被删除）的总是刚压进的元素，而最先压入的元素则被放在栈的底部当栈中没有元素时称为“空栈”k0k1...kn-1栈顶栈底出栈进栈“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6栈的主要操作入栈（push）出栈（pop）取栈顶元素（top）判断栈是否为空（isEmpty）“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.63.1.1栈的抽象数据类型templateclassT//栈的元素类型为TclassStack{public://栈的运算集voidclear();//变为空栈boolpush(constTitem);//item入栈，成功则返回真，否则返回假boolpop(T&item);//返回栈顶内容并弹出，成功返回真，否则返回假booltop(T&item);//返回栈顶内容但不弹出，成功返回真，否则返回假boolisEmpty(;//若栈已空返回真boolisFull();//若栈已满返回真};“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6栈的实现方式顺序栈（Array-basedStack）使用向量实现，本质上是顺序表的简化版•栈的大小关键是确定哪一端作为栈顶链式栈（LinkedStack）用单链表方式存储，其中指针的方向是从栈顶向下链接“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.63.1.2顺序栈templateclassTclassarrStack:publicStackT{private://栈的顺序存储intmSize;//栈中最多可存放的元素个数inttop;//栈顶位置，应小于mSizeT*st;//存放栈元素的数组public://栈的运算的顺序实现arrStack(intsize){//创建一个给定长度的顺序栈实例mSize=size;top=-1;st=newT[mSize];}arrStack(){//创建一个顺序栈的实例top=-1;}~arrStack(){//析构函数delete[]st;}voidclear(){//清空栈内容top=-1;}}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6顺序栈按压入先后次序，最后压入的元素编号为4，然后依次为3,2,1123top栈底4“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6顺序栈示意012345s.top=-1s.top=0A0B1C2D3E4F5s.top=5A012345A0B1C2D345s.top=3“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6顺序栈的溢出上溢（Overflow）当栈中已经有maxsize个元素时，如果再做进栈运算，所产生的现象下溢（Underflow）对空栈进行出栈运算时所产生的现象“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6顺序栈若入栈的顺序为1,2,3,4的话，则出栈的顺序可以有哪些?12341243132413421423143221342143……“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6压入栈顶boolarrStackT::push(constTitem){if(top==mSize-1){//栈已满cout栈满溢出endl;returnfalse;}else{//新元素入栈并修改栈顶指针st[++top]=item;returntrue;}}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6从栈顶弹出boolarrStackT::pop(T&item){//出栈的顺序实现if(top==-1){//栈为空cout栈为空，不能执行出栈操作endl;returnfalse;}else{item=st[top--];//返回栈顶元素并修改栈顶指针returntrue;}}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6从栈顶读取，但不弹出boolarrStackT::top(T&item){//返回栈顶内容，但不弹出if(top==-1){//栈空cout栈为空，不能读取栈顶元素endl;returnfalse;}else{item=st[top];returntrue;}}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6其他算法把栈清空voidarrStackT::clear(){top=-1;}栈满时，返回非零值（真值true）boolarrStackT::isFull(){return(top==maxsize-1);}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6栈的变种两个独立的栈底部相连：双栈迎面增长哪一种更好些？迎面增长的栈top1top2“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.63.1.3链式栈ki+2ki+1kik0topdatanext用单链表方式存储指针的方向从栈顶向下链接“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6链式栈的创建templateclassTclasslnkStack:publicStackT{private://栈的链式存储LinkT*top;//指向栈顶的指针intsize;//存放元素的个数public://栈运算的链式实现lnkStack(intdefSize){//构造函数top=NULL;size=0;}~lnkStack(){//析构函数clear();}}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6压入栈顶//入栈操作的链式实现boollnksStackT::push(constTitem){LinkT*tmp=newLinkT(item,top);top=tmp;size++;returntrue;}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6自单链栈弹出//出栈操作的链式实现boollnkStackT::pop(T&item){LinkT*tmp;if(size==0){cout栈为空，不能执行出栈操作endl;returnfalse;}item=top-data;tmp=top-next;deletetop;top=tmp;size--;returntrue;}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6顺序栈和链式栈的比较时间效率所有操作都只需常数时间顺序栈和链式栈在时间效率上难分伯仲空间效率顺序栈须说明一个固定的长度链式栈的长度可变，但增加结构性开销“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6顺序栈和链式栈的比较实际应用中，顺序栈比链式栈用得更广泛些顺序栈容易根据栈顶位置，进行相对位移，快速定位并读取栈的内部元素顺序栈读取内部元素的时间为O(1)，而链式栈则需要沿着指针链游走，显然慢些，读取第k个元素需要时间为O(k)•一般来说，栈不允许“读取内部元素”，只能在栈顶操作“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.63.1.4栈的应用栈的特点：后进先出体现了元素之间的透明性常用来处理具有递归结构的数据深度优先搜索表达式求值子程序／函数调用的管理消除递归“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6计算表达式的值表达式的递归定义基本符号集：{0，1，…，9，+，-，*，/，（，）}语法成分集：{表达式,项,因子,常数,数字}语法公式集中缀表达式23+(34*45)/(5+6+7)后缀表达式233445*56+7+/+后缀表达式求值“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6中缀表达法的语法公式表达式∷=项+项|项－项|项项∷=因子*因子|因子/因子|因子因子∷=常数|（表达式）常数∷=数字|数字常数数字∷=0|1|2|3|4|5|6|7|8|9“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6中缀表达的算术表达式的计算次序1.先执行括号内的计算，后执行括号外的计算。在具有多层括号时，按层次反复地脱括号，左右括号必须配对2.在无括号或同层括号时，先乘(*)、除(／)，后加(+)、减(-)3.在同一个层次，若有多个乘除（*、／）或加减(+，-)的运算，那就按自左至右顺序执行23+(34*45)/(5+6+7)=?计算特点？“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6后缀表达式表达式∷=项项+|项项-|项项∷=因子因子*|因子因子/|因子因子∷=常数常数∷=数字|数字常数数字∷=0|1|2|3|4|5|6|7|8|9“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6后缀表达式的计算233445*56+7+/+=？计算特点？中缀和后缀表达式的主要异同？23+34*45/(5+6+7)=?233445*56+7+/+=？“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6从左到右扫描中缀表达式。用栈存放表达式中的操作数、开括号以及在此开括号后暂不确定计算次序的其他符号：(1)当输入的是操作数时，直接输出到后缀表达式序列；(2)当遇到开括号时，把它压入栈；(3)当输入遇到闭括号时，先判断栈是否为空，若为空（括号不匹配），应该作为错误异常处理，清栈退出。若非空，则把栈中元素依次弹出，直到遇到第一个开括号为止，将弹出的元素输出到后缀表达式序列中（弹出的开括号不放到序列中），若没有遇到开括号，说明括号不配对，做异常处理，清栈退出。中缀表达式后缀表达式“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6中缀表达式后缀表达式从左到右扫描中缀表