• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(2.1)栈和栈的应用:撤销操作和系统栈

极客笔记 Geekerstar 12个月前 (05-08) 394次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

栈Stack

  • 栈也是一种线性结构
  • 相比数组来说,栈对应的操作是数组的子集
  • 只能从一端添加元素,也只能从同一端取出元素
  • 这一端称为栈顶

  • 栈是一种后进先出的数据结构(Last In First Out即LIFO)

无处不在的Undo(撤销)操作

比如在文本编辑的过程中,如果我们输入一句话或修改一个内容。

修改以后发现之前的修改可能有问题,我想撤销到修改前的状况,就要执行Undo操作。

对于编辑器来说,Undo操作的原理是什么呢?

其实就是靠一个栈来进行操作的,举一个简单的例子,比如输入一句话,其中第一个词“沉迷”,对于编辑器来说,相当于把“沉迷”放进一个栈中。

然后又打了两个字“学习”,那么编辑器的栈就记录下“学习”两个字,这个记录操作是把“学习”两个字压入栈中。

然后输入的是“无法”,不过一不小心打成了“不法”,那么编辑器也会将这两字压入栈中。

此时我意识到打错了,想撤销这一操作,按退格也好,Ctrl+Z也好,编辑器做的事情就行从这个栈中拿出栈顶的元素。

通过栈顶的元素来确认一下最近的操作是什么?

发现原来是输入了“不法”两个字,撤销操作要做的就是把“不法”两个字给删掉,也就是出栈,这就是撤销的原理解析。

程序调用所使用的系统栈

接下来这个例子更加重要,如果大家真正的非常深入理解了,会对计算机程序的一些运行机制,比如递归的机制有更加深入的理解。

在计算机程序调用的过程中,会出现这种情况:一个逻辑的中间发生中止,然后跳到另外一个逻辑去执行,这就是所谓的子函数调用过程。

在这个过程中,计算机就需要使用一个叫做“系统栈”的数据结构来记录我们程序的调用过程。

假设有三个函数分别叫A(),B(),C(),对于A()这个函数在程序执行到一半的时候要调用一个子函数B(),对于B()这个函数在执行到一半的时候要调用一个子函数C(),C()就直接运行完了不需要调子函数。

如上所分析的那样,当A()中调用B()时,系统栈中将记录一个信息,我们叫它A2,意思是之前我们的程序执行到A这个函数的第二行了,在这里进行了中断,现在开始执行B()。

同理,当B()中执行到第二行调用C(),此时系统栈压入一个信息叫B2。接着执行C(),当C()执行完了计算机会遇到一个问题,此时该执行谁呢?

此时就要看一下系统栈了,位于栈顶的元素是B2。

此时系统栈B2出栈,执行B()剩余的部分。

这样系统栈就帮我们找到了上一次执行的位置,以此类推,B()执行完后,A2出栈,继续回去执行A()后面的部分。

这就是在编程的时候,在进行子过程调用的时候,当一个子过程执行完成之后可以自动回到上层调用中断的位置继续执行下去的原因。

因为有这样一个“系统栈”来记录上一次执行中断的点,通过这样一个例子,我们通过栈这样一个看似简单的数据结构,解决了计算机领域中非常复杂的一个问题就是子过程调用在我们编译器内部是如何运行实现的。

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(2.1)栈和栈的应用:撤销操作和系统栈
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00