1.1　堆栈

不少人可能对堆栈的概念并不清楚，甚至部分从事计算机专业的人也没有理解通常所说的堆栈其实是两种数据结构。那么究竟什么是堆，什么又是栈呢？接下来，我们就来看看它们各自的概念。

栈，是硬件，主要作用表现为一种数据结构，是只能在一端插入和删除数据的特殊线性表。允许进行插入和删除操作的一端称为栈顶，另一端为栈底。栈按照后进先出的原则存储数据，最先进入的数据被压入栈底，最后进入的数据在栈顶，需要读数据时从栈顶开始弹出数据。栈底固定，而栈顶浮动。栈中元素个数为零时称为空栈。插入一般称为进栈（push），删除则称为出栈（pop）。栈也被称为先进后出表，在函数调用的时候用于存储断点，在递归时也要用到栈。

在计算机系统中，栈则是一个具有以上属性的动态内存区域。程序可以将数据压入栈中，也可以将数据从栈顶弹出。在i386机器中，栈顶由称为esp的寄存器进行定位。压栈的操作使栈顶的地址减小，弹出的操作使栈顶的地址增大。

栈在程序的运行中有着举足轻重的作用。最重要的是，栈保存了一个函数调用时所需要的维护信息，这常常被称为堆栈帧。栈一般包含以下两方面的信息：

1）函数的返回地址和参数。

2）临时变量：包括函数的非静态局部变量及编译器自动生成的其他临时变量。

堆，是一种动态存储结构，实际上就是数据段中的自由存储区，它是C语言中使用的一种名称，常常用于存储、分配动态数据。堆中存入的数据地址向增加方向变动。堆可以不断进行分配直到没有堆空间为止，也可以随时进行释放、再分配，不存在顺序问题。

堆内存的分配常通过malloc（）、calloc（）、realloc（）三个函数来实现。而堆内存的释放则使用free（）函数。

堆和栈在使用时“生长”方向相反，栈向低地址方向“生长”，而堆向高地址方向“生长”。我们对于堆的理解可能要直观些，而仅从概念上理解栈会让读者感到有些模糊。为了加深读者对于栈的理解，我们来看一个C语言题目。这个题目要求在不传递参数的情况下，在print（）函数中打印出main（）函数中arr数组中的各个元素。

include＜stdio.h＞

void print（）

{

//填充代码

}

int main（）

{

int a=1；

int b=2；

char c='c'；

int arr[]={11，12，13，14，15，16，17}；

print（）；

return 0；

}

注意　如无特殊说明，本书代码均通过VC++6.0来编译运行。

看看上面的代码和相关要求，可能会让很多读者束手无策，如果能联系前面的知识点，就应该想到用栈。那么我们该如何来解决问题呢？先别急，在讲解之前，我们先来回顾几个知识点。

1）push操作先移动栈顶指针，之后将信息入栈。

2）esp为堆栈指针，栈顶由esp寄存器来定位。压栈的操作使栈顶的地址减小，弹出的操作使栈顶的地址增大。

3）ebp是32位的bp，是基址指针。bp为基指针寄存器，用它可直接存取堆栈中的数据，它在调用函数时保存esp，以便函数结束时可以正确返回。

4）默认的函数内部变量的压栈操作为：从上到下、从左向右，采用4字节对齐。数组压栈方法略有不同，即从最后一个元素开始，直到起始元素为止，即采用从右向左的方法压栈。

现在看一下以上代码的汇编代码，在main（）函数的return语句处按F9键设置一个断点，然后按F5键运行代码，代码运行到断点时把光标移动到断点处，右击选择Go to Disassembly，就可以看到上面那段代码的汇编代码了。我们发现，在main（）函数和print（）函数的开头都有如下两句汇编指令：

push ebp

mov ebp,esp

为了使读者易于理解，在此通过图1-1来分析说明。根据图上的标注，函数开头部分的第一个push指令的操作步骤是，首先移动栈顶指针esp，然后将ebp内容压栈，注意此时压栈的ebp的值为上一个函数的esp的值，而esp恰好就是上一个函数的栈底，所以每个函数一开始的push指令就是保存上一个函数的栈底。那么接下来的mov指令有什么作用呢？由于esp是当前的栈顶指针，所以该指令的作用就是保存当前栈顶指针的值。由此就可以分析出，ebp存放的是此刻栈顶的地址，就是说，ebp是一个指针，指向栈顶，而栈顶存放的数据其实是上一个函数的ebp的值，即上一个函数的栈底。

图　1-1　函数调用过程中的压栈流程

通过上面的分析可知，ebp压栈后，接着就是函数中临时变量的压栈操作，由此可知，我们只需要在print（）函数中得到main（）函数的栈底，就可以取出数组中的每个元素了，看看下面的实现方法。

include＜stdio.h＞

void print（）

{

unsigned int_ebp；

__asm{

mov_ebp,ebp

}

intp=（int）（（int）_ebp-4-4-4-7*4）；

for（int i=0；i＜7；i++）

printf（"%d\t"，p[i]）；

}

int main（）

{

int a=1；

int b=2；

char c='a'；

int arr[]={11，12，13，14，15，16，17}；

print（）；

return 0；

}

运行结果为：

11 12 13 14 15 16 17

在没有传递任何参数的情况下，成功地在print（）函数中打印出了main（）函数中arr数组内的每个元素。现在来看看上面代码的实现方法，在print（）函数中定义了一个_ebp无符号整型变量，通过VC++6.0内嵌汇编把ebp的值保持到_ebp中，按照上面的分析，可以将在函数print（）中通过这条内嵌汇编语句得到的ebp看成一个指针，指针所指向的单元存放的就是print（）函数的上一个函数的栈底，在此是main（）函数的栈底。知道了_ebp的作用后，我们来分析下代码，通过（int）_ebp将_ebp转换为一个整型指针，然后通过（int）_ebp即可得到main（）函数的栈底地址。由于栈的压栈操作是从上到下、从右到左的，所以main（）函数中的变量a先压栈，然后是b、c，最后是arr数组，数组的压栈顺序是从右到左。通过“intp=（int）（（int）_ebp-4-4-4-74）；”即可得到数组元素的首地址。接下来，根据首地址就可以取出数组中的每个元素了。有的读者可能会有一个疑惑，main（）函数中有一个字符型变量，是不是在求数组元素的首地址时应该把其中的减4改为减1呢？因为它只占用了一个字节！即将“intp=（int）（（int）_ebp-4-4-4-74）；”修改为“intp=（int）（（int）_ebp-4-4-1-74）”。我们暂且不说其对与错，先来看看修改后的运行结果：

3072 3328 3584 3840 4096 4352-859021056

我们发现这样的运行结果是错误的，为什么呢？细心的读者可能发现了本章一开始回顾的知识点中有一点是很重要的，那就是压栈操作为4字节对齐。所以这里必须减4，而不是减1。

通过上面的分析，希望读者能够对栈有更加深入的理解，而对于堆的使用我们会在后续章节详细讲解。