堆栈

前言

在理解堆(Heap)和栈(Stack)这两个概念时，需要放到具体的场景，因为在不同的场景下，堆和栈代表了两种不同的含义。

两种数据结构
内存管理方式

数据结构

栈的定义

栈(Stack): 只允许在一端进行插入或删除的线性表。
栈顶(TOP): 线性表允许进行插入或删除的那一端。
栈底(Bottom): 固定的，不允许进行插入或删除的另一端。
空栈: 不含任何元素的空表。
栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构

栈的结构

#define MAXSIZE 50  // 栈中元素的最大个数
typedef struct{
    int data[MAXSIZE];
    int top;    //用于栈顶指针
}Stack;

初始化

void InitStack(Stack *S){
    S->top = -1;    //初始化栈顶指针
}

判栈空

bool StackEmpty(Stack S){
    if(S.top == -1){    
        return true;  // 栈空
    }else{  
        return false; // 非空
    }
}

进栈push

// 插入元素data为新的栈顶元素
int Push(Stack* S, int data) {
    // 栈满
    if (S->top == MAXSIZE - 1) {
        return 0;
    }
    S->top++;   //栈顶指针增加一
    S->data[S->top] = data;    //将新插入元素赋值给栈顶空间
    return 1;
}

出栈pop

// mydata为取出的栈顶元素
int Pop(Stack* S, int* mydata) {
    if (S->top == -1) {
        return 0;
    }
    *mydata = S->data[S->top];   //将要删除的栈顶元素赋值给e
    S->top--;   //栈顶指针减一
    return 1;
}

读栈顶元素

// mydata为取出的栈顶元素
int Pop(Stack* S, int* mydata) {
    if (S->top == -1) {
        return 0;
    }
    *mydata = S->data[S->top];
    S->top--;
    return 1;
}

内存管理

程序数据分类

Code：表示程序所占用 FLASH 的大小（FLASH）。
RO-data：即 Read Only-data，表示程序定义的常量，如 const 类型（FLASH）
RW-data：即 Read Write-data，表示已被初始化的全局变量（SRAM）
ZI-data：即 Zero Init-data，表示未被初始化的全局变量(SRAM)

堆区(HEAP)

一般由程序员分配释放，若程序员不释放，程序结束时可能由OS回收。在单片机的sram中的ZI-data中。由malloc 系列函数或new 操作符分配的内存。其生命周期由free 或delete 决定。在没有释放之前一直存在，直到程序结束。其特点是使用灵活，空间比较大，但容易出错。向上生长；

栈区(STACK)

由编译器自动分配释放，在单片机的sram中的ZI-data。保存局部变量。栈上的内容只在函数的范围内存在，当函数运行结束，这些内容也会自动被销毁。其特点是效率高，但空间大小有限。由高地址向低地址生长。

静态数据区（.data和.bss）

保存全局变量和 static 变量（包括static全局和局部变量）。全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域（.data），未初始化的全局变量和未初始化的静态变量在相邻的另一块区域（.bss），程序结束后由系统释放。这些数据也是可读可写的，和stack、heap一样，被包含在sram中。静态区的内容在总个程序的生命周期内都存在，由编译器在编译的时候分配。

三种内存分配方式

从静态存储区域分配。内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在。例如全局变量，static变量。
在栈上创建。在执行函数时，函数内局部变量的存储单元在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。
从堆上分配，亦称动态内存分配。程序在运行的时候用malloc或new申请任意多少的内存，程序员自己负责在何时用free或delete释放内存。