吉林大学数据结构_堆栈、队列.pptx

2.5 堆 栈;基本定义;顺序栈;;顺序栈——入栈算法;顺序栈——出栈算法;顺序栈——存取栈顶元素;链式栈;链式栈——入栈算法;链式栈——出栈算法;链式栈——存取栈顶元素;链式栈——栈清空;顺序栈与链式栈的比较-1;顺序栈与链式栈的比较-2;堆栈应用——括号匹配;高级语言程序设计中各种括号应该匹配，如“（”与“）”匹配、“[”与“]”匹配、“{”与“}”匹配等。字符串“{a=(b*c}+free()]”中的括号就没有匹配上，因为串中第一个关括号“}”和最近的未匹配开括号“（”不匹配。;本小节将给出一个简单程序，该程序检查一个输入文本文件中的括号是否正确匹配。 为了实现该程序，先阐明其主要思想。 我们注意到在输入文本文件中，因为字符是按次序输入的，所以如果输入的字符是开括号，则应将其存放起来，继续下一个字符的输入；如果输入的是关括号，则应考察与其最??的未匹配的开括号是否匹配，若匹配，则将匹配的开括号从存放处删除。也就是说，每次用来和关括号进行匹配的开括号都是最后输入的，这符合堆栈的后进先出的特点，因此用堆栈来存放开括号是合理的。;算法match() Read(c). While c≠’\n’ do ( if isopen(c) then s.push(c). else if isclose(c) then ( if notempty(s) then ( s.pop(c’). if notmatch(c,c’) then (print “匹配失败”. return. ) ) else ( print “匹配失败”. Return. ) ) read(c). ) if notempty(s) then ( print “检测到未匹配的开括号”. Return.) ▍;2.6 队列;;顺序队列;删除操作 ;1）不要求队头元素必须存放在下标为零的数组中。;2）要求队头元素必须存放在下标为零的数组元素中。;删除操作存在的问题;;环状队列;;;;操作;顺序队列——入队;顺序队列——出队;顺序队列——存取队首元素;链式队列;;操 作;链式队列——入队;链式队列——出队;链式队列——存取队首元素