七、顺序栈与链栈的优缺点对比

1. 顺序栈优缺点

优点

• 存取效率高：基于数组实现，栈顶元素可通过下标直接访问，时间复杂度为O(1)
• 实现简单：无需额外的指针域，数据结构直观，代码编写难度低
• 空间连续：内存空间连续，缓存命中率高，访问速度快

缺点

• 容量固定：静态数组的大小在初始化时确定，无法动态扩容，容易出现栈满溢出的情况
• 内存浪费：若预分配的数组空间过大，会造成内存资源的闲置浪费
• 不适合多栈共享：单个顺序栈对内存的利用率较低，多栈场景下需借助共享栈结构优化

2. 链栈优缺点

优点

• 动态扩容：基于链表实现，可根据需求动态申请结点内存，无栈满限制（仅受限于系统内存）
• 内存利用率高：仅在需要时分配内存，不会造成空间闲置，适合元素数量不确定的场景
• 灵活度高：便于实现多栈结构，各链栈独立管理，互不干扰

缺点

• 存取效率略低：访问元素需通过指针遍历（仅栈顶可直接访问），且存在指针域的额外开销
• 实现复杂：需要处理结点的创建、销毁和指针的指向，代码逻辑比顺序栈繁琐
• 内存碎片化：频繁的结点增删会导致内存空间碎片化，降低内存整体利用效率

3. 顺序栈与链栈的对比

栈的实现主要有两种方式：基于数组的顺序栈和基于链表的链栈。通过下方的动态对比，你可以直观地感受到它们在内存管理和扩容特性上的区别。

核心区别

特性	顺序栈 (Sequence Stack)	链栈 (Linked Stack)
存储空间	连续内存空间	非连续，动态申请
容量限制	有最大容量 MaxSize	无限制 (取决于内存)
指针	top 是整数下标	top 是指针，指向头结点
入栈操作	判断是否满 -> data[++top] = x	malloc 新节点 -> 头插法

动态演示

1. 尝试连续 Push 7个元素，观察顺序栈报错"栈满"，而链栈依然可以增长。
2. 观察链栈每个节点的 Addr (模拟内存地址) 是随机的，体现了离散存储的特性。

准备就绪

顺序栈 (Array Stack)

• 内存连续
• 容量固定 (Max=6)
• 依靠 top 下标

Top➜

链栈 (Linked Stack)

• 内存离散 (随机地址)
• 理论无上限
• 依靠 next 指针

NULL (栈空)

3. 适用场景对比

栈类型	适用场景
顺序栈	元素数量固定、对存取效率要求高、内存资源充足的场景，如计算器的表达式求值、简单的括号匹配
链栈	元素数量不确定、需动态扩容、内存资源紧张的场景，如复杂的递归模拟、多任务的栈管理