做嵌入式久了会发现，数据结构不是算法面试里的概念，而是固件每天都在做的取舍：一段 RAM 怎么分配，一路中断数据怎么接住，一个任务队列怎么不丢消息，一个查表逻辑怎么在最坏情况下仍然可控。
小系统拼到最后，差距往往不在某个语法技巧，而在对数组、链表、栈、队列、树、堆、哈希表这些基础结构的使用边界是否清楚。选对了，代码简单、时序稳定；选错了，后期就会被内存碎片、指针野飞、偶发丢包和调度抖动反复折磨。
1 数据结构首先是工程约束的表达
嵌入式开发里的数据结构，第一要看内存，第二要看时序，第三才是代码写起来是否优雅。
数组适合容量固定、下标访问频繁的场景。它的优势很直接：连续内存、访问 O(1)、缓存友好，特别适合 ADC 采样缓存、查表、状态映射、寄存器配置表等逻辑。缺点也同样明显，容量一旦定死，扩展就不灵活。
链表刚好相反。它适合动态插入删除，但每个节点都要额外保存指针，还要面对 malloc/free、内存泄漏、野指针和碎片化问题。在资源紧张的 MCU 上，如果没有稳定的内存池，链表不是不能用，而是要非常克制地用。
栈和队列更贴近日常固件。函数调用、中断现场保护、局部变量都离不开栈；串口接收、日志缓存、生产者消费者模型常常依赖队列或环形缓冲区。哈希表、树和堆则更多出现在快速查找、优先级调度、协议映射、定时器管理等稍复杂的固件模块中。
真正成熟的选型，不是背复杂度，而是先问：容量是否固定？是否需要快速查找？是否允许动态分配？是否会在 ISR 中访问？最坏延迟能不能接受？这些问题回答清楚，结构基本就选出来了。
2 线性结构是驱动代码的基本功
数组是最常用也最容易被低估的数据结构。很多驱动里的寄存器初始化表、GPIO 映射表、波形采样缓存，本质上都是数组。数组的关键不是会不会定义，而是边界是否严格、长度是否集中管理、访问是否避免越界。量产问题里，越界写坏相邻变量，比想象中常见得多。
链表的价值在于灵活，但嵌入式里不能只看灵活。裸机或小 RTOS 项目里频繁动态申请节点，很容易造成碎片，运行几天后才暴露问题。更稳妥的做法通常是固定节点池：节点预分配，空闲链表管理，分配失败有明确降级策略。这样既保留链表的插入删除优势，又把内存风险压住。
栈是系统稳定性的底线。任务栈开小了，问题往往不是立刻复现，而是在某个深层调用、某次中断嵌套、某个日志打印路径里突然崩掉。工程上要养成测栈水位的习惯，尤其是带 printf、协议解析、加解密、文件系统的任务，不要凭感觉给栈。
队列和环形缓冲区是通信驱动的核心。UART、SPI、I2C 接收缓存常用 ring buffer，把 ISR 中的快速收包和任务中的慢速解析解耦。这里最重要的是满、空条件要定义清楚，head/tail 更新要考虑并发访问。若 ISR 和任务同时读写索引，临界区或原子操作不能省。
3 非线性结构解决查找和调度问题
树、堆、图、哈希表在小项目里不一定天天出现，但一旦系统复杂度上来，它们能显著降低模块之间的混乱。
树适合表达层级关系，比如菜单、文件目录、状态机分支、协议对象关系。它的问题在于遍历和递归深度。PC 程序里递归写起来舒服，MCU 上却可能吃掉不可控的栈空间。深度可控时可以递归，深度不确定时最好改成显式栈或迭代遍历。
堆常用于优先级队列。比如多个定时任务需要按最早到期时间调度，用最小堆比每次全表扫描更合适。代价是插入、删除需要维护堆序，代码比普通数组复杂一些。项目不大时，全表扫描反而更可靠；当任务数量变多、调度频率变高，堆的价值才会明显。
图适合描述依赖和连接关系，例如传感器网络、状态跳转、通信拓扑。嵌入式里使用图结构时，要特别关注存储方式。邻接矩阵访问简单但耗内存，邻接表节省空间但指针更多。对于节点数量固定的小系统，静态数组形式的邻接表通常更稳。
哈希表适合快速映射，比如命令字到处理函数、设备 ID 到对象、错误码到描述。平均 O(1) 很诱人，但冲突处理必须认真设计。开放定址要考虑负载因子，链地址法要考虑节点来源。对实时系统来说，还要关心最坏情况，而不是只看平均性能。
4 从固件场景倒推结构选型
数据结构选型最有效的方法，是从场景往回推。
串口数据流通常选择环形缓冲区。ISR 只做最少工作：读寄存器、写入 buffer、移动 head，然后退出。协议解析放到任务里慢慢处理。这样能减少中断占用，也能承受短时间突发流量。若波特率高、数据连续，还要结合 DMA，把 CPU 从字节搬运里解放出来。
配置表和命令解析通常有两种做法。命令少于十几个，用数组线性查找简单可靠；命令多且查询频繁，可以使用排序数组二分查找，或者在 RAM 允许时做哈希映射。不要为了“高级”一上来就写复杂结构，小表用小办法，维护成本最低。
RTOS 任务和中断之间传递数据，要优先考虑确定性。队列、消息邮箱、环形缓冲区都可以，但 ISR 里不能做可能阻塞的操作，也不应该做大段解析。共享数据要么用临界区保护，要么使用单生产者单消费者模型降低锁的复杂度。
内存紧张的 MCU 上，动态分配要谨慎。数组、静态队列、对象池往往比通用 malloc 更适合固件。需要可变对象时，用固定块内存池会更容易定位问题，也更利于做水位统计和异常恢复。
5 总结
嵌入式里的数据结构，价值不在“会多少种”，而在能不能把结构放到具体约束里判断：RAM 是否够、延迟是否确定、并发是否安全、异常是否可恢复、量产后是否容易定位。
数组、链表、栈、队列、树、堆、图、哈希表都不神秘。真正拉开差距的是：在驱动、中断、RTOS、通信协议和内存管理这些真实场景里，知道什么时候用简单结构，什么时候引入复杂结构，以及什么时候坚决不用。
下一主题
