第三章-栈和队列10.17(1).ppt

3栈和队列数据结构3栈和队列主要内容栈的类型定义栈的表示顺序表示链表表示栈的应用进制转换括号匹配地图四染色问题走迷宫表达式计算栈和递归栈的类型定义定义只允许在同一端删除、同一端插入的线性表允许插入、删除的一端叫做栈顶(top)，另一端叫做栈底(bottom)初始化：栈内没有元素栈的应用栈的应用颠倒元素顺序直接应用栈先进后出的特性数制转换记录“历史信息”括号匹配的检验地图四染色问题走迷宫表达式计算栈的应用：括号匹配检测问题括号、引号等符号是成对出现的，必须相互匹配设计一个算法，自动检测输入的字符串中的括号是否匹配比如：{}[([][])]匹配[(])，(()]都不匹配栈的应用：括号匹配检测括号的匹配规则从里向外开始左括号应当和最近的右括号匹配[([][])]栈的应用：括号匹配检测思考从左向右扫描字符串栈的应用：括号匹配检测发现规律当扫描到当前字符的时候，需要知道已经扫描过的字符中，哪一个离它最近栈的应用：括号匹配检测栈“记录历史”的特性人的记忆：越早发生的事情越难回忆越迟发生的事情越容易回忆栈的应用：括号匹配检测算法思想从左向后扫描每一个字符栈的应用：括号匹配检测栈的应用：括号匹配检测栈的应用：括号匹配检测栈的应用：括号匹配检测栈的应用：括号匹配检测栈的应用：括号匹配检测栈的应用：括号匹配检测栈的应用：括号匹配检测])][][([当前是[，期待一个]栈的应用：括号匹配检测思考从左向右扫描字符串])][][([当前是(，和刚才的[不匹配，说明相匹配的符号还在右边，继续扫描栈的应用：括号匹配检测思考从左向右扫描字符串])][][([当前是[，和刚才的(不匹配，说明相匹配的符号还在右边，继续扫描栈的应用：括号匹配检测思考从左向右扫描字符串])][][([当前是]，和刚才的[正好一对，可以从字符串中“删去”不考虑了栈的应用：括号匹配检测思考从左向右扫描字符串])][([当前是[，目前最近的一个是(，不匹配，继续扫描])][][([因此希望有一个工具，能够记录扫描的历史，这样可以方便的得到最近的上一次访问的字符栈的先进后出越早压入的元素越晚弹出越迟压入的元素越早弹出因此很自然的想到利用栈来模拟记忆准备一个栈，用于存放扫描过的字符如果栈为空，直接把当前字符入栈否则，把栈顶字符和当前字符比较当所有字符都扫描完毕，栈应当为空若匹配，则弹出栈顶字符，继续向前扫描不匹配，则当前字符入栈，继续向前扫描])][][([栈为空，当前字符直接入栈[如果栈为空，直接把当前字符入栈否则，把栈顶字符和当前字符比较若匹配，则弹出栈顶字符，继续向前扫描不匹配，则当前字符入栈，继续向前扫描])][][([栈顶字符和当前字符不匹配，当前字符入栈[(如果栈为空，直接把当前字符入栈否则，把栈顶字符和当前字符比较若匹配，则弹出栈顶字符，继续向前扫描不匹配，则当前字符入栈，继续向前扫描])][][([栈顶字符和当前字符不匹配，当前字符入栈[([如果栈为空，直接把当前字符入栈否则，把栈顶字符和当前字符比较若匹配，则弹出栈顶字符，继续向前扫描不匹配，则当前字符入栈，继续向前扫描])][][([栈顶字符和当前字符匹配，弹出栈顶字符[([如果栈为空，直接把当前字符入栈否则，把栈顶字符和当前字符比较若匹配，则弹出栈顶字符，继续向前扫描不匹配，则当前字符入栈，继续向前扫描])][][([栈顶字符和当前字符不匹配，当前字符入栈[([如果栈为空，直接把当前字符入栈否则，把栈顶字符和当前字符比较若匹配，则弹出栈顶字符，继续向前扫描不匹配，则当前字符入栈，继续向前扫描])][][([栈顶字符和当前字符匹配，弹出栈顶字符[([如果栈为空，直接把当前字符入栈否则，把栈顶字符和当前字符比较若匹配，则弹出栈顶字符，继续向前扫描不匹配，则当前字符入栈，继续向前扫描])][][([栈顶字符和当前字符匹配，弹出栈顶字符[(如果栈为空，直接把当前字符入栈否则，把栈顶字符和当前字符比较若匹配，则弹出栈顶字符，继续向前扫描不匹配，则当前字符入栈，继续向前扫描])][][([栈顶字符和当前字符匹配，弹出栈顶字符[如果栈为空，直接把当前字符入栈否则，把栈顶字符和当前字符比较若匹配