数据结构：栈的原理与应用.ppt

主要内容 栈的定义 顺序栈 链栈 栈的应用举例 课堂作业 一、栈的定义 2、栈的逻辑结构 3、入栈与出栈 4、 栈的基本操作 ?初始化 IniStack(S): 构造一个空栈S，准备存放数据； 进栈操作 Push(S,x)： 将数据元素x插入栈S，使x成为S的栈顶元素； 出栈操作 Pop(S)： 当栈不空时返回栈顶元素为该函数的值，然后删除栈顶元素； 取栈顶元素 GetTop(S)： 当栈不空时返回栈顶元素为该函数的值，但栈顶保持不变； 判栈空 EmptyStack(S)： 若S为空栈则该函数值为1，否则为0。 二、栈的顺序存储结构 四、栈的应用举例 实现数制转换 表达式求值 （2）算术表达式求值 中缀式求值的算法 运算符和界限符统称为算符。根据算术四则运算的规则（即中缀式的运算规则），任两个相继出现的算符θ1和θ2之间的优先关系至多是下面三种关系之一： θ1 θ2 θ1的优先权低于θ2 θ1 =θ2 θ1的优先权等于θ2 θ1 θ2 θ1的优先权高于θ2 操作符优先级表 求表达式算法 算法需两个栈。一个是运算符栈(OPTR) ；另一个是操作数或运算结果栈(OPND) 。算法的基本思想是： （1）首先置操作数栈为空栈；为了使表达式中第一个运算符能够进栈，首先将一个优先权最低的运算符‘#’压入运算符栈中成为其栈底。 （2）从左向右依次读出表达式中的每一个字符， ①若为操作数，则将其压入操作数栈中，接着读出下一个字符； ②若为运算符，则和运算符栈的栈顶运算符比较优先权： ⅰ 如果读出的运算符的优先权高于运算符栈栈顶运算符的优先权，则将其压入运算符栈中，接着读出下一个字符； ⅱ 如果读出的运算符的优先权等于运算符栈栈顶运算符的优先权（即左右括号相遇），则从运算符栈中退出一个运算符（即左括号）； ⅲ 如果读出的运算符的优先权低于运算符栈栈顶运算符的优先权，则从操作数栈连续退出两个操作数（先退出的是第二操作数，后退出的是第一操作数），从运算符栈中退出一个运算符，然后作相应的运算，并将运算结果压入操作数栈中。 例如：表达式3*(7-2),求值过程如下表： 解题的思路 当老鼠走到某个位置，前面没有路可走时，怎么办？要沿着老路回去。退回到哪里呢？退回到刚走的位置。这正好符合栈的特征，最近的最先出来。 需要解决的几个问题 迷宫如何表示？ 位置如何保存在栈里？ 如何确定当前位置是否有出路？ 如何表示已经走过的位置？ 谢谢，请批评指正。 第*页 目录 高等学校教师资格认定2011 数据结构 栈是限定仅能在表尾一端进行插入、删除操作的线性表 （a1, a2, ... , ai -1, ai , ai+1, …, an ） 插入 删除 1.??? 什么是栈 第一个进栈的元素在栈底，最后一个进栈的元素在栈顶， 不含元素的栈称为空栈。 出栈 Pop 进栈 Push 栈顶 栈底 top bottom 空栈 top bottom a1 a2 . . . an bottom top bottom top A A B C D E A B 栈操作图示 A进栈 B C D E 进栈 E D C 出栈 C D E top top top 栈的特点 后进先出LIFO top bottom top bottom top top top 栈属于加了限制条件的线性结构； 栈是后进先出的线性表； 进栈和出栈只能从栈的一个端点进行； 栈中的元素个数可以是0，此时是空栈； 栈的元素的个数是可以变化的，可以是多个，但不能是无穷多个； 每个栈中的元素的类型相同. 5、栈的特性 思考：假设有A,B,C三个元素进S栈的顺序是A,B,C，写出所有可能的出栈序列。 CBA ACB ABC CAB BAC BCA 如果是4个元素，那么它 不可能的出栈序列有哪些？ 可能的出栈序列： 1243 1324 1342 2134 2143 2314 2431 3241 3214 3421 4321 不可能出现的出栈序列： 2413 3124 3412 4123 4231 4213 4312 用一个一维数组和一个整型变量来实现。 struct stack { datatype array[maxlen]; int top; } 栈数组 array[maxlen] 用来存放栈中所有元素； 整型变量top的整数值表示栈顶元素在数组array中的位置，也称为栈顶指针。 约定栈顶指针指向 向栈顶元素的位置 当栈用顺序结构存储时， 栈的基本操作如建空栈、 进栈、出栈等操作 如何实现？ 顺