文章目录一、前置基础概念时间复杂度1.1 时间复杂度1.2 内存层面栈(Stack内存区) vs 堆(Heap内存区)二、线性数据结构2.1 数组2.2 数据结构栈 std::stack容器适配器默认底层 deque2.3 队列 std::queue容器适配器默认底层 deque2.4 链表 std::list三、堆数据结构堆优先队列底层四、树、二叉树、二叉搜索树、红黑树4.1 树4.2 二叉树4.3 二叉搜索树 BSTBinary Search Tree4.4 红黑树平衡二叉搜索树五、哈希结构 关联容器5.1 哈希表Hash Table5.2 std::map5.3 std::unordered_map5.4 std::set / std::unordered_set六、快速对比总结七、补充记忆要点一、前置基础概念时间复杂度1.1 时间复杂度含义衡量算法运行时间随数据规模 n 增长的增长趋势不考虑常数系数只看最高阶项用大 O 记号表示O(1)常数复杂度固定次数运算随机访问数组元素O(log n)对数复杂度每次减半查找二分查找、红黑树查找O(n)线性复杂度遍历全部元素O(n log n)线性对数复杂度快排、归并排序O(n²)平方复杂度两层嵌套循环、朴素冒泡排序O(2ⁿ)指数复杂度暴力递归补充还有空间复杂度衡量额外占用内存的增长趋势1.2 内存层面栈(Stack内存区) vs 堆(Heap内存区)✅ 栈内存系统栈 / 调用栈内存特点连续、由编译器自动分配释放、后进先出LIFO、容量很小几MB、分配速度极快存放内容局部变量、函数参数、函数返回地址、静态数组生命周期函数调用结束自动销毁超出容量会发生栈溢出C示例int a; int arr[100];✅ 堆内存动态堆 / 自由堆内存特点不连续、手动申请/释放、容量很大、分配速度较慢、全局有效申请/释放new / delete、malloc / free生命周期直到主动 delete / 程序结束才释放忘记释放会造成内存泄漏C示例int *p new int[100]; delete[] p;注意区分内存栈/堆和数据结构栈/堆下文二者不是同一个概念二、线性数据结构2.1 数组1定长静态数组本质连续整块内存、同类型元素、下标随机访问、长度编译期固定不能动态扩容C写法intarr[10];// 栈上定长数组intarr2[5]{1,2,3,4,5};特性✅ 优点随机访问 O(1)遍历速度极快缓存友好❌ 缺点长度固定无法灵活扩容中间插入/删除 O(n)需要整体移位易越界时间复杂度随机访问 O(1)头部插入/删除 O(n)尾部追加未满O(1)2不定长动态数组Cstd::vector本质底层是堆上的连续数组自带动态扩容机制通常容量不够时 ×2 扩容特性✅ 优点随机访问 O(1)尾部增删 O(1) amortized 均摊支持自动扩容❌ 缺点中间/头部插入删除 O(n)扩容时会拷贝全部元素产生开销时间复杂度随机访问 O(1)末尾 push_back 均摊 O(1)中间插入 O(n)存储数据存在堆内存容器对象本身可在栈上2.2 数据结构栈 std::stack容器适配器默认底层 deque核心规则LIFO 后进先出只能在一端栈顶做插入和删除核心接口push()入栈、pop()出栈、top()取栈顶、empty()判空时间复杂度入栈、出栈、取栈顶均 O(1)用途函数调用、表达式求值、括号匹配、深度优先 DFS❗不能随机访问内部元素只能访问栈顶2.3 队列 std::queue容器适配器默认底层 deque核心规则FIFO 先进先出一端入队队尾一端出队队头核心接口push()入队、pop()出队、front()队首、back()队尾时间复杂度入队、出队 O(1)变种双端队列std::deque两端都可 O(1) 增删支持下标随机访问分段连续内存优先队列std::priority_queue本质是堆结构自动按优先级弹出最值用途任务排队、BFS广度优先遍历、消息缓冲2.4 链表 std::list1原生链表单向/双向链表本质非连续内存节点每个节点存数据 指针指向后继/前驱节点单向链表只有后继指针只能向后遍历查找 O(n)头部增删 O(1)双向链表同时存前驱后继指针可双向遍历✅优点任意已知位置插入删除 O(1)无需整体移位、无连续内存限制、无扩容拷贝开销❌缺点不支持随机访问访问第k个元素 O(n)缓存不友好额外占用指针内存2std::listC 标准双向链表特性双向循环链表实现随机访问不支持 [] 下标访问遍历/查找 O(n)已知迭代器位置插入/删除O(1)适合频繁中间增删、很少随机访问的场景三、堆数据结构堆优先队列底层✅概念本质完全二叉树结构通常用数组/vector存储分为大顶堆、小顶堆大顶堆父节点值 ≥ 子节点值堆顶是最大值小顶堆父节点值 ≤ 子节点值堆顶是最小值索引规律下标 i 的父节点 i/2左孩子 2i1右孩子 2i2Cstd::priority_queue默认是大顶堆时间复杂度建堆O(n)插入元素、弹出堆顶元素O(log n)获取最值O(1)用途TopK 问题、堆排序、任务调度、Dijkstra最短路径算法四、树、二叉树、二叉搜索树、红黑树4.1 树概念n 个节点的非线性层级结构1个根节点其余节点分为若干互不相交子树无环、连通节点根节点、父节点、子节点、叶子节点、深度、高度特点适合存储层级数据目录、组织结构遍历前序、中序、后序、层序遍历4.2 二叉树概念每个节点最多只有 2 个子节点左子树、右子树满二叉树每一层节点都填满完全二叉树除最后一层外全部填满最后一层靠左排布堆的底层结构遍历前序(根左右)、中序(左根右)、后序(左右根)、层序遍历普通二叉树查找效率差最坏退化成链表 O(n)4.3 二叉搜索树 BSTBinary Search Tree核心规则左子树所有节点值 根节点值右子树所有节点值 根节点值中序遍历 升序序列理想时间复杂度查找/插入/删除 O(log n)❌ 缺陷极端数据下退化成单侧链表复杂度退化 O(n)失去平衡目的快速查找、有序遍历4.4 红黑树平衡二叉搜索树概念自平衡二叉搜索树通过变色旋转保持平衡解决普通BST退化问题五大核心规则节点颜色只有 红色 / 黑色根节点一定是黑色所有叶子节点NIL空节点都是黑色红节点的子节点必须都是黑色不能有连续红节点任意节点到其所有后代叶子节点的路径上黑节点数量相同黑高一致特性保证最长路径不超过最短路径的 2 倍始终保持近似平衡查找/插入/删除稳定 O(log n)Cstd::map/std::set底层默认实现就是红黑树✅优点查找稳定高效、有序遍历❌缺点插入删除需要额外旋转变色开销五、哈希结构 关联容器5.1 哈希表Hash Table核心原理通过哈希函数把 key 映射到数组下标直接定位存储位置存在哈希冲突不同key映射同一位置冲突解决方法链地址法链表/红黑树、开放寻址法Cstd::unordered_map/unordered_set时间复杂度平均查找/插入/删除 O(1)最坏情况大量冲突退化为 O(n)✅优点查询速度极快❌缺点无序、占用内存更大、存在哈希冲突风险不支持有序遍历5.2 std::map底层红黑树平衡BST键值对 key-valuekey 唯一默认按 key 升序排序查找/插入/删除稳定 O(log n)✅优点有序遍历、范围查找稳定❌缺点比 unordered_map 查询慢支持[]访问、迭代器有序遍历5.3 std::unordered_map底层哈希表key 唯一无序存储不保证遍历顺序平均查找/插入/删除 O(1)查询速度更快✅优点高频单点查询性能优秀❌缺点无序、迭代器不稳定、存在哈希冲突适合高频单点查找不需要有序遍历的场景5.4 std::set / std::unordered_set- set红黑树有序、唯一元素、O(log n) - unordered_set哈希表无序、唯一元素、平均 O(1)六、快速对比总结结构底层是否有序查找复杂度随机访问核心用途静态数组连续内存否O(1)✅固定长度、快速遍历vector动态连续数组否O(1)✅可变长度、随机访问list双向链表否O(n)❌频繁中间增删stack容器适配器LIFOO(1)(仅栈顶)❌后进先出逻辑queue容器适配器FIFOO(1)(两端)❌先进先出逻辑priority_queue堆(完全二叉树)最值优先O(log n)❌取最值、TopKmap红黑树按键有序O(log n)❌有序键值查找unordered_map哈希表无序平均 O(1)❌高速单点键值查找七、补充记忆要点内存栈 ≠ 数据结构栈、内存堆 ≠ 数据结构堆两套概念务必区分开连续数组擅长随机访问不擅长中间插入链表反之红黑树稳定 O(log n)、有序哈希表平均 O(1)、无序BST 的隐患不平衡会退化成链表红黑树本质就是用来保持 BST 平衡