04|栈:函数调用的秘密究竟是什么?
黄清昊
该思维导图由 AI 生成,仅供参考
你好,我是微扰君。
目前为止,我们已经介绍了 STL 里的大部分序列式容器,包括 vector、deque 和 list,也对应着数组、队列和链表这几种基础数据结构;今天我们来学习最后一种常用的线性数据结构,栈。
栈这个词,相信每一个研发同学在学习编程的过程中都会经常听到。不仅仅是因为栈本身就是一种基础的、常见的数据结构,更因为栈在计算机世界里起着举足轻重的作用。
在编程语言中,栈除了作为一种常用的数据结构,也常常用来表示一种叫做“调用栈”的概念,它是编程语言之所以能实现函数调用的关键所在。而在内存分配中,栈也表示一种内存分配的区域,和内存中的堆区是一种相对的概念。
栈区是有结构和固定大小的,区块按照次序存放,每个线程独占一个栈区,总的大小也是事先确定的;而堆区则没有固定的大小,数据可以随意存放。我们常常听到的 stack overflow 错误,也就是栈溢出错误,就是指程序在运行时,存放在栈上的数据已经多于栈区的容量,产生了容量不足的错误。相信说到这,你就更加明白为什么说栈相比于其他数据结构更经常被听到了吧。
其实无论是调用栈还是内存中的栈区,这两种含义都和栈数据结构的 LIFO 特性有关。如果你已经有了充分的背景知识,可以先想想这是为什么?
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文介绍了栈的基本特性、STL中的实现以及在函数调用中的应用。栈是一种常见的线性数据结构,具有LIFO(后进先出)的特性,类似于电梯的运行方式。在计算机编程中,栈在函数调用中扮演重要角色,利用其LIFO特性来管理函数调用的顺序。文章以JavaScript语言为例,通过函数调用的过程展示了调用栈的状态变化,深入探讨了函数上下文的产生与销毁,以及栈帧的作用。通过使用栈,实现了函数调用这一编程语言中最基础的核心能力。此外,文章还提到了STL中栈的实现方式,指出list、vector、deque都可以用来做stack的底层容器,但STL选择了用deque来实现栈。最后,留下了一个问题,探讨了STL选择deque实现栈的原因以及与vector实现的差异。整体而言,本文通过具体的例子和技术细节,帮助读者深入了解栈的内部机制和在计算机编程中的重要作用。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《业务开发算法 50 讲》,新⼈⾸单¥59
《业务开发算法 50 讲》,新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(3)
- 最新
- 精选
- 友感觉用deque主要是扩容逻辑方便 直接复用
作者回复: 友同学非常优秀,经常在评论区留言呀! vector也可以复用逻辑哦。 我理解主要好的地方在于: vector扩容的时候需要整体拷贝数据,动作比较大;deque在扩容的时候则只需要拷贝map中的数据即可。
2021-12-1828 - Geek_a8ce05说的太深了,估计劝退很多人
作者回复: 哈哈哈 还好啦 调用栈还是很值得掌握的;可以去看看CSAPP的相关章节哦~
2022-04-123 - Paul Shan如果用vector实现栈,内存管理更简单,省去了Deque存储指针的开销,结构更紧凑,均摊复杂度和Deque是一样的,都是O(1). Deque因为内存管理分了两层,带来了两个好处。第一个好处是极端情况下的高效。虽然均摊复杂度是一样的,但是vector扩容的时候,整体容量要扩充两倍,这一个时刻的效率会很差。Deque分了两层,第一层扩容的时候也要加倍,但是因为第一层管理的是数据块,这个加倍带来的影响小很多。第二个好处是,对大块内存的需求降低。Deque分了两层,只要求第一层是连续内存,第二层可以利用内存碎片。我想正是因为这两个优点让STL采用Deque作为默认Stack实现。
作者回复: 总结的非常不错
2021-12-1832
收起评论