Post

栈和队列

Posted Updated
By 何翌闻
14 min read
栈和队列

image-20250928081306927

程序如何运行起来——从硬盘到内存的旅程

核心问题

一个编译好的、静态存储在硬盘上的程序（如 a.exe），是如何被加载到内存中，并成为一个动态运行的进程的？

核心答案

这个过程依赖于操作系统的核心机制：创建虚拟地址空间 和 按需加载。它就像为程序搭建一个专属的、私有的“理想厨房”（虚拟空间），然后根据需要将食材（代码和数据）从仓库（硬盘）搬进真实的工作台（内存）。

一、静态阶段：硬盘里有什么？

程序在运行前，以可执行文件的形式静态地存储在硬盘上。我们可以把它想象成一本完整的“建筑蓝图和原料清单”。

存储内容对应区域说明
机器指令代码段（.text）由所有函数（包括 main 函数）编译而成的二进制机器码。这是程序的核心逻辑。
已初始化全局/静态变量数据段（.data）在代码中预先赋了初值的全局变量和静态变量。
未初始化全局/静态变量BSS段（.bss）在代码中未赋初值的全局变量和静态变量。在文件中只记录大小，不占用实际空间。
其他元信息头文件、符号表等告诉操作系统如何加载程序，如程序入口地址、所需共享库等。

关键点：此时的程序是被动的，它只是一堆数据，无法自己执行。

二、加载阶段：操作系统搭建“理想厨房”

当我们启动程序时，操作系统的加载器开始工作。它的核心任务是创建一个进程，并为这个进程分配一个虚拟地址空间。

  1. 创建进程：操作系统创建一个新的进程控制块（PCB），用于管理这个程序运行的所有信息。

  2. 分配虚拟地址空间（核心概念）：

    • 每个进程都认为自己独占了整个内存（例如，从地址0到地址2^64-1）。
    • 操作系统将这个巨大的、一维的线性地址空间，规划成一个规整的“树状”或“段式”结构。这个结构是标准化的，如下图所示：

    （此处可配一个虚拟地址空间布局图）

    • 代码区（Text Segment）：存放程序的指令。
    • 数据区（Data Segment）：存放全局和静态变量。
    • 堆区（Heap）：用于动态内存分配（malloc/new），向高地址增长。
    • 栈区（Stack）：用于函数调用、保存局部变量，向低地址增长。
    • 共享库区：映射用到的标准库等共享代码。

关键点：此时，操作系统主要是在内核中建立内存映射管理表，相当于画好了“厨房的规划图”，但真正的食材（代码和数据）大部分还在硬盘里。

三、运行阶段：内存成为工作舞台

当CPU开始执行进程的第一条指令时，程序才真正“活”了过来。

  1. 按需加载（缺页中断）：
    • CPU要访问一个虚拟地址，但操作系统发现该地址对应的内容不在物理内存中。
    • 这会触发一个缺页中断。操作系统介入： a. 从硬盘的可执行文件中找到对应的代码或数据页。 b. 在物理内存中找一页空闲空间。 c. 将数据从硬盘复制到物理内存。 d. 更新内存映射表，建立虚拟地址到物理地址的链接。
    • CPU重新执行指令，此时成功。
  2. 内存（RAM）里保存什么？（程序运行时）
    • 正在执行的指令：CPU当前和即将要执行的代码段内容。
    • 正在使用的数据：包括全局数据、当前函数栈帧中的局部变量、参数、返回值等。
    • 动态分配的数据：通过 malloc 或 new 在堆上申请的空间。
    • 操作系统内核代码和数据（部分）：用于管理这个进程。
  3. 硬盘的幕后工作（虚拟内存/交换）：
    • 当物理内存不足时，操作系统会将暂时不用的内存页面换出到硬盘的交换空间（Swap Space），以便为急需的页面腾出位置。当需要时再换入。

四、总结：硬盘 vs. 内存

特性硬盘（Hard Disk Drive / SSD）内存（Random Access Memory, RAM）
角色比喻仓库工作台
存储内容静态、永久的全部数据动态、临时的活跃数据
程序相关保存整个可执行文件（蓝图）保存进程运行所必需的代码和数据片段（正在施工的部分）
速度慢快
持久性断电后数据不丢失断电后数据全部丢失
管理单位文件/扇区内存页（通常4KB）

核心结论

程序运行的本质是：操作系统通过虚拟内存技术，为每个进程提供一个统一的、隔离的虚拟地址空间（树状结构），并通过按需加载机制，将硬盘上静态的程序蓝图，高效地映射到物理内存这个“工作台”上，交由CPU执行。

栈帧和程序运行

1
2
3
4
5
6
7

int main() {
    int a = 10;     // 初始化a为10
    int b = 20;     // 初始化b为20
    f(a);           // 第一次函数调用
    f(b);           // 第二次函数调用
    return 0;
}

栈变化全过程图解

图1：main函数开始执行，栈帧建立

当main函数被调用，它的栈帧已经建立，局部变量a和b完成了分配和初始化。

image-20250928083441915

状态说明：

  • main 函数的栈帧已建立。
  • 局部变量 a 和 b 已在栈上分配空间并被初始化。
  • EBP 指向当前栈帧的底部，ESP 指向栈帧的顶部。
图2：准备调用 f(a)，参数压栈

执行到 f(a); 时，将参数 a 的值（10）压入栈顶。

image-20250928083506503

状态说明：

  • 参数 a=10 被压入栈顶，ESP 上移。
  • 此时栈上为调用 f 函数做好了准备。
图3：执行 call f 指令后，进入f函数

执行 call f 指令后，返回地址被压栈，CPU 开始执行 f 函数的代码。f 函数执行 push ebp; mov ebp, esp 来建立自己的栈帧。

image-20250928083527313

状态说明：

  • call f 将返回地址压入栈顶。
  • f 函数首先保存 main 函数的 EBP，然后将当前 ESP 值设置给自己的 EBP，从而建立新的栈帧。
  • 此时 EBP 和 ESP 都指向 f 函数栈帧的底部。如果 f 函数有局部变量，ESP 会继续下移为它们分配空间。
图4：f函数返回后，准备第二次调用

f 函数执行 ret 指令返回后，栈顶指针 ESP 下移到参数位置。main 函数清理参数后，栈恢复原状。接着准备调用 f(b)，将参数 b=20 压入栈顶。

image-20250928083548960

状态说明：

  • 第一次调用 f(a) 的痕迹已被完全清理。
  • 参数 b=20 被压入栈顶，为第二次调用 f(b) 做准备。
  • 之后的过程（图3、图4）会完全重复一次，只是这次传递的值是20。

核心要点总结

  1. 栈增长方向：栈从高地址向低地址增长，ESP 始终指向栈顶。
  2. 栈帧结构：每个函数栈帧通常包含参数、返回地址、保存的 EBP 和局部变量。
  3. 值传递：C/C++ 默认是值传递，f(a) 传递的是 a 值的副本，因此在 f 内部修改参数不会影响 main 中的 a。
  4. 生命周期：局部变量 a 和 b 的生命周期与 main 函数栈帧共存亡。
  5. 函数调用开销：函数调用和返回伴随着压栈、出栈等操作，这就是函数调用的时间开销所在。

栈

概念

栈是一种 后进先出 的数据结构，像一摞盘子：你只能从最上面放盘子（压栈）或取盘子（弹栈）。

C++ 实现方式

  • 标准库容器： std::stack
  • 底层容器： 默认基于 deque，也可用 vector 或 list。

核心操作

1
2
3
4
5
6
7
8
9
10
11
12
13

AbstractDataType Stack{
    instances
        list of elements;
        one end is called the  bottom;
        the other is the top;
    operations
        Create():Create an empty stack;
        IsEmpty():Return true if stack is empty,return  false otherwise
        IsFull ():Return true if stack if full,return false otherwise;
        Top():return top element of the stack;
        Add(x): add element x to the stack;
        Delete(x):Delete top element from stack and put it in x;
}

特点 & 用途

  • 特点： LIFO，快速访问栈顶，大小动态变化。
  • 用途：
    • 函数调用栈（存储局部变量、返回地址等）。
    • 表达式求值（如括号匹配）。
    • 撤销操作（Ctrl+Z）。

队列

概念

队列是一种 先进先出 的数据结构，像排队买票：先来的人先服务，后来的人排到队尾。

C++ 实现方式

  • 标准库容器： std::queue
  • 底层容器： 默认基于 deque，也可用 list。

核心操作

1
2
3
4
5
6
7
8
9
10
11
12

AbstractDataType Queue {
    instances
        ordered list of elements;one end is called the front; the other is the rear;
    operations
        Create(): Create an empty queue; 
        IsEmpty(): Return true if queue is empty,return  false otherwise; 
        IsFull(): return true if queue is full, return false  otherwise; 
        First(): return first element of the queue;
        Last(): return last element of the queue;
        Add(x): add element x to the queue;
        Delete(x): delete front element from the queue  and put it in x; 
}

特点 & 用途

  • 特点： FIFO，从队尾插入，队首删除。
  • 用途：
    • 消息队列（处理异步任务）。
    • 广度优先搜索（BFS）。
    • 打印机任务调度。
数据结构与算法
笔记
This post is licensed under CC BY 4.0 by the author.

Trending Tags

笔记 随笔 插件