基础数据结构题单

从栈、队列、堆、并查集到单调栈和单调队列，建立后续图论、树和区间算法所需的数据结构基础。

0 / 0 已完成

基础数据结构题单

数据结构题的训练目标不是记住 API，而是知道每种结构维护了什么信息，以及为什么能把一次操作降到合适的复杂度。

一、栈与表达式

先掌握后进先出、括号匹配和表达式求值。遇到“最近的、还没有匹配的对象”，优先想到栈。

二、队列与模拟

队列适合处理先进先出的事件；循环队列和双端队列则是滑动窗口与 BFS 的基础。

luogu P1996 约瑟夫问题题解
· P1996 约瑟夫问题
luogu P1540 [NOIP 2010 提高组] 机器翻译题解
· P1540 机器翻译
luogu P1160 队列安排题解
· P1160 队列安排
luogu P2058 [NOIP 2016 普及组] 海港题解
· P2058 海港

三、堆与优先队列

堆解决“动态加入元素并反复取最小/最大值”的问题。先做模板，再做哈夫曼合并和多路归并。

luogu P3378 【模板】堆题解
· P3378 【模板】堆
luogu P1090 [NOIP 2004 提高组] 合并果子题解
· P1090 合并果子
luogu P1631 序列合并题解
· P1631 序列合并
luogu P2085 最小函数值题解
· P2085 最小函数值

四、并查集

并查集维护动态连通块。重点理解路径压缩、按秩合并，以及“把额外关系挂在集合代表元上”的扩展方式。

luogu P3367 【模板】并查集题解
· P3367 【模板】并查集
luogu P1551 亲戚题解
· P1551 亲戚
luogu P1955 [NOI2015] 程序自动分析题解
· P1955 程序自动分析
luogu P1455洛谷原题
· P1455 搭配购买

五、单调栈与单调队列

当题目只关心窗口中的最值，或要求找到左侧/右侧第一个更大元素时，单调结构可以删除永远不可能成为答案的元素。

luogu P5788洛谷原题
· P5788 【模板】单调栈
luogu P2866 [USACO06NOV] Bad Hair Day S题解
· P2866 Bad Hair Day S
luogu P1886 【模板】单调队列 / 滑动窗口题解
· P1886 【模板】单调队列 / 滑动窗口
luogu P2032 扫描题解
· P2032 扫描

过关标准

做完本题单后，应能解释：

text

1
2
3为什么这个操作符合栈/队列/堆的顺序：
为什么某个元素可以从单调结构中永久删除：
并查集合并后，哪些信息仍然可以代表整个集合：