王争数据结构与算法学习笔记-栈

浏览器的前进后退功能的实现使用到了栈这种数据结构。

当依次访问了页面a，b，c，然后后退的时候又可以重新返回到页面b、a，访问的过程属于入栈的功能，后退的过程是出栈的功能。

理解“栈”

栈是一种操作受限的线性表，只允许在一端进行插入和删除操作。

为什么需要“栈”？

为何需要单独设计一个数据结构，而不是直接使用链表或者数组来代替呢？

数据结构是对于不同应用场景的抽象，数组和链表用于实现栈的功能，暴露了过多的端口，使用起来不可控，容易出错。

栈的复杂度？

不论是链式栈还是顺序栈，其时间复杂度均为 $O(1)$ （针对入栈和出栈操作），空间复杂度也为 $O(1)$ 。

空间复杂度不是 $O(n)$ 吗？

我们所说的空间复杂度指的是除去本来需要的、用于存储数据的存储空间之外，算法运行起来所需要的额外空间。栈所需要的额外空间为个位数，所以大 $O$ 表示法表示空间复杂度为 $O(1)$ 。

支持动态扩容的顺序栈

对于数组实现的栈，如果数据量超过数组一开始申请的空间就会受限，对于链表实现的栈，每一个结点多出一个“next”指针，内存消耗过多，所以为了解决这个问题，我们需要设计一个支持动态扩容的栈。

对于动态扩容的数组而言，当剩余的容量不够的时候，再申请一块更大的空间，将原来的数据拷贝到新数组中，就实现了动态扩充。所以要实现动态扩容的顺序栈就需要在一个动态扩容的数组上操作。

那么支持动态扩容的顺序栈的时间复杂度和空间复杂度如何分析呢？

对于出栈操作来说，不会涉及到数据的转移操作，所以时间复杂度仍然为 $O(1)$ ，对于插入操作就不一样了，如果剩余的空间可以容下需要插入的数据，则时间复杂度为 $O(1)$ ，如果空间不够，则需要申请一块新的内存，并将之前的数据全部转移到新的数组中，这就涉及到移动数据所花费的时间了，这样一来时间复杂度就是 $O(n)$ 。

所以对于入栈操作来讲，最好的情况下时间复杂度为 $O(1)$ ，最坏的时间复杂度为 $O(n)$ ，接下来给定下面几点假设来分析平均时间复杂度：

栈空间不够时，申请原来数组长度的两倍；
假设只有入栈操作没有出栈操作；
不涉及内存搬移的入栈操作为simple-push操作，时间复杂度为 $O(1)$ 。

这里的平均时间复杂度的分析使用均摊时间复杂度。对于均摊时间复杂度，在之前的时间空间复杂度分析中有讲到。对于需要重新申请数组空间，并将数据转移到新数组中的操作场景而言，假设数组的长度为n，那么前n个数据入栈的时间复杂度为 $O(1)$ ，而第n+1个数据入栈的时候栈满，需要转移数据到新的数组中，时间复杂度为 $O(n)$ 。此时容量为2n的新栈剩余的容量为n-1，所以剩余n-1个数据入栈的时间复杂度均为 $O(1)$ 。最后，将第n+1个数据上的 $O(n)$ 时间复杂度给均摊到其他的结点，所以均摊时间复杂度就变成了 $O(1)$ 。

均摊时间复杂度一般都等于最好情况下的时间复杂度。

栈在函数调用中的应用

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

栈在表达式求值中的应用

栈在括号匹配中的应用

思考

为什么函数要调用栈来保存临时变量呢？使用其他的数据结构不行吗？

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

内存中的堆栈和数据结构中的栈不是一个概念，内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象的数据存储结构。

内存空间在逻辑上分为三个部分：代码区、静态数据区和动态数据区，动态数据区又分为栈区和堆区。

代码区：存储方法体的二进制代码。高级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）控制代码区执行代码的切换。

静态数据区：存储全局变量、静态变量、常量，常量包括final修饰的常量和String常量。系统自动分配和回收。

栈区：存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。

堆区：new一个对象的引用或地址存储在栈区，指向该对象存储在堆区中的真实数据。

由于在JVM中的栈实现了先进后出的逻辑功能，所以叫做“栈”也可以理解。
内存中的堆栈？

堆是一个内存空间，这个内存控件可以由程序员分配和释放，当然部分语言自带 GC（ Garbage Collection 垃圾回收），部分堆内存可以由 GC 回收。这里千万要注意，这里说的堆和数据结构里面说的堆不是同一个概念。堆是程序在运行的时候请求操作系统分配给自己内存。由于从操作系统管理的内存分配，所以在分配和销毁时都要占用时间，因此用堆的效率相对栈来说略低。但是堆的优点在于，编译器不必知道要从堆里分配多少内存空间，也不必知道存储的数据要在堆里停留多长的时间，因此用堆保存数据时会得到更大的灵活性。因此，为达到这种灵活性，在堆里分配存储空间时会花掉相对更长的时间，这也是效率低于栈的原因。

栈是由编译器自动分配和释放的，存放函数的参数值，局部变量的值等。也请注意，这里说的栈不是数据结构中的栈。栈的优势是，存取速度比堆要快，仅次于寄存器，栈数据可以共享。但缺点是，存在栈中的数据大小与生存期必须是确定的，缺乏灵活性。

在C#中，数据类型有两大类型 —— 值类型 和 引用类型，内置值类型指的是 int、float、bool、double 等等，引用类型大概我们学 C 语言的时候学到的指针类型。值类型变量声明后，不管是否已经赋值，编译器为其分配内存。然而引用类型当声明一个变量时，只在栈中分配一小片内存用于容纳一个地址，而此时并没有为其分配堆上的内存空间。当使用 new 创建一个类的实例时，这时候会分配堆上的空间，并把堆上空间的地址保存到栈上分配的小片空间中。说通俗一点，堆上存放的是我们声明出来的实例对象，当我们需要访问这个实例对象的时候，我们找到它的方法是先找到变量对应在栈上的内存，然后通过栈上存放的数据，我们才能找到其真正的实例在堆的什么位置。

即使在堆上面，现代化的高级语言也会有一些桎梏让你并不能随意的，随时随地的释放你认为可以释放的内存，很多语法概念中都蕴含了“栈”的概念。

例如，一个C++的对象X，他有数据成员a和b, 现在我知道我不再使用X.a了，但是我还会使用X.b，有没有办法去“浅释放”X.a所占的sizeof(X.a)的内存呢？抱歉不行，你只能先释放X，在释放X的过程中去释放X.a和X.b（不能只释放一个）。而且这和X在堆还是在栈上分配没有任何关系。

换而言之，面向对象语言中的“对象”，从他的成员的构建过程中蕴含了“栈的概念”，所以他的释放依然受制于栈的先入后出的规则影响。类似于默认生成的析构函数总是先调用对象的析构函数再去遍历调用成员的析构函数一样，只是可以把这个栈看成分叉栈，或者树的先序遍历。

Reference:

https://zhuanlan.zhihu.com/p/45597548

https://www.zhihu.com/question/281940376/answer/424990646
什么是装箱什么是拆箱？

装箱实际上是将值类型转换为引用类型，而拆箱是将引用类型转换为值类型。再说的透彻点，实际上装箱拆箱就是栈内存和堆内存的来回拷贝和赋值，这不仅仅浪费性能，而且还会造成没必要的 GC。因此，能避免 “装箱”、“拆箱” 操作的就尽量避免。

Reference: https://zhuanlan.zhihu.com/p/45597548