数据结构-栈，队列， 堆

顺序栈 (Sequential Stack)顺序栈使用数组来实现。需预先分配一块连续的内存空间。优点 实现简单逻辑清晰。 内存连续访问效率高对CPU缓存友好。缺点 大小固定需要预先指定容量不够灵活。 存在栈满溢出的风险。 扩容成本较高需要重新分配更大的内存并复制所有元素链栈链式栈 (Linked Stack) 链式栈使用链表来实现。通过动态分配节点来存储数据。优点 大小动态可变理论上只受可用内存限制没有栈满溢出的问题。 内存利用率高按需分配。缺点 每个元素需要额外的空间来存储指向下一个节点的指针内存开销稍大。 内存不连续访问效率略低于数组。常用简单数据结构——队列队列Queue是计算机科学中另一种极其重要的基础数据结构。与栈的“后进先出”不同它遵循的核心原则是先进先出FIFO, First-In-First-Out。核心概念与术语队头 (Front)允许进行删除操作的一端。元素从这里“出队”。队尾 (Rear)允许进行插入操作的一端。元素从这里“入队”。入队 (Enqueue)向队尾添加一个新元素的操作。出队 (Dequeue)从队头移除一个元素的操作。查看队头 (Peek/Front)获取队头元素的值但不将其移除空队列 (Empty Queue)不包含任何元素的队列。队列溢出 (Queue Overflow)向一个已满的队列在固定大小的实现中尝试执行入队操作。队列下溢 (Queue Underflow)尝试从一个空队列中执行出队操作。顺序队列 (Sequential Queue)顺序队列使用数组来实现。它需要预先分配一块连续的内存空间并使用两个指针或下标front 和 rear 来管理。 优点 实现简单逻辑清晰。 内存连续访问效率高对CPU缓存友好。 缺点 大小固定需要预先指定容量。 存在一个严重问题——“假溢出”链式队列 (Linked Queue)链式队列使用链表来实现。它通过动态分配节点来存储数据。优点 大小动态可变理论上只受可用内存限制没有队列满溢出的问题。 内存利用率高按需分配。缺点 每个元素需要额外的空间来存储指针内存开销稍大。 内存不连续访问效率略低于数组。循环队列 (Circular Queue)循环队列是顺序队列的优化版本它通过一种巧妙的设计解决了“假溢出”问题。核心思想将数组在逻辑上首尾相连想象成一个环形。当 rear 指针到达数组末尾时如果数组开头有空位它会“绕回来”指向开头继续存放元素。常用简单数据结构——堆为什么内存分配要用「堆结构」操作系统 / C 库 malloc 需要频繁 从空闲内存块里快速选一块最合适的内存分配给用户 回收内存块后重新组织空闲块、快速复用 经典内存分配算法 用小顶堆 / 大顶堆管理空闲链表实现「快速取出目标大小空闲块」典型场景最佳适配分配器 把所有空闲内存块按「块大小」构建小顶堆用户申请 size 内存弹出堆顶最小满足 size 的块分割分配用户 free 回收把空闲块重新插入堆中排序