关于c++:cc后台开发必知堆与栈的区别

堆（Heap）与栈（Stack）是开发人员必须面对的两个概念，在了解这两个概念时，须要放到具体的场景下，因为不同场景下，堆与栈代表不同的含意。个别状况下，有两层含意：
（1）程序内存布局场景下，堆与栈示意两种内存治理形式；
（2）数据结构场景下，堆与栈示意两种罕用的数据结构。

1. 程序内存分区中的堆与栈

1.1 栈简介

栈由操作系统主动调配开释，用于寄存函数的参数值、局部变量等，其操作形式相似于数据结构中的栈。参考如下代码：

int main() {
    int b;                // 栈
    char s[] = "abc";     // 栈
    char *p2;            // 栈
}

其中函数中定义的局部变量依照先后定义的程序顺次压入栈中，也就是说相邻变量的地址之间不会存在其它变量。栈的内存地址成长方向与堆相同，由高到底，所以后定义的变量地址低于先定义的变量，比方下面代码中变量 s 的地址小于变量 b 的地址，p2 地址小于 s 的地址。栈中存储的数据的生命周期随着函数的执行实现而完结。

1.2 堆简介

堆由开发人员调配和开释，若开发人员不开释，程序完结时由 OS 回收，调配形式相似于链表。参考如下代码：

int main() {// C 中用 malloc() 函数申请
    char* p1 = (char *)malloc(10);
    cout<<(int*)p1<<endl;        // 输入：00000000003BA0C0
    
    // 用 free() 函数开释
    free(p1);
   
    // C++ 中用 new 运算符申请
    char* p2 = new char[10];
    cout << (int*)p2 << endl;        // 输入：00000000003BA0C0
    
    // 用 delete 运算符开释
    delete[] p2;}

其中 p1 所指的 10 字节的内存空间与 p2 所指的 10 字节内存空间都是存在于堆。堆的内存地址成长方向与栈相同，由低到高，但须要留神的是，后申请的内存空间并不一定在先申请的内存空间的前面，即 p2 指向的地址并不一定大于 p1 所指向的内存地址，起因是先申请的内存空间一旦被开释，后申请的内存空间则会利用先前被开释的内存，从而导致先后调配的内存空间在地址上不存在先后关系。堆中存储的数据若未开释，则其生命周期等同于程序的生命周期。

对于堆上内存空间的调配过程，首先应该晓得操作系统有一个记录闲暇内存地址的链表，当零碎收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆节点，而后将该节点从闲暇节点链表中删除，并将该节点的空间调配给程序。另外，对于大多数零碎，会在这块内存空间中的首地址处记录本次调配的大小，这样，代码中的 delete 语句能力正确地开释本内存空间。因为找到的堆节点的大小不肯定正好等于申请的大小，零碎会主动地将多余的那局部从新放入闲暇链表。

1.3 堆与栈区别

堆与栈实际上是操作系统对过程占用的内存空间的两种治理形式，次要有如下几种区别：
（1）治理形式不同。栈由操作系统主动调配开释，无需咱们手动管制；堆的申请和开释工作由程序员管制，容易产生内存透露；

（2）空间大小不同。每个过程领有的栈的大小要远远小于堆的大小。实践上，程序员可申请的堆大小为虚拟内存的大小，过程栈的大小 64bits 的 Windows 默认 1MB，64bits 的 Linux 默认 10MB；

（3）成长方向不同。堆的成长方向向上，内存地址由低到高；栈的成长方向向下，内存地址由高到低。

（4）调配形式不同。堆都是动态分配的，没有动态调配的堆。栈有 2 种调配形式：动态调配和动态分配。动态调配是由操作系统实现的，比方局部变量的调配。动态分配由 alloca 函数进行调配，然而栈的动态分配和堆是不同的，他的动态分配是由操作系统进行开释，无需咱们手工实现。

（5）调配效率不同。栈由操作系统主动调配，会在硬件层级对栈提供反对：调配专门的寄存器寄存栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比拟高。堆则是由 C /C++ 提供的库函数或运算符来实现申请与治理，实现机制较为简单，频繁的内存申请容易产生内存碎片。显然，堆的效率比栈要低得多。

（6）寄存内容不同。栈寄存的内容，函数返回地址、相干参数、局部变量和寄存器内容等。当主函数调用另外一个函数的时候，要对以后函数执行断点进行保留，须要应用栈来实现，首先入栈的是主函数下一条语句的地址，即扩大指针寄存器的内容（EIP），而后是以后栈帧的底部地址，即扩大基址指针寄存器内容（EBP），再而后是被调函数的实参等，个别状况下是依照从右向左的程序入栈，之后是被调函数的局部变量，留神动态变量是寄存在数据段或者 BSS 段，是不入栈的。出栈的程序正好相同，最终栈顶指向主函数下一条语句的地址，主程序又从该地址开始执行。堆，个别状况堆顶应用一个字节的空间来寄存堆的大小，而堆中具体寄存内容是由程序员来填充的。

从以上能够看到，堆和栈相比，因为大量 malloc()/free()或 new/delete 的应用，容易造成大量的内存碎片，并且可能引发用户态和外围态的切换，效率较低。栈相比于堆，在程序中利用较为宽泛，最常见的是函数的调用过程由栈来实现，函数返回地址、EBP、实参和局部变量都采纳栈的形式寄存。尽管栈有泛滥的益处，然而因为和堆相比不是那么灵便，有时候调配大量的内存空间，次要还是用堆。

无论是堆还是栈，在内存应用时都要避免非法越界，越界导致的非法内存拜访可能会捣毁程序的堆、栈数据，轻则导致程序运行处于不确定状态，获取不到预期后果，重则导致程序异样解体，这些都是咱们编程时与内存打交道时应该留神的问题。

须要 C /C++ Linux 高级服务器架构师学习材料后盾加群 812855908（包含 C /C++，Linux，golang 技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg 等）

2. 数据结构中的堆与栈

数据结构中，堆与栈是两个常见的数据结构，了解二者的定义、用法与区别，可能利用堆与栈解决很多理论问题。

2.1 栈简介

栈是一种运算受限的线性表，其限度是指只仅容许在表的一端进行插入和删除操作，这一端被称为栈顶（Top），绝对地，把另一端称为栈底（Bottom）。把新元素放到栈顶元素的下面，使之成为新的栈顶元素称作进栈、入栈或压栈（Push）；把栈顶元素删除，使其相邻的元素成为新的栈顶元素称作出栈或退栈（Pop）。这种受限的运算使栈领有“先进后出”的个性（First In Last Out），简称 FILO。

栈分程序栈和链式栈两种。栈是一种线性构造，所以能够应用数组或链表（单向链表、双向链表或循环链表）作为底层数据结构。应用数组实现的栈叫做程序栈，应用链表实现的栈叫做链式栈，二者的区别是程序栈中的元素地址间断，链式栈中的元素地址不间断。

栈的构造如下图所示：

栈的基本操作包含初始化、判断栈是否为空、入栈、出栈以及获取栈顶元素等。上面以程序栈为例，应用 C++ 给出一个简略的实现。

#include<stdio.h>
#include<malloc.h>

#define DataType int
#define MAXSIZE 1024
struct SeqStack {DataType data[MAXSIZE];
    int top;
};

// 栈初始化, 胜利返回栈对象指针，失败返回空指针 NULL
SeqStack* initSeqStack() {SeqStack* s=(SeqStack*)malloc(sizeof(SeqStack));
    if(!s) {printf("空间有余 n");
        return NULL;
    } else {
        s->top = -1;
        return s;
    }
}

// 判断栈是否为空
bool isEmptySeqStack(SeqStack* s) {if (s->top == -1)
        return true;
    else
        return false;
}

// 入栈，返回 - 1 失败，0 胜利
int pushSeqStack(SeqStack* s, DataType x) {if(s->top == MAXSIZE-1)
    {return -1;// 栈满不能入栈} else {
        s->top++;
        s->data[s->top] = x;
        return 0;
    }
}

// 出栈，返回 - 1 失败，0 胜利
int popSeqStack(SeqStack* s, DataType* x) {if(isEmptySeqStack(s)) {return -1;// 栈空不能出栈} else {*x = s->data[s->top];
        s->top--;
        return 0;
    }
}

// 取栈顶元素，返回 - 1 失败，0 胜利
int topSeqStack(SeqStack* s,DataType* x) {if (isEmptySeqStack(s))
        return -1;    // 栈空
    else {*x=s->data[s->top];
        return 0;
    }
}

// 打印栈中元素
int printSeqStack(SeqStack* s) {
    int i;
    printf("以后栈中的元素:n");
    for (i = s->top; i >= 0; i--)
        printf("%4d",s->data[i]);
    printf("n");
    return 0;
}

//test
int main() {SeqStack* seqStack=initSeqStack();
    if(seqStack) {
        // 将 4、5、7 别离入栈
        pushSeqStack(seqStack,4);
        pushSeqStack(seqStack,5);
        pushSeqStack(seqStack,7);
        
        // 打印栈内所有元素
        printSeqStack(seqStack);
        
        // 获取栈顶元素
        DataType x=0;
        int ret=topSeqStack(seqStack,&x);
        if(0==ret) {printf("top element is %dn",x);
        }
        
        // 将栈顶元素出栈
        ret=popSeqStack(seqStack,&x);
        if(0==ret) {printf("pop top element is %dn",x);
        }
    }
    return 0;
}

运行下面的程序，输入后果：

以后栈中的元素:
   7   5   4
top element is 7
pop top element is 7

2.2 堆简介

2.2.1 堆的性质

堆是一种罕用的树形构造，是一种非凡的齐全二叉树，当且仅当满足所有节点的值总是不大于或不小于其父节点的值的齐全二叉树被称之为堆。堆的这一个性称之为堆序性。因而，在一个堆中，根节点是最大（或最小）节点。如果根节点最小，称之为小顶堆（或小根堆），如果根节点最大，称之为大顶堆（或大根堆）。堆的左右孩子没有大小的程序。上面是一个小顶堆示例：

堆的存储个别都用数组来存储堆，i 节点的父节点下标就为(i – 1) / 2 (i – 1) / 2(_i_–1)/2。它的左右子节点下标别离为 2 ∗ i + 1 2 i + 12∗_i_+1 和 2 ∗ i + 2 2 i + 22∗_i_+2。如第 0 个节点左右子节点下标别离为 1 和 2。

2.2.2 堆的基本操作

（1）建设
以最小堆为例，如果以数组存储元素时，一个数组具备对应的树示意模式，但树并不满足堆的条件，须要重新排列元素，能够建设“堆化”的树。

（2）插入
将一个新元素插入到表尾，即数组开端时，如果新形成的二叉树不满足堆的性质，须要重新排列元素，下图演示了插入 15 时，堆的调整。

（3）删除。
堆排序中，删除一个元素总是产生在堆顶，因为堆顶的元素是最小的（小顶堆中）。表中最初一个元素用来填补空缺地位，后果树被更新以满足堆条件。

2.2.3 堆操作实现

（1）插入代码实现
每次插入都是将新数据放在数组最初。能够发现从这个新数据的父节点到根节点必然为一个有序的数列，当初的工作是将这个新数据插入到这个有序数据中，这就相似于间接插入排序中将一个数据并入到有序区间中，这是节点“上浮”调整。不难写出插入一个新数据时堆的调整代码：

// 新退出 i 节点, 其父节点为(i-1)/2
// 参数：a：数组，i：新插入元素在数组中的下标 
void minHeapFixUp(int a[], int i) {  
    int j, temp;  
    temp = a[i];  
    j = (i-1)/2;      // 父节点 
    while (j >= 0 && i != 0) {if (a[j] <= temp)// 如果父节点不大于新插入的元素，进行寻找 
            break;  
        a[i]=a[j];            // 把较大的子节点往下挪动, 替换它的子节点 
        i = j;  
        j = (i-1)/2;  
    }  
    a[i] = temp;  
} 

因而，插入数据到最小堆时：

// 在最小堆中退出新的数据 data 
//a：数组，index：插入的下标，void minHeapAddNumber(int a[], int index, int data) {a[index] = data;  
    minHeapFixUp(a, index);  
} 

（2）删除代码实现
依照堆删除的阐明，堆中每次都只能删除第 0 个数据。为了便于重建堆，理论的操作是将数组最初一个数据与根节点替换，而后再从根节点开始进行一次从上向下的调整。

调整时先在左右儿子节点中找最小的，如果父节点不大于这个最小的子节点阐明不须要调整了，反之将最小的子节点换到父节点的地位。此时父节点实际上并不需要换到最小子节点的地位，因为这不是父节点的最终地位。但逻辑上父节点替换了最小的子节点，而后再思考父节点对前面的节点的影响。堆元素的删除导致的堆调整，其整个过程就是将根节点进行“下沉”解决。上面给出代码：

// a 为数组，len 为节点总数；从 index 节点开始调整，index 从 0 开始计算 index 其子节点为 2*index+1, 2*index+2；len/2- 1 为最初一个非叶子节点 
void minHeapFixDown(int a[],int len,int index) {if(index>(len/2-1))//index 为叶子节点不必调整
        return;
    int tmp=a[index];
    lastIndex=index;
    while(index<=len/2-1)        // 当下沉到叶子节点时，就不必调整了
    { 
        // 如果左子节点小于待调整节点
        if(a[2*index+1]<tmp) {lastIndex = 2*index+1;}
        // 如果存在右子节点且小于左子节点和待调整节点
        if(2*index+2<len && a[2*index+2]<a[2*index+1]&& a[2*index+2]<tmp) {lastIndex=2*index+2;}
        // 如果左右子节点有一个小于待调整节点，抉择最小子节点进行上浮
        if(lastIndex!=index) {a[index]=a[lastIndex];
            index=lastIndex;
        } else break;             // 否则待调整节点不必下沉调整
    }
    a[lastIndex]=tmp;           // 将待调整节点放到最初的地位
}

依据堆删除的下沉思维，能够有不同版本的代码实现，以上是和孙凛同学一起探讨出的一个版本，在这里感激他的参加，读者可另行给出。集体领会，这里倡议大家依据对堆调整过程的了解，写出本人的代码，切勿看示例代码去了解算法，而是了解算法思维写出代码，否则很快就会遗记。

（3）建堆
有了堆的插入和删除后，再思考下如何对一个数据进行堆化操作。要一个一个的从数组中取出数据来建设堆吧，不必！先看一个数组，如下图：

很显著，对叶子节点来说，能够认为它曾经是一个非法的堆了即 20，60，65，4，49 都别离是一个非法的堆。只有从 A[4]=50 开始向下调整就能够了。而后再取 A[3]=30，A[2] = 17，A[1] = 12，A[0] = 9 别离作一次向下调整操作就能够了。下图展现了这些步骤：

写出堆化数组的代码：

// 建设最小堆
//a: 数组，n：数组长度
void makeMinHeap(int a[], int n) {for (int i = n/2-1; i >= 0; i--)  
        minHeapFixDown(a, i, n);  
} 

2.2.4 堆的具体利用——堆排序

堆排序（Heapsort）是堆的一个经典利用，有了上面对堆的理解，不难实现堆排序。因为堆也是用数组来存储的，故对数组进行堆化后，第一次将 A[0]与 A[n – 1]替换，再对 A[0…n-2]从新复原堆。第二次将 A[0]与 A[n – 2]替换，再对 A[0…n – 3]从新复原堆，反复这样的操作直到 A[0]与 A[1]替换。因为每次都是将最小的数据并入到前面的有序区间，故操作实现后整个数组就有序了。有点相似于间接抉择排序。

因而，实现堆排序并没有用到后面阐明的插入操作，只用到了建堆和节点向下调整的操作，堆排序的操作如下：

//array: 待排序数组，len：数组长度
void heapSort(int array[],int len) {
    // 建堆
    makeMinHeap(array,len); 
    
    // 最初一个叶子节点和根节点替换，并进行堆调整，替换次数为 len- 1 次
    for(int i=len-1;i>0;--i) {
        // 最初一个叶子节点替换
        array[i]=array[i]+array[0];
        array[0]=array[i]-array[0];
        array[i]=array[i]-array[0];
        
        // 堆调整
        minHeapFixDown(array, 0, len-i-1);  
    }
} 

（1）稳定性。堆排序是不稳固排序。

（2）堆排序性能剖析。因为每次从新复原堆的工夫复杂度为 O(logN)，共 N - 1 次堆调整操作，再加上后面建设堆时 N / 2 次向下调整，每次调整工夫复杂度也为 O(logN)。两次操作工夫复杂度相加还是 O(NlogN)，故堆排序的工夫复杂度为 O(NlogN)。

最坏状况：如果待排序数组是有序的，依然须要 O(NlogN)复杂度的比拟操作，只是少了挪动的操作；

最好状况：如果待排序数组是逆序的，不仅须要 O(NlogN)复杂度的比拟操作，而且须要 O(NlogN)复杂度的替换操作，总的工夫复杂度还是 O(NlogN)。

因而，堆排序和疾速排序在效率上是差不多的，然而堆排序个别优于疾速排序的重要一点是数据的初始散布状况对堆排序的效率没有大的影响。