栈

发表于 2024-11-08 更新于 2024-11-15 分类于中文，数据结构

栈的概念和使用

1. 栈的基本概念

后进先出（LIFO）：栈中最新放入的元素最先被取出，类似于一摞盘子，最后放进去的盘子最先被拿出来
栈顶（Top）：栈中最后插入元素的位置
栈底（Bottom）：栈中第一个插入元素的位置

2. 栈的操作

入栈（Push）：将一个元素放入栈中，入栈操作会将元素放在栈顶并更新栈顶位置
出栈（Pop）：将栈顶元素移出，出栈操作会移除并返回栈顶元素，同时更新栈顶位置
查看栈顶元素（Peek）：返回栈顶元素但不移除

3. 栈在程序中的应用

函数调用栈：
- 每次函数调用时，程序会在栈中为该函数创建一个栈帧（Stack Frame）
- 栈帧用于存储函数的参数、局部变量和返回地址
- 当函数调用结束时，栈帧会从栈中移除，返回控制权给调用它的函数
递归：
- 每次递归调用都会创建一个新的栈帧，因此递归会占用较多的栈空间
- 如果递归过深，可能会导致栈溢出（Stack Overflow）
处理局部变量：
- 函数中的局部变量会存储在栈帧中，函数结束时自动释放

4. 栈的内存布局

栈在内存中通常是从高地址向低地址增长
栈顶指针 %esp 用于标识当前栈顶的位置
栈基指针 %ebp 用于标识当前栈帧的基地址，方便函数访问参数和局部变量
栈操作通常是快速和高效的，因为它在内存中连续分配并自动管理释放

5. 栈的特性和局限性

快速访问：因为栈是按顺序存储的，访问栈顶元素非常高效
自动管理：函数调用结束时，栈帧自动释放，不需要手动管理
空间限制：栈的大小是有限的，如果分配过多的内存（如深层递归或大量局部变量），可能会导致栈溢出

6. 栈的示例

假设有一个简单的函数调用过程

void func1() {
    int a = 10; // 局部变量
    func2();    // 调用另一个函数
}

void func2() {
    int b = 20; // 局部变量
}

在 func1() 调用 func2() 时，内存栈的布局如下

func1() 的栈帧被创建，包含局部变量 a 和返回地址
调用 func2() 时，func2() 的栈帧被推入栈，包含局部变量 b 和返回地址
func2() 执行完毕后，其栈帧被弹出，控制权返回给 func1()
func1() 结束时，其栈帧也被弹出，程序返回到调用 func1() 的位置

栈帧结构详解

栈帧在函数调用时用于保存函数的参数、局部变量、返回地址以及一些寄存器的值以下是栈帧中各部分的详细解释

栈帧结构图示

内存布局图

1. %ebp（栈帧指针）

%ebp 指向当前栈帧的起始位置，帮助函数在运行时访问其参数和局部变量
在调用新函数时，当前的 %ebp 会被保存到栈中，以便在函数结束时能够恢复调用者的栈基地址

2. 参数（arg 1, arg 2 等）

函数调用时传递的参数会被压入栈中，通常从右到左依次存放
参数在栈中用于函数内部的计算和操作

3. 返回地址

在函数调用时，调用位置的下一条指令地址会被存储到栈中，作为返回地址
函数执行完毕时，CPU会读取返回地址，将控制权返回给调用函数的指令位置

4. 局部变量和保存的寄存器

在栈帧中还包括函数内部的局部变量空间，用于在函数运行期间存储局部变量的值
有时会保存一些寄存器的值（如 %ebx），以确保在函数执行期间寄存器的值不被破坏

5. 栈指针 %esp

%esp 指向当前栈的顶部，是动态变化的
每次栈操作（如压入或弹出元素）都会更新 %esp，并标识当前栈顶的位置

0%