【3.1】栈

操作受限的线性表:

  • 栈 (Stack) – 运算只在表的一端进行
  • 队列 (Queue) – 运算只在表的两端进行

一、栈定义

后进先出 (Last In First Out) – 一种限制访问端口的线性表

主要操作:

  • 进栈 (push) *出栈 (pop)

应用:

  • 表达式求值
  • 消除递归
  • 深度优先搜索

栈的抽象数据类型

火车进出栈问题:

  • 判断火车的出栈顺序是否合法 http://poj.org/problem?id=1363
  • 编号为1,2,…,n的n辆火车依次进站,给定一个n的排 列,判断是否是合法的出站顺序?

利用合法的重构找冲突

思考:

若入栈的顺序为1,2,3,4, 那么出栈的顺序可以有哪些?

从初始输入序列1,2,…,n,希望利用一个栈 得到输出序列p1,p2,…,pn (它们是1, 2, …,n的一种排列)。若存在下标i,j,k,满足 i<j<k 同时 Pj<Pk<Pi,则输出序列是否合法?

二、栈的实现方式

  • 顺序栈 (Array-based Stack)
    • 使用向量实现,本质上是顺序表的简化版 。栈的大小
    • 关键是确定哪一端作为栈顶
    • 上溢,下溢问题
  • 链式栈(Linked Stack)
    • 用单链表方式存储,其中指针的方向是从栈顶向下链接

2.1 顺序栈

顺序栈的类定义:

压入先后次序,最后压入的元素编号为 4,然后依次为3,2,1

顺序栈的溢出:

  • 上溢 (Overflow)
    • 当栈中已经有maxsize个元素时,如果再做进栈 运算,所产生的现象
  • 下溢 (Underflow)
    • 对空栈进行出栈运算时所产生的现象

压入栈顶:

从栈顶弹出:

2.2 链式栈

用单链表方式存储

指针的方向从栈顶向下链接

链式栈的创建:

压入栈顶

从单链栈弹出元素

2.3 顺序栈和链式栈的比较

时间效率

  • 所有操作都只需常数时间
  • 顺序栈和链式栈在时间效率上难分伯仲

空间效率

  • 顺序栈须说明一个固定的长度
  • 链式栈的长度可变,但增加结构性开销

实际应用中,顺序栈比链式栈用得更广泛

  • 顺序栈容易根据栈顶位置,进行相对位移,快速定位并读取栈的内部元
  • 顺序栈读取内部元素的时间为O(1),而链式栈则需 要沿着指针链游走,显然慢些,读取第 k个元素需要 时间为 O(k) 素
  • 一般来说,栈不允许“读取内部元素”,只能 在栈顶操作

思考: STL中关于栈的函数:

  • top函数表示取栈顶元素,将结果返回给用户
  • pop函数表示将栈顶元素弹出(如果栈不空)
    • pop函数仅仅是一个操作,并不将结果返回。
    • pointer = aStack.pop()? 错误!
  • STL为什么这两个操作分开? 为什么不提供 ptop?

三、栈的应用

  • 栈的特点:后进先出
    • 体现了元素之间的透明性
  • 常用来处理具有递归结构的数据
    • 深度优先搜索
    • 表达式求值
    • 子程序/函数调用的管理
    • 消除递归

计算表达式的值:

  • 表达式的递归定义
    • 基本符号集:{0,1,…,9,+,-,*,/,(,)}
    • 语法成分集:{<表达式> , <项> , <因子> , <常数> , <数字> }
  • 中缀表达式 23+(34*45)/(5+6+7)
  • 后缀表达式 23 34 45 * 5 6 + 7 + / +

中缀表达法的语法公式:

表达式的递归图示

后缀表达式

后缀表达式

后缀表达式的计算:

后缀表达式求值:

  • 循环:依次顺序读入表达式的符号序列(假设 以=作为输入序列的结束),并根据读入的元 素符号逐一分析
    1. 当遇到的是一个操作数,则压入栈顶
    2. 当遇到的是一个运算符, 就从栈中两次取出栈顶, 按照运算符对这两个操作数进行计算。然后将计 算结果压入栈顶
  • 如此继续,直到遇到符号=,这时栈顶的值就 是输入表达式的值

后缀计算器的类定义:

思考:

  1. 栈往往用单链表实现。可以用双链表 吗?哪个更好?
  2. 请总结前缀表达式的性质,以及求值 过程。

四 递归转非递归

4.1 递归函数调用原理

递归的再研究:

递归出口:

  • 递归终止的条件,即最小子问题的求解
  • 可以允许多个出口

递归规则(递归体+界函数)

  • 将原问题划分成子问题
  • 保证递归的规模向出口条件靠拢

阶乘的非递归方式 :

  • 建立迭代
  • 递归转换为非递归

河内塔问题的递归求解程序(http://www.17yy.com/f/play/89425.html):

Hanoi递归子程序的运行示意图

递归运行时,堆栈的进退以及通过堆栈传递参数:

一个递归数学公式:

函数运行时的动态存储分配:

思考:

  • 对以下函数,请画出n=4情况下的递归树, 并用栈模拟递归的调用过程。
    • 阶乘函数
    • 2阶斐波那契函数 f0=0, f1=1, fn = fn-1+ fn-2

4.2 机械的递归转换

3.增加非递归入口

// 入栈
S.push(t+1,p1, ...,pm,q1,...qn);

6.标号为t+1的语句

7.改写循环和嵌套中的递归

对于循环中的递归,改写成等价的goto型循环

对于嵌套递归调用

例如,recf (... recf()) 改为:
exmp1 = recf ( ); 
exmp2 = recf (exmp1); 
...
exmpk = recf (exmpk-1)
然后应用规则 4 解决

8.优化处理

  • 去掉冗余进栈/出栈
  • 根据流程图找出相应的循环结构,从而消去 goto语句

4.3 优化后的非递归函数

快排的时间对照(单位ms):

递归与非递归处理问题的规模:

递归求f(x):

int f(int x) {
    if (x==0) return 0;
    return f(x-1)+1;
}

在默认设置下,当x超过 11,772 时会出现堆栈溢出

非递归求f(x),栈中元素记录当前x值和返回值

  • 在默认设置下,当x超过32,375,567时会出现错误

思考:

用机械的转换方法

  • 阶乘函数
  • 2阶斐波那契函数 f0=0, f1=1, fn = fn-1+ fn-2
  • Hanoi 塔算法

参考资料

  • 北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾
个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学