08 | 栈：如何实现浏览器的前进和后退功能？

为什么函数调用要用“栈”来保存临时变量呢？用其他数据结构不行吗？ 其实，我们不一定非要用栈来保存临时变量，只不过如果这个函数调用符合后进先出的特性，用栈这种数据结构来实现，是最顺理成章的选择。 从调用函数进入被调用函数，对于数据来说，变化的是什么呢？是作用域。所以根本上，只要能保证每进入一个新的函数，都是一个新的作用域就可以。而要实现这个，用栈就非常方便。在进入被调用函数的时候，分配一段栈空间给这个函数的变量，在函数结束的时候，将栈顶复位，正好回到调用函数的作用域内。

内存中的堆栈和数据结构堆栈不是一个概念，可以说内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象的数据存储结构。 内存空间在逻辑上分为三部分：代码区、静态数据区和动态数据区，动态数据区又分为栈区和堆区。 代码区：存储方法体的二进制代码。高级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）控制代码区执行代码的切换。 静态数据区：存储全局变量、静态变量、常量，常量包括final修饰的常量和String常量。系统自动分配和回收。 栈区：存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。 堆区：new一个对象的引用或地址存储在栈区，指向该对象存储在堆区中的真实数据。

为什么函数调用要用“栈”来保存临时变量呢？用其他数据结构不行吗？ 其实，我们不一定非要用栈来保存临时变量，只不过如果这个函数调用符合后进先出的特性，用栈这种数据结构来实现，是最顺理成章的选择。 从调用函数进入被调用函数，对于数据来说，变化的是什么呢？是作用域。所以根本上，只要能保证每进入一个新的函数，都是一个新的作用域就可以。而要实现这个，用栈就非常方便。在进入被调用函数的时候，分配一段栈空间给这个函数的变量，在函数结束的时候，将栈顶复位，正好回到调用函数的作用域内。

关于这个浏览器的前进和后退，老师您说的是用两个栈实现，其实开篇我已经想到，但是，我还有一个很不错的解决思路，对于内存消耗可能会高点，但是时间复杂度也很低，就是使用双向链表，用 pre和next 来实现前进和后退

对于每次留下的思考题都希望老师在n（n>1）天后给出权威的答案，谢谢。 国庆在家里只看文档和听音频没有记录笔记，回去工作了，一定补上。个人认为本课题是最实惠的知识付费，没有之一。❤

王老师，”你应该可以看出来，这 K 次入栈操作，总共涉及了 K 个数据搬移，以及 K 次 simple-push 操作“-----文章中的这句话，我觉得应该是2K次入栈操作，前K次做了数据搬移(时间复杂度O(1))，第K+1次要扩容，对应的时间复杂度是O(k),后面的k-1时间复杂度是O(1),所以这2K次的操作平摊下来就是O(1)-----是这么理解么？我并不是想钻牛角尖，只是希望真正理解你说的这个概念哈，虽然结果是一样，但我想知道我想错了没有

想借此机会请教一个问题，同时也算是给大家的一道思考题。如果文中计算表达式的例子 涉及到小括号(默认小括号使用合法) 该如何处理呢？

请问老师，3+5*8-6的栈计算演示图的第5步和第6步中间是不是省略了一步40 3 + 啊？不然如果表达式是3+5*8/2-6的结果就不对了。谢谢您

看到有人问小括号的情况怎么办，我写了个JS的示例，抛砖引玉哈。 主要思路就是遇到小括号时，将小括号内的表达式提取出来，然后进行递归调用。 使用ES6写的，Git地址： https://github.com/taifu5522/ProblemSet

例子举得不恰当，一堆碟子是可以随意抽取的