【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 塔算法

参考资料

• 北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾