21.2  栈内存管理

栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。在执行函数时，函数内局部变量的存储单元都能够在栈上创建，函数执行结束时这些存储单元会自动被释放。

21.2.1  申请栈内存

栈内存有两种实现方法，一种是由系统根据需要自动分配，程序不能控制，另一种是用堆来模拟栈的操作。下面通过两个例子来看一下栈空间是如何分配的。

【示例21-2】 函数f是递归函数，当从第n层进入第n+1层时就需要在栈上存储现场。

int fun(int x)  
{  
    if x>0 then  
        fun(x--);  
cout<<"x="<<x<<endl;  
    return 0;  
} 

分析：当x为正数时就进入下一层递归，否则输出x的值，然后退到上一层。当每进入一层递归时，任何其他返回时要恢复的现场数据都将被保存在栈上，例如x的值，返回后继续执行的下一条指令的地址等。由于从内层递归返回外层后，原来的x的值还要使用，所以进入内层递归时，x的值必须保存在栈上。当返回时，再依次从栈上取出。

【示例21-3】 临时变量保存在栈上的情况。

void main ()  
{  
    int a;  
    float b;  
    double c;  
    char s[10];  
    ...  
}  
void func(int x, int y)  
{  
    ...  
} 

分析：函数main()中声明了4个临时变量，各个变量在编译时自动从栈上获得存储空间。各语句的意思如下所示。

int a;表示系统在栈上为整型变量a申请了int字节大小的内存存储单元。

float b;表示系统在栈上为浮点型变量b申请了float字节大小的内存存储单元。

double d;表示系统在栈上为双精度型变量c申请了double字节大小的内存存储单元。

char s[10];表示系统在栈上为字符型数组s 申请了10个char字节大小的内存存单元。

在函数func中的参数列表(int x, int y)，申请了2个形参变量。

int x表示系统在栈上为形参x申请了int字节大小的内存存储单元。

int y表示系统在栈上为形参y申请了int字节大小的内存存储单元。

注意：如果在栈上申请的内存大于栈上的所有剩余的内存空间，系统将会提示栈溢出的错误。

【示例21-4】 用指针来模拟的链栈。

class intstack  
{  
private:  
    struct tagint  
    {  
        int x;  
        int *p;  
    } value;  
public:  
    void push(int y);  
    int pop();  
} 

分析：该类是用堆来模拟了一个先进后出的栈。其中，结构体struct tagint实现了一个链栈，它的内存空间实际上来自于堆（下一节会讲到），而函数push()和pop()则负责对该栈进行操作。push()是压栈，既写数据进栈，而pop()是从栈内弹出数据，同时释放申请的空间。该示例实际上是不完整的，只说明了栈的基本元素，21.2.2节将补全该示例。关于链栈还有很多操作，可以参考本书其他章节。