内存分配中的堆和栈
在 C 语言中，内存分配方式不外乎有如下三种形式：
从静态存储区域分配：它是由编译器自动分配和释放的，即内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在，直到整个程序运行结束时才被释放，如全局变量与 static 变量。
在栈上分配：它同样也是由编译器自动分配和释放的，即在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元将被自动释放。需要注意的是，栈内存分配运算内置于处理器的指令集中，它的运行效率一般很高，但是分配的内存容量有限。
从堆上分配：也被称为动态内存分配，它是由程序员手动完成申请和释放的。即程序在运行的时候由程序员使用内存分配函数（如 malloc 函数）来申请任意多少的内存，使用完之后再由程序员自己负责使用内存释放函数（如 free 函数）来释放内存。也就是说，动态内存的整个生存期是由程序员自己决定的，使用非常灵活。需要注意的是，如果在堆上分配了内存空间，就必须及时释放它，否则将会导致运行的程序出现内存泄漏等错误。
数据结构的堆和栈
在数据结构中，栈是一种可以实现“先进后出”（或者称为“后进先出”）的存储结构。假设给定栈 S=（a0，a1，…，an-1），则称 a0 为栈底，an-1 为栈顶。进栈则按照 a0，a1，…，an-1 的顺序进行进栈；而出栈的顺序则需要反过来，按照“后存放的先取，先存放的后取”的原则进行，则 an-1 先退出栈，然后 an-2 才能够退出，最后再退出 a0。
在实际编程中，可以通过两种方式来实现：使用数组的形式来实现栈，这种栈也称为静态栈；使用链表的形式来实现栈，这种栈也称为动态栈。
相对于栈的“先进后出”特性，堆则是一种经过排序的树形数据结构，常用来实现优先队列等。假设有一个集合 K={k0，k1，…，kn-1}，把它的所有元素按完全二叉树的顺序存放在一个数组中，并且满足：
则称这个集合 K 为最小堆（或者最大堆）。
由此可见，堆是一种特殊的完全二叉树。其中，节点是从左到右填满的，并且最后一层的树叶都在最左边（即如果一个节点没有左儿子，那么它一定没有右儿子）；每个节点的值都小于（或者都大于）其子节点的值。
/*下面的代码定义了一些宏，使用这些宏能为多种数据类型建立同种逻辑的相关数据结构和算法。
使用这些宏，例子代码定义了3种数据类型的相关内容。
我在代码中都是ARRAY、数组的叫法，但是你把名字改成堆栈就可以了，因为堆栈的基本操作都有了。大小也会自动变大在需要的时候。
泛型宏的类型参数应该是个合法的符号名，例如：int，double等，
如果类型中包含特别的字符，可以先typedef一下，例如：typedef int *INT_PTR
这样就可以用INT_PTR表示原始的int*类型了。注意不能用宏，因为展开后还是包含
特别字符。
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <malloc.h>
#include <stddef.h>
/*避免符号重复的前缀*/
#define GENERIC_PREFIX() __C_Generic_2007_10_16_
/*一个宏，用于产生(针对某种包含数据类型的泛型数组)的类型名*/
#define ARRAY_TYPE(T) GENERIC_PREFIX()Array_##T
/*一些宏，用于(针对某种包含数据类型的泛型数组)的操作*/
#define ARRAY_NEW(T,N) ARRAY_TYPE(T)_New(N) /*创建新的元素为T的数组，初始容量为N*/
#define ARRAY_FREE(T,A) ARRAY_TYPE(T)_Free(&(A))/*释放元素为T的数组A*/
#define ARRAY_ITEM(T,A,N) (*ARRAY_TYPE(T)_Item(&(A),N)) /*获取元素为T的数组A的第N个元素*/
#define ARRAY_FRONT(T,A) (*ARRAY_TYPE(T)_Item(&(A),0)) /*获取元素为T的数组A的第一个（顶部）元素*/
#define ARRAY_BACK(T,A) (*ARRAY_TYPE(T)_Item(&(A),(A).size-1)) /*获取元素为T的数组A的末尾（底部）元素*/
#define ARRAY_RESERVE(T,A,N) ARRAY_TYPE(T)_Reserve(&(A),N) /*为元素为T的数组A保留至少N的容量*/
#define ARRAY_RESIZE(T,A,N) ARRAY_TYPE(T)_Resize(&(A),N) /*设置元素为T的数组A的大小为N（含有N各元素）*/
#define ARRAY_PUSH_BACK(T,A,V) ARRAY_TYPE(T)_PushBack(&(A),V) /*在元素为T的数组A的末尾压入一个元素V*/
#define ARRAY_POP_BACK(T,A) ARRAY_TYPE(T)_PopBack(&(A)) /*在元素为T的数组A的末尾弹出一个元素*/
#define ARRAY_PUSH_FRONT(T,A,V) ARRAY_TYPE(T)_Insert(&(A),0,V) /*在元素为T的数组A的头部压入一个元素V*/
#define ARRAY_POP_FRONT(T,A) ARRAY_TYPE(T)_Remove(&(A),0) /*在元素为T的数组A的头部弹出一个元素*/
#define ARRAY_INSERT(T,A,I,V) ARRAY_TYPE(T)_Insert(&(A),I,V) /*在元素为T的数组A的I处插入一个元素V*/
#define ARRAY_REMOVE(T,A,I) ARRAY_TYPE(T)_Remove(&(A),I) /*在元素为T的数组A的I处移除一个元素*/
/*一个宏，定义包含某种数据的泛型数组的数据结构及相应算法*/
#define ARRAY_DEF(T) \
typedef struct ARRAY_TYPE(T)_tag \
{ \
T (*const data) /*数据*/\
size_t const capacity/*容量*/\
size_t const size /*大小*/\
}ARRAY_TYPE(T)\
\
/*创建新的元素为T的数组，初始容量为N*/ \
__inline ARRAY_TYPE(T) ARRAY_TYPE(T)_New(size_t initCap) \
{ \
ARRAY_TYPE(T) r\
*(T (**))(void**)(&r)=(T (*))malloc(sizeof(T)*initCap)\
assert(r.data!=NULL)\
*(size_t*)((void**)(&r)+1)=initCap\
*((size_t*)((void**)(&r)+1)+1)=0\
return r\
}\
\
/*释放元素为T的数组A*/ \
__inline void ARRAY_TYPE(T)_Free(ARRAY_TYPE(T) const *a) \
{ \
assert(a->data!=NULL)\
free(a->data)\
}\
\
/*获取元素为T的数组A的第N个元素*/ \
__inline T * ARRAY_TYPE(T)_Item(ARRAY_TYPE(T) const *a, size_t index) \
{ \
assert(index>=0 &&index<(a->size))\
return a->data+index\
}\
\
/*为元素为T的数组A保留至少N的容量*/ \
__inline void ARRAY_TYPE(T)_Reserve(ARRAY_TYPE(T) const *a,size_t cap) \
{ \
if (a->capacity<cap) \
{ \
(*((T const **)(void const **)a))=realloc(a->data, (cap*4/3)*sizeof(T))\
assert(a->data!=NULL)\
*(size_t*)((void**)(a)+1)=cap\
} \
}\
\
/*设置元素为T的数组A的大小为N（含有N各元素）*/ \
__inline void ARRAY_TYPE(T)_Resize(ARRAY_TYPE(T) const *a,size_t sz) \
{ \
if (a->size<=sz) \
{ \
*((size_t*)((void**)(a)+1)+1)=sz\
} \
else \
{ \
ARRAY_TYPE(T)_Reserve(a,sz)\
*((size_t*)((void**)(a)+1)+1)=sz\
} \
}\
\
/*在元素为T的数组A的末尾压入一个元素V*/ \
__inline void ARRAY_TYPE(T)_PushBack(ARRAY_TYPE(T) const *a,T const vp) \
{ \
ARRAY_TYPE(T)_Reserve(a,a->size+1)\
a->data[a->size]=vp\
(*((size_t*)((void**)(a)+1)+1))++\
}\
\
/*在元素为T的数组A的末尾弹出一个元素*/ \
__inline void ARRAY_TYPE(T)_PopBack(ARRAY_TYPE(T) const *a) \
{ \
assert(a->size>0)\
(*((size_t*)((void**)(a)+1)+1))--\
}\
\
/*在元素为T的数组A的I处插入一个元素V*/ \
__inline void ARRAY_TYPE(T)_Insert(ARRAY_TYPE(T) const *a,size_t index,T const vp) \
{ \
size_t i\
assert(index>=0 &&index<=(a->size))\
ARRAY_TYPE(T)_Reserve(a,a->size+1)\
for (i=a->sizei>indexi--) \
{ \
a->data[i]=a->data[i-1]\
} \
a->data[index]=vp\
(*((size_t*)((void**)(a)+1)+1))++\
}\
\
/*在元素为T的数组A的I处移除一个元素*/ \
__inline void ARRAY_TYPE(T)_Remove(ARRAY_TYPE(T) const *a,size_t index) \
{ \
assert(index>=0 &&index<(a->size))\
for (index++(a->size)>indexindex++) \
{ \
a->data[index-1]=a->data[index]\
} \
(*((size_t*)((void**)(a)+1)+1))--\
}
/*定义一种存放long的数组*/
ARRAY_DEF(long)
/*定义一种存放char的数组*/
ARRAY_DEF(char)
/*定义一种存放double的数组*/
ARRAY_DEF(double)
/*不能重复定义相同的类型*/
int main()
{
/*声明3个数组*/
ARRAY_TYPE(long) la=ARRAY_NEW(long,11)
ARRAY_TYPE(char) ca=ARRAY_NEW(char,1)
ARRAY_TYPE(double) da=ARRAY_NEW(double,1)
/*压栈*/
ARRAY_PUSH_BACK(long,la,1)
/*打印大小（包含元素个数）*/
printf("size:%d\n",la.size)
/*打印容量（当前数组空间的大小）*/
printf("capacity:%d\n",la.capacity)
ARRAY_PUSH_BACK(long,la,2)
ARRAY_PUSH_BACK(long,la,3)
printf("size:%d\n",la.size)
printf("capacity:%d\n",la.capacity)
/*最深的那个元素*/
printf("%d\n",ARRAY_FRONT(long,la))
/*最浅的那个元素*/
printf("%d\n",ARRAY_BACK(long,la))
/*出栈*/
ARRAY_POP_BACK(long,la)
printf("size:%d\n",la.size)
printf("capacity:%d\n",la.capacity)
printf("%d\n",ARRAY_BACK(long,la))
printf("----------------------------\n")
ARRAY_PUSH_BACK(char,ca,'A')
printf("size:%d\n",ca.size)
printf("capacity:%d\n",ca.capacity)
ARRAY_PUSH_BACK(char,ca,'B')
ARRAY_PUSH_BACK(char,ca,'C')
printf("size:%d\n",ca.size)
printf("capacity:%d\n",ca.capacity)
printf("%c\n",ARRAY_FRONT(char,ca))
printf("%c\n",ARRAY_BACK(char,ca))
ARRAY_POP_BACK(char,ca)
printf("size:%d\n",ca.size)
printf("capacity:%d\n",ca.capacity)
printf("%c\n",ARRAY_BACK(char,ca))
printf("----------------------------\n")
ARRAY_PUSH_BACK(double,da,1.0)
printf("size:%d\n",da.size)
printf("capacity:%d\n",da.capacity)
ARRAY_PUSH_BACK(double,da,2.0)
ARRAY_PUSH_BACK(double,da,3.0)
printf("size:%d\n",da.size)
printf("capacity:%d\n",da.capacity)
printf("%f\n",ARRAY_FRONT(double,da))
printf("%f\n",ARRAY_BACK(double,da))
ARRAY_POP_BACK(double,da)
printf("size:%d\n",da.size)
printf("capacity:%d\n",da.capacity)
printf("%f\n",ARRAY_BACK(double,da))
ARRAY_FREE(double,da)
ARRAY_FREE(char,ca)
ARRAY_FREE(long,la)
return 0
}
