栈 - 简书

栈

什么是栈

栈是一种线性的 后进先出 的数据结构，其规定了数据只能在栈顶进行操作，要么从栈顶压入数据，要么从栈顶弹出数据

生活中就有类似栈的例子，比如吃完饭，将盘子一个一个摞起来，然后洗盘子的时候，从摞起来的盘子中的顶部拿一个来洗，这就是类似栈的操作，先放的盘子在底部，后放的盘子在顶部，后放的盘子先被洗( 弹出 )

栈的操作的时间复杂度都是 O(1)，因为其只涉及在栈顶的压入或者弹出操作，不涉及别的额外的操作

内存中 '栈' 这块内存地址被用来 存储函数调用时的临时变量，每执行一个函数，就会将其临时变量装成一个栈帧入 '栈'，在其执行完毕之后，再将其所对应的栈帧出栈

function sum(a, b) {
  var sum = a + b;
  return sum;
}

var a = 1;
var b = 2;
sum(a, b);

栈帧

对于求值表达式，类似 3+2*1-5 这种，我们也可以通过栈来计算其结果
其步骤如下：

栈可以用来判断字符串中的括号是否对应，例如 '()'、'[]'、'{}'、')('，最后一个就是对应不上的

使用两个栈来保存浏览历史和后退操作

被点击的 url 入栈1，点击后退，栈1顶部的 url 出栈入栈2，点击前进，栈2顶部的 url 出栈入栈1，当栈1有新的 url 入栈时，清空栈2，相当于 栈2保存的是后退的操作记录

浏览器前进后退

内存中的堆栈和数据结构的堆栈是不一样的，内存中的堆栈是 真实的物理地址区域，数据结构的堆栈是抽象出来的数据存储结构，在内存物理地址上做了和逻辑数据结构一样的操作( 出栈，入栈... )，就将其类比称为对应的数据结构

其实用其它数据结构也可以，不过在函数嵌套调用时，栈最符合这种 后进先出 的逻辑，所以用栈是最好的选择。从调用函数进入被调用函数，对于数据只是作用域的变化，使用栈的话，被调用函数执行完毕之后出栈，正好回到调用函数的作用域

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。