堆及栈学习总结.doc

堆和栈

在计算机领域，堆栈是一个不容忽视的概念，但是很多人甚至是计算机专业的人也没有明确堆栈其实是两种数据结构。堆栈都是一种数据项按序排列的数据结构，只能在一端(称为栈顶(top))对数据项进行插入和删除。要点：堆：顺序随意栈：后进先出(Last-In/First-Out)

堆和栈的区别

堆和栈的比较

从堆和栈的功能和作用来通俗的比较,堆主要用来存放对象的，栈主要是用来执行程序的.而这种不同又主要是由于堆和栈的特点决定的:

 在编程中，例如C/C++中，所有的方法调用都是通过栈来进行的,所有的局部变量,形式参数都是从栈中分配内存空间的。实际上也不是什么分配,只是从栈顶向上用就行,就好像工厂中的传送带(conveyor belt)一样,Stack Pointer会自动指引你到放东西的位置,你所要做的只是把东西放下来就行.退出函数的时候，修改栈指针就可以把栈中的内容销毁.这样的模式速度最快,当然要用来运行程序了.需要注意的是,在分配的时候,比如为一个即将要调用的程序模块分配数据区时,应事先知道这个数据区的大小,也就说是虽然分配是在程序运行时进行的,但是分配的大小多少是确定的,不变的,而这个"大小多少"是在编译时确定的,不是在运行时.

 堆是应用程序在运行的时候请求操作系统分配给自己内存，由于从操作系统管理的内存分配,所以在分配和销毁时都要占用时间，因此用堆的效率非常低.但是堆的优点在于,编译器不必知道要从堆里分配多少存储空间，也不必知道存储的数据要在堆里停留多长的时间,因此,用堆保存数据时会得到更大的灵活性。事实上,面向对象的多态性,堆内存分配是必不可少的,因为多态变量所需的存储空间只有在运行时创建了对象之后才能确定.在C++中，要求创建一个对象时，只需用new命令编制相关的代码即可。执行这些代码时，会在堆里自动进行数据的保存.当然，为达到这种灵活性，必然会付出一定的代价:在堆里分配存储空间时会花掉更长的时间！这也正是导致效率低的原因,

我想你现在该明白了吧。：）

学过汇编么？
内存中的东西分三类：代码(code)、数据(data)、栈(stack),
其中stack是负责子程序的调用和返回的，stack实行后进先出的机制，调用子程序时先将当前地址的下一个地址临时保存到stack中，而子程序根据这个地址返回。
在子程序（函数）内部分配的局部变量也是在stack中分配，这样，函数返回时，分配的空间也自动收回。
而heap则是系统从data区中特别挪用并且独立管理的一个数据区，用于程序执行中数据的动态分配。
从表相看：全局静态数据在data中，局部分配的静态数据在stack中，动态分配的数据在heap中。

一、 预备知识—程序的内存分配
一个程序一般分为3段:text段,data段,bss段

text段:就是放程序代码的,编译时确定,只读,
data段:存放在编译阶段(而非运行时)就能确定的数据,可读可写
就是通常所说的静态存储区,赋了初值的全局变量和静态变量存放在这个区域,常量也存放在这个区域
bss段:定义而没有赋初值的全局变量和静态变量,放在这个区域

一个由C/C++编译的程序占用的内存分为以下几个部分
1、栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
2、堆区（heap） — 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。
3、全局区（静态区）（static）— 全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束后由系统释放。
4、文字常量区 — 常量字符串就是放在这里的，程序结束后由系统释放 。
5、程序代码区 — 存放函数体的二进制代码。

二、例子程序
这是一个前辈写的，非常详细
//main.cpp
int a = 0; 全局初始化区
char *p1; 全局未初始化区
main()
{
int b; 栈
char s[] = "abc"; 栈
char *p2; 栈
char *p3 = "123456"; 123456\0在常量区，p3在栈上。
static int c =0； 全局（静态）初始化区
p1 = (char *)malloc(10);
p2 = (char *)malloc(20);
}

分配得来得10和20字节的区域就在堆区。
strcpy(p1, "123456"); 123456\0放在常量区，编译器可能会将它与p3所指向的"123456"优化成一个地方。

堆和栈的理论知识
1.申请方式
stack:
由系统自动分配。 例如，声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间
heap:
需要程序员自己申请，并指明大小，在c中malloc函数
如p1 = (char *)malloc(10);
在C++中用new运算符
如p2 = new char[20];//(char *)malloc(10);
但是注意p1、p2本身是在栈中的。

2.申请后系统的响应
栈：只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。
堆：首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块内存空间中的首地址处记录本次分配的大小，这样，代码中的delete语句才能正确的释放本内存空间。另外，由于找到的堆结点的大小不一定正好等于申请的大小，系统会自动的将多余的那部分重新放入空闲链表中。

3.申请大小的限制
栈：在Windows下,栈是向低地址扩展的数据结构，是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的，在 WINDOWS下，栈的大小是2M（也有的说是1M，总之是一个编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将提示overflow。因此，能从栈获得的空间较小。
堆：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。

4.申请效率的比较
栈由系统自动分配，速度较快。但程序员是无法控制的。
堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便.
另外，在WINDOWS下，最好的方式是用VirtualAlloc分配内存，他不是在堆，也不是在栈,而是直接在进程的地址空间中保留一快内存，虽然用起来最不方便。但是速度快，也最灵活

5.堆和栈中的存储内容
栈： 在函数调用时，第一个进栈的是主函数中函数调用后的下一条指令（函数调用语句的下一条可执行语句）的地址，然后是函数的各个参数，在大多数的C编译器中，参数是由右往左入栈的，然后是函数中的局部变量。注意静态变量是不入栈的。
当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的地址，也就是主函数中的下一条指令，程序由该点继续运行。
堆：一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。

6.存取效率的比较

char s1[] = "aaaaaaaaaaaaaaa";
char *s2 = "bbbbbbbbbbbbbbbbb";
aaaaaaaaaaa是在运行时刻赋值的；
而bbbbbbbbbbb是在编译时就确定的；
但是，在以后的存取中，在栈上的数组比指针所指向的字符串(例如堆)快。
比如：
#include
void main()
{
char a = 1;
char c[] = "1234567890";
char *p ="1234567890";
a = c[1];
a = p[1];
return;
}
对应的汇编代码
10: a = c[1];
00401067 8A 4D F1 mov cl,byte ptr [ebp-0Fh]
0040106A 88 4D FC mov byte ptr [ebp-4],cl
11: a = p[1];
0040106D 8B 55 EC mov edx,dword ptr [ebp-14h]
00401070 8A 42 01 mov al,byte ptr [edx+1]
00401073 88 45 FC mov byte ptr [ebp-4],al
第一种在读取时直接就把字符串中的元素读到寄存器cl中，而第二种则要先把指针值读到edx中，在根据edx读取字符，显然慢了。

7.小结：
堆和栈的区别可以用如下的比喻来看出：
使用栈就象我们去饭馆里吃饭，只管点菜（发出申请）、付钱、和吃（使用），吃饱了就走，不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作，他的好处是快捷，但是自由度小。
使用堆就象是自己动手做喜欢吃的菜肴，比较麻烦，但是比较符合自己的口味，而且自由度大。

堆和栈的区别主要分：
操作系统方面的堆和栈，如上面说的那些，不多说了。
还有就是数据结构方面的堆和栈，这些都是不同的概念。这里的堆实际上指的就是（满足堆性质的）优先队列的一种数据结构，第1个元素有最高的优先权；栈实际上就是满足先进后出的性质的数学或数据结构。
虽然堆栈，堆栈的说法是连起来叫，但是他们还是有很大区别的，连着叫只是由于历史的原因。

补充
堆栈是一种存储部件，即数据的写入跟读出不需要提供地址，而是根据写入的顺序决定读出的顺序

一个例子：
跟一个朋友谈堆栈的时候 就写下了这段文字，顺便发到这里给需要的看看吧
汇编初学者比较头痛的一个问题
////////////////////////////////////////////////////////////////////
比如 我们有这样一个C函数
#include<stdio.h>
long test(int a,int b)
{
    a = a + 1;
    b = b + 100;
    return a + b;
}
void main()
{  
  printf("%d",test(1000,2000));
}

写成32位汇编就是这样
;//////////////////////////////////////////////////////////////////////////////////////////////////////
.386
.model flat,stdcall ;这里我们用stdcall 就是函数参数 压栈的时候从最后一个开始压，和被调用函数负责清栈
option casemap:none区分大小写

includelib msvcrt.lib ;这里是引入类库 相当于 #include<stdio.h>了       
printf  PROTO C:DWORD,:VARARG  ;这个就是声明一下我们要用的函数头，到时候 汇编程序会自动到msvcrt.lib里面找的了:VARARG 表后面的参数不确定 因为C就是这样的printf(const char *, ...);;这样的函数要注意 不是被调用函数负责清栈 因为它本身不知道有多少个参数 ;而是有调用者负责清栈  下面会详细说明
.data
szTextFmt  BYTE '%d',0， 这个是用来类型转换的，跟C的一样,字符用字节类型
a dword 1000 ;假设
b dword 2000 ;处理数值都用双字 没有int 跟long 的区别

;/////////////////////////////////////////////////////////////////////////////////////////
.code

_test proc ;A:DWORD,B:DWORD 
      push ebp
      mov  ebp,esp
      mov  eax,dword ptr ss:[ebp+8]
      add  eax,1
      mov  edx,dword ptr ss:[ebp+0Ch]
      add  edx,100
      add  eax,edx
      pop  ebp      
      retn 8
_test endp

_main proc 
      push dword ptr ds:b       ;反汇编我们看到的b就不是b了而是一个[*****]数字 dword ptr 就是我们在ds(数据段)把[*****]
                                ;开始的一个双字长数值取出来
      push dword ptr ds:a       ;跟她对应的还有 byte ptr ****就是取一个字节出来 比如这样 mov  al,byte ptr ds:szTextFmt 
                                ;就把 % 取出来 而不包括 d
      call _test                  
      push eax                  ;假设push eax的地址是×××××
      push offset szTextFmt
      call printf
      add  esp,8
      ret             
_main endp
end  _main

;////////////////////////////////////////////////////////////// 下面介绍堆栈的变化
首先要明白的是 操作堆栈段 ss 只能用 esp或ebp寄存器 其他的寄存器eax ebx edx等都不能够用 而 esp永远指向堆栈栈顶 ebp用来 在堆栈段

里面寻址
push 指令是压栈 ESP=ESP-4
pop  指令是出栈 ESP=ESP+4
我们假设main函数一开始堆栈定是 ESP=400
push dword ptr ds:b                 ;ESP-4=396 ->里面的值就是 2000 就是b的数值
push dword ptr ds:a                 ;ESP-4=392 ->里面的值就是 1000 就是a的数值
call test                           ;ESP-4=388－>里面的数值是什么？这个太重要了 就是我们用来找游戏函数的原理所在。
                                                 里面的数值就是call test 指令下一条指令的地址－>即push eax的地址×××××

到了test函数里面

push ebp                           ;ESP-4=384->里面保存了当前ebp的值 而不是把ebp清零
mov  ebp,esp                       ;这里ESP＝384就没变化了，但是 ebp=esp=384,为什么要这样做呢 因为我们要用ebp到堆栈里面找参数
mov  eax,dword ptr ss:[ebp+8]      ;反汇编是这样的 想想为什么a就是[ebp+8]呢
                                   ;我们往上看看堆栈里地址392处就保存着a的值 这里ebp=384 加上8正好就是392了
                                   ;这样就把传递过来的1000拿了出来eax=1000
add  eax,1                         ;相当于 a+1了 eax=1001
mov  edx,dword ptr ss:[ebp+0Ch]    ; 0Ch=12 一样道理这里指向堆栈的地址是384+12=396 就是2000了 edx=2000
add  edx,100                       ;相当于 b+100 edx=2100
add  eax,edx                       ;eax=eax+edx＝1001＋2100＝3101 这里eax已经保存了最终的结果了 
                                   ;因为win32汇编一般用eax返回结果 所以如果最终结果不是在eax里面的话 还要把它放到eax
                                   ;比如假设我的结果保存在变量nRet里面 最后还是要这样 mov eax,dword ptr nRet
pop  ebp                           ;ESP=384+4=388 而保存在栈顶384的值 保存到 ebp中 即恢复ebp原来的值                       
                                   ;因为一开始我们就把ebp的值压栈了，mov ebp,esp已经改变了ebp的值，这里恢复就是保证了堆栈平衡
retn  8                            ;ESP+8->396 这里retn是由系统调用的 我们不用管 系统会自动把EIP指针指向 原来的call的下一条指令
                                   ;由于是系统自动恢复了call那里的压栈所以 真正返回到的时候ESP+4就是恢复了call压栈的堆栈
                                   ;到了这个时候 ESP=400 就是函数调用开始的堆栈，就是说函数调用前跟函数调用后的堆栈是一样的
                                   ;这就是堆栈平衡 
由于我们用stdcall上面retn 8就是被调用者负责恢复堆栈的意思了，函数test是被调用者，所以负责把堆栈加8,call 那里是系统自动恢复的

push eax                ;ESP-4=396->里面保存了eax的值3101
                        ;上面已经看到了eax保存着返回值，我们要把它传给printf也是通过堆栈传递       
push offset szTextFmt   ;ESP-4=392->里面保存了szTextFmt的地址 也就是C里面的指针 实际上没有什么把字符串传递的，我们传的都是地址
                        ;无论是在汇编或C 所以在汇编里没有什么字符串类型 用最多的就是DWORD。嘿嘿游戏里面传递参数 简单多了
call printf             ;ESP-4=388->里面保存了下一条指令的地址
add  esp,8              ;ESP+8=400 恢复了调用printf前的堆栈状态
                        ;上面说了由于printf后面参数是:VARARG 这样的类型是有调用者恢复堆栈的 所以printf里面没有retn 8之类的指令
                        ;这是由调用者负责清栈 main是调用者 所以下面一句就是 add esp,8 把堆栈恢复到调用printf之前
                        ;而call printf那里的压栈 是由系统做的 恢复的工作也是系统完成 我们不用理 只是知道里面保存是返回地址就够  

                      ;了
ret                     ;main 函数返回 其他的事情是系统自动搞定 我们不用理 任务完成