栈，是一种“操作受限”的线性表，只允许在一端插入和删除数据。先进后出是它的最大特点。
为什么需要这种操作受限的线性表？直接使用数组或者链表不好吗？
理由是，数组和链表确实可以代替栈完成我们需要的功能，但是我们要知道，特定的数据结构是对特定场景的抽象，而且，数组或者链表暴露了太多的操作接口，从后台开发工程师的角度来看，没有用到的功能，就不该给用户暴露，否则，只会失控，引来问题。
栈的实现
栈可以用数组和链表实现。数组实现的栈叫顺序栈，链表实现的栈叫链式栈。特别要注意的是，顺序栈的动态扩容，应用平摊分析法，最终分析出插入的时间复杂度仍是 O(1)。
栈的应用
-
函数调用栈
操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈。当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。 -
栈在函数表达式中的应用
为了方便解释，我们将算术表达式简化为只包含加减乘除四则运算。
然后编译器通过使用两个栈，一个保存操作数的栈，另一个保存运算符的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶符号比较。
如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。 -
栈在括号匹配中的应用
我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则讲其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。
当所有括号都扫描完成之后，如果栈为空，则说明字符串是合法格式；否则，说明有未匹配的左括号，为非法格式。
课后思考
- 我们在讲栈的应用时，讲到用函数调用栈来保存临时变量，为什么函数调用要用“栈”来保存临时变量呢？其他数据结构不行吗？
特定数据结构是特定应用场景的抽象。
函数调用的顺序，符合先进者后出，后进者先出的特点，还有函数中调用函数，也是这样，先开始执行的函数，必须等到内部调用的其他函数执行完毕，该函数才能执行结束。
比如函数中的局部变量的生命周期的长短，是先定义的局部变量生命周期长，后定义的局部变量生命周期短。
- 我们都知道，JVM 内存管理中有个“堆栈”的概念。栈内存用来存储局部变量和方法调用，堆内存用来存储 Java 中的对象。那么 JVM 里面的“栈”跟我们这里说的“栈”是不是一回事呢？如果不是，那它又为什么叫做“栈”呢？
内存中的堆栈和数据结构堆栈不是一个概念。内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象的数据结构。
内存空间在逻辑上分为三部分：代码区、静态数据区和动态数据区。动态数据区又分为栈区和堆区。
代码区：存储方法体的二进制代码。高级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）控制代码区执行代码的切换。
静态数据区：存储全局变量、静态变量、常量，常量包括 final 修饰的常量和 String 常量。系统自动分配和回收。
栈区：存储方法的形参、局部变量、返回值。由系统自动分配和回收。
堆区：new 操作符创建的一个对象的引用地址存储在栈区，指向该对象存储在堆区中的真实数据。
网友评论