，会误以 为输入的是 float 参数。 • 如果你输入的是 3 这样的 int 类型常量， C 语 言不会帮你检测到他和 “ %f” 其实是不匹配的，而 是直接把 int 类型的 4 个字节推到栈上作为 printf 的参数，而 printf 却会把这 4 个字节作为 浮点来处理。由于浮点的指数位处于高位，但整数 是 3 ，导致高位全是 0 ，所以 printf 误读出来的 float 非主流的硬件架构如 PowerPC ， MIPS 才用大端字节序。 贴近底层的语言，比如 C/C++/Fortran 会采用当前硬件架构的字节序，比如在 x86 上就会变成小端字节序。 Java 这种虚拟机语言会采用大端字节序，因此在小端字节序的硬件上会比较低效，需要额外的字节序转换工作。 为了统一，互联网标准规定，协议包头中传输的数据类型（但凡是多个字节组成的）必须是大端字节序。 假如 x=0x01234567 gcc 特有的 alloca(n) 函数，会在当前函数的栈上分配内存，函数退出 时也会自动释放。 如果不是固定长度为 4 的数组呢？ • 但是 msvc 就不行，因为 alloca 是 gcc 特有的函数，微软比较笨，所以不支持。 • 因此栈上动态数组不是标准的 C 语言特 性，是无法跨平台使用的。 • 所以一般认为栈上的东西都是固定长度的 。 • DIDU_KNOW_TH

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5. 栈与队列 59 5.1. 栈 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5 复杂度分析：数据结构与算法的评价维度、算法效率的评估方法。时间复杂度、空间复杂度，包括推算 方法、常见类型、示例等。 ‧ 数据结构：常用的基本数据类型，数据在内存中的存储方式、数据结构分类方法。数组、链表、栈、队列、 散列表、树、堆、图等数据结构，内容包括定义、优劣势、常用操作、常见类型、典型应用、实现方法等。 ‧ 算法：查找算法、排序算法、搜索与回溯、动态规划、分治算法，内容包括定义、使用场景、优劣势、时 通常情况下，空间复杂度统计范围是「暂存空间」+「输出空间」。 暂存空间可分为三个部分： ‧「暂存数据」用于保存算法运行中的各种 常量、变量、对象 等。 ‧「栈帧空间」用于保存调用函数的上下文数据。系统每次调用函数都会在栈的顶部创建一个栈帧，函数返 回时，栈帧空间会被释放。 ‧「指令空间」用于保存编译后的程序指令，在实际统计中一般忽略不计。 Figure 2‑9. 算法使用的相关空间 /* 结构体 */

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5. 栈与队列 59 5.1. 栈 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5 复杂度分析：数据结构与算法的评价维度、算法效率的评估方法。时间复杂度、空间复杂度，包括推算 方法、常见类型、示例等。 ‧ 数据结构：常用的基本数据类型，数据在内存中的存储方式、数据结构分类方法。数组、链表、栈、队列、 散列表、树、堆、图等数据结构，内容包括定义、优劣势、常用操作、常见类型、典型应用、实现方法等。 ‧ 算法：查找算法、排序算法、搜索与回溯、动态规划、分治算法，内容包括定义、使用场景、优劣势、时 通常情况下，空间复杂度统计范围是「暂存空间」+「输出空间」。 暂存空间可分为三个部分： ‧「暂存数据」用于保存算法运行中的各种 常量、变量、对象 等。 ‧「栈帧空间」用于保存调用函数的上下文数据。系统每次调用函数都会在栈的顶部创建一个栈帧，函数返 回时，栈帧空间会被释放。 ‧「指令空间」用于保存编译后的程序指令，在实际统计中一般忽略不计。 Figure 2‑9. 算法使用的相关空间 /* 结构体 */

都隐藏着精 妙的算法思想。 同样，数据结构无处不在：大到社会网络，小到地铁线路，许多系统都可以建模为“图”；大到一个国家，小 到一个家庭，社会的主要组织形式呈现出“树”的特征；冬天的衣服就像“栈”，最先穿上的最后才能脱下； 羽毛球筒则如同“队列”，一端放入、另一端取出；字典就像一个“哈希表”，能够快速查找目标词条。 本书旨在通过清晰易懂的动画图解和可运行的代码示例，使读者理解算法和数据结构的核心概念，并能够通 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 第 5 章 栈与队列 89 5.1 栈 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 5.2 本书的主要内容如图 0‑1 所示。 ‧ 复杂度分析：数据结构和算法的评价维度与方法。时间复杂度和空间复杂度的推算方法、常见类型、示 例等。 ‧ 数据结构：基本数据类型和数据结构的分类方法。数组、链表、栈、队列、哈希表、树、堆、图等数据 结构的定义、优缺点、常用操作、常见类型、典型应用、实现方法等。 ‧ 算法：搜索、排序、分治、回溯、动态规划、贪心等算法的定义、优缺点、效率、应用场景、解题步骤 和示例问题等。

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 第 5 章 栈与队列 89 5.1 栈 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 5.2 本书的主要内容如图 0‑1 所示。 ‧ 复杂度分析：数据结构和算法的评价维度与方法。时间复杂度和空间复杂度的推算方法、常见类型、示 例等。 ‧ 数据结构：基本数据类型和数据结构的分类方法。数组、链表、栈、队列、哈希表、树、堆、图等数据 结构的定义、优缺点、常用操作、常见类型、典型应用、实现方法等。 ‧ 算法：搜索、排序、分治、回溯、动态规划、贪心等算法的定义、优缺点、效率、应用场景、解题步骤 和示例问题等。 递归：将问题分解为子问题 ?(?) = ?+?(?−1) ，不断（递归地）分解下去，直至基本情况 ?(1) = 1 时终止。 1. 调用栈 递归函数每次调用自身时，系统都会为新开启的函数分配内存，以存储局部变量、调用地址和其他信息等。 这将导致两方面的结果。 ‧ 函数的上下文数据都存储在称为“栈帧空间”的内存区域中，直至函数返回后才会被释放。因此，递归 通常比迭代更加耗费内存空间。 ‧ 递归调用函数会产生额

都隐藏着精 妙的算法思想。 同样，数据结构无处不在：大到社会网络，小到地铁线路，许多系统都可以建模为“图”；大到一个国家，小 到一个家庭，社会的主要组织形式呈现出“树”的特征；冬天的衣服就像“栈”，最先穿上的最后才能脱下； 羽毛球筒则如同“队列”，一端放入、另一端取出；字典就像一个“哈希表”，能够快速查找目标词条。 本书旨在通过清晰易懂的动画图解和可运行的代码示例，使读者理解算法和数据结构的核心概念，并能够通 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 第 5 章 栈与队列 89 5.1 栈 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 5.2 本书的主要内容如图 0‑1 所示。 ‧ 复杂度分析：数据结构和算法的评价维度与方法。时间复杂度和空间复杂度的推算方法、常见类型、示 例等。 ‧ 数据结构：基本数据类型和数据结构的分类方法。数组、链表、栈、队列、哈希表、树、堆、图等数据 结构的定义、优缺点、常用操作、常见类型、典型应用、实现方法等。 ‧ 算法：搜索、排序、分治、回溯、动态规划、贪心等算法的定义、优缺点、效率、应用场景、解题步骤 和示例问题等。

小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5. 栈与队列 68 5.1. 栈 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.2 本书主要内容包括： ‧ 复杂度分析：数据结构和算法的评价维度，算法效率的评估方法。时间复杂度、空间复杂度的推算方 法、常见类型、示例等。 ‧ 数据结构：基本数据类型，数据结构的分类方法。数组、链表、栈、队列、散列表、树、堆、图等数据 结构的定义、优缺点、常用操作、常见类型、典型应用、实现方法等。 ‧ 算法：搜索、排序、分治、回溯、动态规划、贪心等算法的定义、优缺点、效率、应用场景、解题步骤、 ‧「暂存数据」用于保存算法运行过程中的各种常量、变量、对象等。 ‧「栈帧空间」用于保存调用函数的上下文数据。系统在每次调用函数时都会在栈顶部创建一个栈帧，函 数返回后，栈帧空间会被释放。 ‧「指令空间」用于保存编译后的程序指令，在实际统计中通常忽略不计。 因此，在分析一段程序的空间复杂度时，我们一般统计 暂存数据、输出数据、栈帧空间 三部分。 Figure 2‑9. 算法使用的相关空间 /*

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 第 5 章 栈与队列 84 5.1 栈 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.2 本书主要内容如图 0‑1 所示。 ‧ 复杂度分析：数据结构和算法的评价维度与方法。时间复杂度、空间复杂度的推算方法、常见类型、示 例等。 ‧ 数据结构：基本数据类型，数据结构的分类方法。数组、链表、栈、队列、哈希表、树、堆、图等数据 结构的定义、优缺点、常用操作、常见类型、典型应用、实现方法等。 ‧ 算法：搜索、排序、分治、回溯、动态规划、贪心等算法的定义、优缺点、效率、应用场景、解题步骤、 递归：将问题分解为子问题 ?(?) = ?+?(?−1) ，不断（递归地）分解下去，直至基本情况 ?(0) = 0 时终止。 1. 调用栈 递归函数每次调用自身时，系统都会为新开启的函数分配内存，以存储局部变量、调用地址和其他信息等。 这将导致两方面的结果。 ‧ 函数的上下文数据都存储在称为“栈帧空间”的内存区域中，直至函数返回后才会被释放。因此，递归 通常比迭代更加耗费内存空间。 ‧ 递归调用函数会产生额

里面真正 K-V 对的一份深拷贝。你写入的只是这份拷贝 后的 V ，不是 map 中的那个 V 。 map 的遍历：遍历的同时修改怎么办？ k v map 中的 堆空间 执行你这段代码 的栈空间 未初 始化 v2 要写入的数 执行中的代码 for (auto [k, v]: m) { v = v2; } • 我们现在遍历一个 map ，然后把他里面所有的 V 都设为 v2 ，要怎么做？ 里面真正 K-V 对的一份深拷贝。你写入的只是这份拷贝 后的 V ，不是 map 中的那个 V 。 map 的遍历：遍历的同时修改怎么办？ k v map 中的 堆空间 执行你这段代码 的栈空间 k v v2 要写入的数 执行中的代码 for (auto [k, v]: m) { v = v2; } • 我们现在遍历一个 map ，然后把他里面所有的 V 都设为 v2 ，要怎么做？ ，不是 map 中的那个 V 。 map 的遍历：遍历的同时修改怎么办？ k v map 中的 堆空间 执行你这段代码 的栈空间 k v2 v2 要写入的数 执行中的代码 for (auto [k, v]: m) { v = v2; } 你修改的是栈空间 ( 周树人 ) 管我堆空间 ( 鲁迅 ) 什么事？ • 我们现在遍历一个 map ，然后把他里面所有的 V 都设为 v2 ，要怎么做？

当字符串长度小于 15 时， 还和局部小字符串缓存共享了空间。 _M_local_buf 是物理让字符串比较小的时候能 存储在栈上，如果超过 15 字节再去堆上分配空 间。这样能节省 new/delete 的一点性能开销。 例如 “ helloworld” 这个字符串只有 10 字节，他 实际上是存储在栈上的，这时 _M_p 会被设置为 指向 _M_local_buf 的首地址。 不过对于大字符串，这多出来的 8 capacity] 构型。 vector 没有采用小字符串优化…这是因为 string 面对的都 是 char ， wchar_t 这种比较小的类型，且用户常用的字符 串往往比较短很容易放进 15 字节的局部栈空间里；然而 vector 面对的往往是比较大的数据结构，有时还有智能指 针， std::thread 这种具有非平凡构造 / 析构函数的类型。对 vector 来说保障 RAII 的安全更重要，所以没有冒险优化。 MSVC 经典笑话：烫烫烫屯屯屯 • Windows 的 MSVC 在 Debug 模式下会默认把未初始化的栈内存 填满 0xCC （ x86 的 INT3 单步中断指令），未初始化的堆内存填 满 0xCD 。 • 而 0xCCCC 在 GBK 编码中就是“烫”，所以如果不小心打印了栈上 未初始化的字符串数组，就会看到“烫烫烫”。 • 而 0xCDCD 在 GBK 编码中就是“屯”，所以如果不小心打印了堆上