思维导图
『 栈 』 是计算机存储中一种常见的简单数据结构
对 『 栈 』结构常进行的数据操作我们常称为 『 出栈 』（ 读取或是删除数据 ） 或是 『 入栈 』（ 插入数据 ）
有个很形象的比喻 ，把 『 栈 』看成是一个子弹夹将数据压入和弹出，恰好的表达了『 栈 』的特性 『 后进先出 ， 先进后出 』，而『 递归 』的使用就是和 『 栈 』紧密相连。（ 递归 ： 不断调用函数自己 。）如何理解 栈这是 王争 老师在 《 数据结构与算法之美 》 专栏中 『 栈：如何实现浏览器的前进和后退功能？ 』稍作修改变成的 C# 代码 。（ 两门语言因为历史原因惊人的相似 ， 却因开源和闭源的问题而有了极大的差别的开发者数量 ）// 基于数组实现的顺序栈
public class ArrayStack
{
private String[] items; // 定义一个数组
private int count; // 栈中元素个数
private int n; // 栈的大小
// 初始化数组，申请一个大小为 n 的数组空间
public ArrayStack(int n)//构造函数 ， 每次实例化对象时需传入参数 n
{
this.items = new String[n];// 初始化栈数组的长度
this.n = n; // 初始化私有变量 n 的值 ， this.n 是指类中的变量 n
this.count = 0; // 初始化 count 计数器的值为
}
// 入栈操作
public bool push(String item)
{
// 数组空间不够了，直接返回 false，入栈失败。
if (count == n) return false;
// 将 item 放到下标为 count 的位置，并且 count 加一
items[count] = item;
++count;
return true;
}
// 出栈操作
public String pop()
{
// 栈为空，则直接返回 null
if (count == 0) return null;
// 返回下标为 count-1 的数组元素，并且栈中元素个数 count 减一
String tmp = items[count - 1];
--count;
return tmp;
}
}
这是一个 C# 实现的 栈 类 ，表达的是数组实现的『 顺序栈 』，完全按照数据的录入顺序来执行压栈 。
代码解读 ：
count 为计数器 ， 但数组索引从 0 开始 ， 所以每次录入数据之后 计数器 +1 ，而最后一个元素则为 items[ count-1 ] 。
而 栈 的结构也可以用链表来表示 ， 实际上就是在链表头结点插入数据 ， 又因为链表的从『 首到尾 』遍历特性每次从 起始位 也就是首结点开始读取数据 。 相比较数组实现栈 ， 链表的实现更有灵活性， 便于动态扩充数据长度 ， 而数组相对而言会节省内存， 灵活性稍差 。（ 如果是动态数组 ， 则会因为动态扩容增加算法的时间复杂度 ， 在平摊时间复杂度分析法中 动态数组实现栈也是 O( 1 ) ，因为只有一种特殊情况 数据长度超出初始数组长度时执行扩容操作 ， 特殊情况的时间复杂度为 O( n ) ，执行了一次数据拷贝 ）栈在函数中的应用函数总是被嵌套 ， 例如 其他函数总是被 main 函数（ 主函数 ）所嵌套 ， 可以用『 栈 』的定义来思考函数嵌套。/* 递归实现累加 ， 假设 n 一定为正整数 */
int recursion(int n)
{
if (n == 1)
return 1;
else
n=(n+recursion(n-1));
return n;
}
在这个累加递归函数中 ，recursion 函数被不断调用 ， 直到 n == 1 ；因为 『 栈 』的数据操作是 『 后进先出 』所以在计算机中 ， 依次执行的是 1+ 2 + 3 …. + n ，而其他被嵌套的函数也是大致这样的过程 。先执行最里层的函数将数据不断返回到最外层 ，最终产生我们所需要的结果。==栈的结构未必是计算机执行函数嵌套必然的选择 ， 但是这样的结构更利于我们去理解 ，因为递归的思想符合我们人思考的逻辑 。也符合函数执行『 后进先出 』的特性。将二者联系一起考虑是一种好的方式。==计算机中通过栈来实现算术运算王争老师在课中将计算机执行算术运算用 『 栈 』的思想给我们讲解了一下。
例如 1 + 2 × 3 - 4
计算机执行运算的过程中将 数字 和 运算符分开存储在两个栈里。
先按输入顺序存放 ， 在读取到 × 号等运算级别较高的算术运算符时 ， 根据算术运算符将运算符 升到栈顶（ 即执行 出栈 、 出栈 的一端），相应的 ，数字栈中对应的两端的数据上升。（ 王争老师数字这一块的操作未指出，如有误导请 指正 ）
按照『 栈 』思想运算顺序应当为 ① 2*3 ② 6-4 ③ 2+1
发表于 2018-12-10 13:37
|
发表于 2018-12-10 20:41
