【文件属性】：
文件名称：栈与递归-web服务稳定性测试 负载测试 可靠性测试 测试报告
文件大小：10.35MB
文件格式：PDF
更新时间：2024-07-30 10:59:06
数据结构 邓俊辉 清华大学 mooc学堂在线 教材
§4.2 栈不逑弻 第4章 栈不队列
8888
4.1.3 Stack模板类
既然栈可视作序列的特例，故只要将栈作为向量的派生类，即可利用C++的继承机制，基于
2.2.3节定义的向量模板类实现栈结构。当然，这里需要按照栈的习惯，对各接口重新命名。
按照表4.1所列的ADT接口，可描述并实现Stack模板类如代码4.1所示。
1 #include "../Vector/Vector.h" //以向量为基类，派生出栈模板类
2 template class Stack: public Vector { //将向量癿首/末端作为栈底/顶
3 public: //size()、empty()以及其它开放接口，均可直接沿用
4 void push(T const& e) { insert(size(), e); } //入栈：等效亍将新元素作为向量癿末元素揑入
5 T pop() { return remove(size() - 1); } //出栈：等效亍初除向量癿末元素
6 T& top() { return (*this)[size() - 1]; } //叏顶：直接迒回向量癿末元素
7 };
代码4.1 Stack模板类
既然栈操作都限制于向量的末端，参与操作的元素没有任何后继，故由2.5.5节和2.5.6节
的分析结论可知，以上栈接口的时间复杂度均为常数。
套用以上思路，也可直接基于3.2.2节的List模板类派生出Stack类（习题[4-1]）。
§4.2 栈与递归
习题[1-17]指出，递归算法所需的空间量，主要决定于最大递归深度。在达到这一深度的
时刻，同时活跃的递归实例达到最多。那么，操作系统具体是如何实现函数（递归）调用的？如
何记录调用与被调用函数（递归）实例之间的关系？如何实现函数（递归）调用的返回？又是如
何维护同时活跃的所有函数（递归）实例的？所有这些问题的答案，都可归结于栈。
4.2.1 函数调用栈
图4.3 函数调用栈实例：主函数main()调用funcA()，funcA()调用funcB()，funcB()再自我调用
