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
收起评论
