文档介绍：2017-3-3 北京化工大学信息学院数据结构 1 ??栈栈 ( Stack ) ( Stack ) 八进制数、括号匹配、行编辑程序、八进制数、括号匹配、行编辑程序、迷宫、表达式求值、出栈合法性迷宫、表达式求值、出栈合法性??队列队列 ( Queue ) ( Queue ) 杨辉三角杨辉三角 2017-3-3 北京化工大学信息学院数据结构 2 定义定义●●只允许在一端插入和删除的线性表; 只允许在一端插入和删除的线性表; ●●允许插入和删除的一端称为允许插入和删除的一端称为栈顶栈顶(top) (top) , ,另一另一端称为端称为栈底栈底(bottom) (bottom) 。。特点特点后进先出后进先出 (LIFO) (LIFO) 栈栈 ( Stack ) ( Stack ) 退栈进栈 a 0a n-1a n-2? top bottom 2017-3-3 北京化工大学信息学院数据结构 3 ADT Stack { // 对象:由数据类型为 StackData 的元素构成 void p ush (StackData x) ; //进栈 void p op () ; //出栈 StackData t op () ; //取栈顶 bool is Empty () ; //判栈空否 bool is Full () ; //判栈满否(顺序栈) } 栈的主要操作栈的主要操作 2017-3-3 北京化工大学信息学院数据结构 4 top 空栈 top top top top top a 进栈 b 进栈 aa b a b c d e e 进栈 a b c d e f 进栈溢出 a b d e e 退栈 c 2017-3-3 北京化工大学信息学院数据结构 5 top c 退栈 b 退栈 a b aa 退栈空栈 top a b dd 退栈 c top a b c top top 2017-3-3 北京化工大学信息学院数据结构 6栈的链接表示栈的链接表示——链式栈链式栈链式栈无栈满问题,空间可扩充链式栈无栈满问题,空间可扩充插入与删除仅在栈顶处执行插入与删除仅在栈顶处执行链式栈的栈顶在链头链式栈的栈顶在链头适合于多栈操作适合于多栈操作 top 2017-3-3 北京化工大学信息学院数据结构 7栈的应用举例栈的应用举例 1 1——八进制数八进制数 2017-3-3 北京化工大学信息学院数据结构 8栈的应用举例栈的应用举例 2 2——括号匹配括号匹配{()()()()[][][]} {()()()()[][][]} 匹配匹配)))((( )))((( 不匹配不匹配({)} ({)} 不匹配不匹配后后出现的左括号出现的左括号先先匹配匹配————栈栈 2017-3-3 北京化工大学信息学院数据结构 9 2017-3-3 北京化工大学信息学院数据结构 10栈的应用举例栈的应用举例 3 3——行编辑程序行编辑程序# 退格符@ 退行符 switch(ch){ case '#': (); break; case '@': (); break; default: (ch); break; }