堆栈的基本了解

一、概述

1.1 大致目的

• 对计算机操作系统中的堆和栈的作用有一个初步的了解。（本篇）
• 对数据结构中的堆和栈有一个初步了解。（本篇）
• 理解 java 虚拟机中堆和栈等其他内存区域的作用和运行时的基本原理。（第三篇）
• 理解 java 中变量、对象、方法与堆、栈的关系。（第三篇）

1.2 堆栈

注意：
①我们有时候会遇到“堆栈”这种称呼，根据语义“堆栈”这种称呼无非等价以下两种说法：

1. 表示“堆”和“栈”的合称。
2. 表示栈。

②操作系统的堆和栈是指对内存进行操作和管理的一些方式这和数据结构中的堆和栈是有区别的。

二、计算操作系统中的栈(stack)

在计算机系统中，栈也可以称之为栈内存是一个具有动态内存区域, 存储函数内部（包括 main 函数）的局部变量和方法调用和函数参数值。我们需要知道:

1. 栈的基本性质
2. 栈帧的概念
3. 栈的存储形式及数据的存储和函数的调用。

2.1 栈的基本性质

①内存管理：
栈由编译器自动分配释放。
②栈中的内容存放
栈存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。满足：“先进后出”的原则存取，也就是位于栈内的元素，必须等到其上面 (对应的地址为较低的地址) 的数据或函数执行完成后，弹出后才可以进行下面的元素的操作。
③栈的结构：
栈的一端是固定的，另一端是浮动的。固定的一端是较高的地址，我们称栈顶。浮动的一端是较低的地址（最低到 0）随着元素或方法的加入栈顶指针会逐步地往下移动。所有的数据存入或取出，只能在浮动的一端（称栈顶）进行。（栈的生长方向是向下的，是向着内存地址减小的方向增长）
④栈的速度：
栈是由系统自动分配的，一般速度较快 (栈的速度高于堆的速度)
⑤申请大小的限制：
栈是向低地址扩展的，是一块连续的内存的区域。是栈顶的地址和栈的最大容量是系统预先规定好的，栈的大小是 2M（也有的说是 1M，总之是一个编译时就确定的常数 ) , 如果申请的空间超过栈的剩余空间时，将提示 overflow。因此，能从栈获得的空间较小。
⑥单片机中的栈：单片机应用中，栈是个特殊存储区，栈属于 RAM 空间的一部分，栈用于函数调用、中断切换时保存和恢复现场数据。栈中定义了一些操作，两个最重要的是 PUSH 和 POP。PUSH（入栈）操作：堆栈指针（SP）加 1，然后在堆栈的顶部加入一 个元素。POP（出栈）操作相反，出栈则先将 SP 所指示的内部 ram 单元中内容送入直接地址寻址的单元中（目的位置），然后再将堆栈指针（SP）减 1。这两种操作实现了数据项的插入和删除。

2.2 栈帧的概念

函数的每一次调用, 均会在调用栈 (call stack) 上维护一个独立的栈帧 (stack frame). 每个独立的栈帧一般包括:
①函数的返回地址和参数。
②临时变量: 包括函数的非静态局部变量以及编译器自动生成的其他临时变量。
③函数调用的上下文。
栈是从高地址向低地址延伸, 一个函数的栈帧用 ebp 和 esp 这两个寄存器来划定范围.ebp 指向当前的栈帧的底部,esp 始终指向栈帧的顶部;
ebp 寄存器又被称为帧指针(Frame Pointer);
esp 寄存器又被称为栈指针(Stack Pointer);

2.3 栈和函数的调用关系

下面以函数 P 内部调用函数 Q 为例：

①在函数 P 调用函数 Q 的过程，Q 在执行时，P 以及所有在向上追溯到 P 的调用链中的过程，都是被暂时挂起的。
②当 Q 运行时，它只需要为局部变量分配新的储存空间，或者设置另一个过程的调用。
③Q 返回时，任何它所分配的局部存储空间都可以被释放。当 P 调用 Q 时控制和数据信息会添加到栈尾，当 P 返回时，这些信息会被释放掉。
对于调用中栈帧的过程：
①当前正在执行的栈帧总是在栈顶，当过程 P 调用过程 Q 时，会把返回地址压入栈中，指明当 Q 返回时，要从 P 程序的哪个位置继续执行。并且这个 返回地址当作 P 的栈帧的一部分 。因为它存放的是与 P 相关的状态。
②Q 的代码会推展当前栈的边界，并分配它的栈帧所需的空间。这个空间中，Q 可以保存寄存器的值，分配局部变量空间，为它调用的过程分配参数
注意：并不是所有函数都学要栈帧的，比如不调用任何子函数的函数。

三、计算操作系统中的堆(heap)

3.1 堆的基本了解

①堆的内存管理：
堆是程序中一块预留的内存空间，可由程序自由使用，堆被程序申请使用的内存在被主动释放前一直有效。一般由程序员分配释放, 若程序员不释放, 对于堆来讲，释放工作由程序员手动管理，不及时回收容易产生内存泄露。程序结束时可能由操作系统回收。
②C 中对空间的申请： C 语言程序中通过头文件为“malloc.h”的库函数调用获得堆空间，关键字“malloc”以字节的方式动态申请堆空间，关键字“free”将堆空间归还给系统。
③堆的速度：有种说法是“栈是存放在一级缓存中的，而堆则是存放在二级缓存中的，堆的生命周期由虚拟机的垃圾回收算法来决定（并不是一旦成为孤儿对象就能被回收）。”所以调用这些对象的速度要相对来得低一些，故堆的速度慢于栈的速度。
④系统对堆空间的管理方式：我们了解下空闲链表法这种管理方式：：首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块内存空间中的首地址处记录本次分配的大小，这样，代码中的 delete 语句才能正确的释放本内存空间。另外，由于找到的堆结点的大小不一定正好等于申请的大小，系统会自动的将多余的那部分重新放入空闲链表中。
下部分描述参见: 程序中的三国天下：栈、堆、静态存储区:
分析：
假设每个节点下的内存都为 12byte、100byte、50byte….
当申请内存时，系统遍历空闲链表节点，查看所需内存大小与哪一个节点下内存大小最接近
到此节点下查找可用单元，查找到之后返回对应单元地址
在空闲链表管理法中，存在查找所需内存大小与哪一节点最接近的操作，这将导致 malloc 实际分配的内存可能会比请求的多。但我们不能依赖这种行为，因为在不同的系统中，对堆空间的管理方式可能是不同的。

3.2 堆和栈的对比

①按分配方式分：
栈：栈有两种分配方式：静态分配和动态分配
堆：在 C 中堆是动态分配和回收内存的，没有静态分配的堆。
（静态分配是系统编译器完成的，比如局部变量的分配.）
（动态分配是有 malloc 函数进行分配的，但是栈的动态分配和堆是不同的，它的动态分配也由系统编译器进行释放，不需要程序员手动管理）
②申请大小的限制
栈：栈是向低地址扩展的数据结构，是一块连续的内存的区域。
堆：堆是向高地址扩展的数据结构，是不连续的内存区域。堆获得的空间比较灵活，也比较大。
③效率：
栈：由系统自动分配，速度较快，不会产生内存碎片。
堆：在 C 中堆是由 malloc 分配的内存，速度比较慢，而且容易产生内存碎片，不过用起来较方便。
使用堆时，频繁的用 new/delete 必会造成内存空间的不连续, 导致造成大量碎片的产生, 降低程序效率。而栈则不会有这个问题, 因为栈是先进后出的队列, 它们是如此的一一对应, 以至于永远都不可能有一个内存块从栈中间弹出。

四、数据结构中的堆、栈

我们在此只是了解下基本的数据结构，它们的语言实现、深入了解请参考其他资料。

4.1 栈

①定义：栈是限制插入和删除只能在一个位置上进行的线性表。该位置即为表的末端也叫栈顶（top）栈又叫作“先进后出表”。
②基本操作：栈的基本操作包括：push(进栈)和 pop（出栈）。
③栈的实现：栈是一个线性表，所以栈可以用数组或者链表来实现（即栈可以由逻辑上连续的 ADT 实现）。在 java 中大部分栈的实现是使用 ArrayList 或者 LinkedList。
④性能：
索引：O(n)
查找：O(n)
插入：O(1)
删除：O(1)

4.2 堆

①定义： 堆是一种特别的树状数据结构。堆要满足以下特征：“给定堆中任意节点 P 和 C，若 P 是 C 的母节点，那么 P 的值会小于等于（或大于等于）C 的值”。
逻辑定义
①定义：

堆是完全二叉树，完全二叉树不一定是堆
②堆的实现： 通过构造 二叉堆 （binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。这种数据结构具有以下性质：
①任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）。
②堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。
③将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
最大堆：若母节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）。
最小堆：若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。
在堆中最顶端的那一个节点，称作根节点（root node），根节点本身没有母节点（parent node）。
④二叉堆的性能：
索引：O(log(n))
查找：O(log(n))
插入：O(log(n))
删除：O(log(n))
删除最大值 / 最小值：O(1)

④应用：堆排序、优先队列。

参考资料

• “堆栈”的有关笔记
• 维基百科
• 栈和堆的区别
• 栈、堆、静态存储区
• 深入理解 java 虚拟机
• 深入理解计算机操作系统