链表实现栈和队列的核心是动态内存分配：栈用头插/头删实现o(1)压弹，判空靠栈顶指针；队列用front/rear双指针分离出入端，需注意空队列时rear同步置null；每次malloc须判null，节点用完即free，禁复用内存。
用链表实现栈和队列，核心在于把“动态内存分配”真正用活——不是只调用 malloc 和 free，而是让每个节点的诞生与消亡都贴合运行时需求。这种灵活性直接决定了结构能否应对不确定数据量、避免空间浪费、支持高频增删。
链表栈：头插即压栈，头删即弹栈
栈的 LIFO 特性天然适配单链表头部操作。所有关键动作都在链表首端完成，无需遍历：
-
push 就是创建新节点，让其
next指向当前栈顶，再把栈顶指针更新为它——两步，O(1) - pop 先取栈顶节点的数据，再将栈顶指针移到下一个节点，最后释放原栈顶内存——不漏 free，防泄漏
- 栈空判断只需检查栈顶指针是否为
NULL，无需额外计数（当然加size字段更便于调试）
链表队列：双指针协同，前后端分离管理
队列的 FIFO 要求一端入、一端出，单靠一个指针不够。必须维护 front（队首）和 rear（队尾）两个指针：
-
enqueue 总在
rear后追加节点，并移动rear；若队列原为空，front也要同步指向新节点 -
dequeue 总从
front取值并后移；若取出后front变成NULL，说明队列变空，此时rear也必须置为NULL，否则悬空 - 初始化时两者都设为
NULL，比设 dummy 头节点更轻量，也更贴近“无预分配”的本质
动态内存分配不是技巧，是设计前提
链表结构的价值，90% 来自运行时按需申请内存。这意味着：
- 每次
malloc都要检查返回值是否为NULL，这是健壮性的底线，不能省 - 节点生命周期由逻辑控制：栈 pop 后立刻 free；队列 dequeue 后立刻 free；销毁整个结构时逐个释放，不跳过中间节点
- 不要复用节点内存（比如清空 data 后反复使用同一块地址），这会掩盖内存管理逻辑，增加调试难度
为什么不用数组实现？对比就清楚了
数组栈/队列看似简单，但面临三个硬约束：
- 容量固定——要么预估过大浪费内存，要么过小频繁扩容（又涉及 memcpy，开销不小）
- 删除元素后空间无法自动回收——哪怕只用过一次，整块数组一直占着
- 插入位置受限——数组中插中间要挪动后续全部元素，而链表只需改两个指针
