Learn-Algorithms 笔记精讲：数组与循环数组（环形队列）原理及应用

教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载本篇技术指南以 Learn-Algorithms 仓库中 数组.md 为核心系统讲解数组的内存特性、与链表的性能差异以及循环数组环形队列/循环队列的头尾指针设计原理、优缺点及其在栈、队列和生产者—消费者场景中的典型应用。读完本文你将掌握环形队列的核心数据结构设计、指针推进规则、判空判满策略并能结合仓库源码理解其在实际工程如 JavaArrayBlockingQueue中的落地方式。一、数组的本质与特点数组是计算机中最基础的数据结构它把一组同类型元素存放在一段连续的内存空间中通过下标即可直接计算出元素的地址实现随机访问。内存连续局部性良好由于元素在物理上相邻遍历数组时能充分利用 CPU 缓存局部性原理这也是数组在顺序访问场景下性能优于链表的重要原因。随机访问 O(1)给定下标i可以通过base i * sizeof(type)直接定位元素。空间一次性分配有界创建数组时必须一次性申请足够大的连续内存一旦容量不足扩容需要重新分配一块更大的空间并把旧数据全部复制过去代价较高。删除元素代价高从数组中间删除一个元素需要把后续所有元素前移时间复杂度为 O(N)。数组与链表的对比仓库 2 List/README.md 中给出了清晰的对比结论维度数组链表内存布局连续利于局部性原理不连续无法按索引计算地址扩容需重新分配整块更大空间并复制数据有界无扩容问题按需分配节点随机访问O(1)O(N)只能顺序遍历有序查找O(log N) 二分查找O(N)删除O(N)需移动后续元素O(1)只需修改指针空间开销无指针额外开销每个节点需额外存储指针占用更多空间从源码结构看仓库 队列.h 中的链式队列实现也印证了这一点Queue结构维护head、tail两个指针插入只需q-tail-next newNode; q-tail newNode;enQueue删除只需调整q-head-nextdeQueue均无需移动元素。二、循环数组环形数组的设计普通数组作为队列的底层存储时会面临一个经典问题出队时队头指针不断后移队头前面的空间虽然空闲却无法再利用造成内存浪费。循环数组环形数组/环形队列正是为解决这一问题而生它在逻辑上把数组的首尾相接让队头指针绕回数组开头继续使用已释放的空间。核心特点原文档总结了循环数组的三个核心特点长度固定下标不会越界虽然物理上是普通数组但通过取模运算下标对容量取余把指针限制在[0, capacity)范围内。使用两个指针标识头尾下标默认均为 0头指针head/takeIndex指向队首元素尾指针tail/putIndex指向下一个可写入位置。方便实现栈与队列以队列为例——新增元素时头下标加 1即写入位置tail后移删除元素时尾下标加 1即读取位置head后移。指针推进规则队列入队enqueue arr[tail] element; tail (tail 1) % capacity; 队列出队dequeue element arr[head]; head (head 1) % capacity;当head tail时队列为空当(tail 1) % capacity head时队列为满通常会空出一个槽位来区分空与满两种状态因为只用两个指针时空和满的指针关系是相同的。环形数组的缺点原文档明确指出头尾之间的元素不好维护从中间删除了某个元素会出现数组空隙。这是环形数组的固有局限它擅长两端操作队头出、队尾入但不擅长中间位置的随机删除。若从中间删除元素后续元素需要整体搬移以填补空隙代价为 O(N)且搬移时还需处理跨环环绕回绕的情况逻辑比普通数组更复杂。因此环形数组通常只用于 FIFO先进先出或 LIFO后进先出场景而不是作为通用集合使用。三、循环数组解决顺序队列的内存浪费问题仓库 队列.h 中同时定义了顺序队列SqQueue和链式队列Queue其代码注释清晰描述了顺序存储队列的问题队列采用顺序存储时有一个毛病队列操作一段时间后头指针到了队列容器的尾部而头指针前面的容器内存不可用了造成内存极大的浪费这个问题可以通过循环队列来解决。在链式队列上则不存在这样的问题。typedef struct Node{ ElemType *elem; ElemType *head; // 队头指针 ElemType *tail; // 队尾指针 int length; // 当前队列长度 int size; // 容器容量可扩容 }SqQueue;这正是循环数组的价值所在把head、tail两个指针的回绕wrap-around处理引入顺序存储队列即可复用队头释放的空间避免越用越靠后、前面全浪费的现象。这份 C 代码为原文档中使用 2 个指针标识头尾下标的抽象描述提供了直接的实现佐证。四、实际案例Java ArrayBlockingQueue原文档指出Java 的ArrayBlockingQueue就是一个典型的环形数组实现它使用takeIndex和putIndex两个下标分别标识取与放的位置与文档所述的头尾两个指针一一对应新增元素时在putIndex处写入并令putIndex inc(putIndex)内部实现为(putIndex 1) % items.length取出元素时从takeIndex读取并同样做取模回绕当takeIndex putIndex时队列为空count 0因为内部使用ReentrantLock与两个Condition保护它也是线程安全的有界阻塞队列适合生产者—消费者模型。理解环形数组的头尾指针机制是读懂ArrayBlockingQueue、Redis 环形缓冲区等经典实现的基石。五、循环结构的另一种形态循环链表循环数组是数组 逻辑回绕而循环链表则是链表 尾节点指向头节点。两者共享环形的抽象思想。仓库中 QPS Counter.md 展示了一个用双向循环链表统计接口 QPS、实现限流的示例static AtomicInteger qpsCount 100; //线程安全 static volatile long lastSenconds System.currentTimeMillis()/1000; // 1 计数器 public static boolean tryAcquire() { long current System.currentTimeMillis()/1000; if(current lastSenconds){ if (qpsCount-- 0) {//CAS api return true; } else { //限流 return false; } } else{//下一个时间窗口 lastSenconds current; qpsCount 100; return true; } }该实现以秒为时间窗口重置计数配合循环链表可进一步组织多个时间窗口的计数节点实现滑动窗口式限流。这说明环形结构在队列、计数器、缓冲等需要周期性复用空间的场景中应用广泛。六、小结数组连续内存、随机访问 O(1)、删除 O(N)、扩容有界循环数组 定长数组 头尾双指针 取模回绕适合实现栈、队列能复用已释放空间循环数组的短板在于中间元素难以维护随机删除会产生空隙典型工程范例JavaArrayBlockingQueuetakeIndex/putIndex环形思想同样延伸至循环链表等结构可用于 QPS 计数、限流等场景。相关材料可继续阅读仓库内的 链表与数组对比、循环队列实现头文件 以及 QPS 计数器实现。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐Learn-Algorithms项目中的队列优化循环队列实现Learn Algorithms项目中的队列优化循环队列实现 你是否在处理数据时遇到过队列内存浪费严重的问题是否想知道如何让队列操作更高效本文将详细介绍L教程Learn-Algorithms 面试题精讲堆与栈、队列的数据结构及五大经典算法题Learn Algorithms 面试题精讲堆与栈、队列的数据结构及五大经典算法题 导读 本文基于 Learn Algorithms https://lin教程《Hello 算法》栈与队列练习题精讲LIFO/FIFO 顺序推导、环形数组与双向队列、括号匹配实战《Hello 算法》栈与队列练习题精讲LIFO/FIFO 顺序推导、环形数组与双向队列、括号匹配实战 本篇技术指南以 hello algo 仓库中 俄罗斯语版教程文档示例工程教育上一篇LifeOS Pulse Index 适配器深度解析用提示词模板把领域目录变成结构化 JSON 页面下一篇Fairseq ASR 实战指南基于 VGG-Transformer 与 wav2letter 组件的语音识别训练与解码全流程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考