队列（Queue）

定义

队列是一种操作受限的线性数据结构，遵循**先进先出（FIFO, First In First Out）**原则。

核心特性

  • 只能在队尾插入元素（入队，enqueue）
  • 只能在队头删除元素（出队，dequeue）
  • 类比：排队买票，先到先服务

基本 API

|,,|,,|,,,--| | push(E e) / enqueue(E e) | 向队尾插入元素 | O(1) | | pop() / dequeue() | 从队头删除并返回元素 | O(1) | | peek() / front() | 查看队头元素（不删除） | O(1) | | size() | 返回队列中元素个数 | O(1) |

底层实现

  • 基于数组实现：需使用环形数组避免空间浪费（见环形数组）
  • 基于链表实现：使用双链表，头部作为队头、尾部作为队尾，增删均为 O(1)（见用链表实现队列栈）

相关概念

  • BFS：广度优先搜索使用队列实现
  • 优先级队列：特殊类型的队列，按优先级出队
  • 环形数组：队列的数组实现方式
  • 链表：队列的链表实现方式

Link to this note

二叉树

type: concept tags: [数据结构, 树结构, 算法基础] created: 2026-05-03 updated: 2026-05-03二叉树（Binary Tree）定义二叉树是每个节点最多有两个子节点（左子节点和右子节点）的树结构。它是大多数高级数据结构的基础，也是一种核心算法思维。核心特性基本结构class TreeNode { int val; TreeNode left, right; }重要性数据结构基础：红黑树、多叉树、二叉堆、图、字典树、并查集、线段树等高级数据结构均基于二叉树算法思维：回溯、BFS、动态规划等穷举算法本质是将问题抽象为树结构常见类型| 类型 | 英文术语 | 特点 | |------|----------|------| | 满二叉树 | Perfect Binary Tree | 每层节点全满，总节点数 = 2^h - 1（h为深度） | | 完全二叉树

优先级队列

type: concept tags: [数据结构, 优先级队列, 二叉堆, 队列] created: 2026-05-05 updated: 2026-05-05优先级队列（Priority Queue）基于二叉堆实现的数据结构，能够按照元素的优先级顺序（而非插入顺序）取出元素。定义优先级队列是一种特殊的队列，每个元素都有优先级，出队时总是优先级最高（或最低）的元素先出队。通常使用二叉堆（小顶堆或大顶堆）作为底层实现，保证插入和删除的时间复杂度为 O(log N)。核心特性| 特性 | 说明 | |------|------| | 底层结构 | 二叉堆（数组实现的完全二叉树） | | 插入元素 | O(log N) | | 删除堆顶 | O(log N) | | 查看堆顶 | O(1) | | 常见类型 | 小顶堆（最小元素优先）、大顶堆（最大元素优先） |基本原理优先级队列底层使用数组实现，但逻辑上是一棵完全二叉树，依靠 swim（上浮）和 sink（下沉）方法维护堆的性质：插入元素：将元素追加到数组末尾，然后调用 swim

层序遍历

type: concept tags: [二叉树, 遍历, BFS, 队列] created: 2026-05-05 updated: 2026-05-05层序遍历（Level Order Traversal）定义层序遍历是二叉树按层级从上到下、每层从左到右遍历的方式。它是广度优先搜索（BFS）在二叉树上的应用。void levelTraverse(TreeNode root) { if (root == null) return; Queue<TreeNode> q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) {

环形数组

type: concept tags: [数据结构, 数组, 队列, 栈] created: 2026-05-03 updated: 2026-05-03环形数组（Circular Array/Ring Buffer）是一种通过模运算实现循环复用的数组结构，避免普通数组增删时的元素移位开销。核心特性底层是普通静态数组，通过头指针（head）和尾指针（tail）标记有效区间利用模运算（index % 数组长度）实现指针循环移动，无需移动元素支持 O(1) 时间复杂度的头尾增删操作应用场景实现队列/双端队列（避免出队时的数组移位）实现栈（简化动态数组的扩缩容逻辑）循环缓冲区（如网络IO、日志缓冲）相关概念[[数组]][[队列]][[栈]][[动态数组]]

index

Harness Engineering Wiki - 内容索引本页面由 Claude 自动维护，每次 ingest 新资料后更新📊 Stats总页面数: 151实体页: 2概念页: 81摘要页: 62对比页: 6最后更新: 2026-05-09📚 摘要页 (Summaries)| 页面链接

log

Harness Engineering - 操作日志本页面记录所有 Claude 的操作记录，仅追加，不修改历史记录[2026-05-02] init | 初始化仓库结构创建 raw/ 目录结构（articles, papers, images）创建 wiki/ 目录结构（entities, concepts, summaries, comparison）创建 wiki/index.md 索引页创建 wiki/log.md 操作日志仓库初始化完成[2026-05-02] ingest | 时间空间复杂度入门保存原始内容到 raw/articles/复杂度分析基础.md创建摘要页 wiki/summaries/2026-05-02 时间空间复杂度入门.md侧重：复杂度分析的实用方法（Big O 简化估算技巧）更新 wiki/index.md：摘要页数量 0→1注意：labuladong 实体和复杂度概念首次出现，暂不创建独立页（需 ≥2 篇来源）[2026-05-02] ingest | 数组基础（labuladong）提取网页内容（defuddle）并创建摘要页 wiki/summaries/2026-05-02 数组基础.md创建实体页

BFS框架

type: summary tags:BFS算法框架LeetCode最短路径 created: 2026-05-06 updated: 2026-05-06BFS 算法框架[[raw/articles/2026/05/BFS框架]]一句话总结BFS 算法的本质是二叉树的层序遍历扩展到图结构，通过队列实现按层级扩散搜索，适合求解最短路径问题。核心要点1. BFS 与树/图遍历的关系DFS/回溯 的本质是二叉树的递归遍历（前中后序）BFS 的本质是二叉树的层序遍历扩展到图结构从基础数据结构到高级算法的推导路径：二叉树遍历 → 多叉树遍历 → 图遍历（加 visited 数组）→ BFS 算法BFS 适合最短路径问题，因为它按层扩散，第一次到达目标时步数最少2. BFS 通用框架（三种写法）第一种写法（简单但局限大）：// 从 start 开始 BFS，寻找 target void bfs(Node start, Node target) { Queue<Node> q = new LinkedList<>();

二叉树遍历基础

type: summary tags: [二叉树, 遍历, DFS, BFS, 递归, 层序遍历, 前序遍历, 中序遍历, 后序遍历] created: 2026-05-03 updated: 2026-05-03二叉树遍历基础[[raw/articles/2026/05/二叉树遍历基础]]一句话总结二叉树只有 递归遍历 和 层序遍历 这两种，再无其他。递归遍历可以衍生出 DFS 算法，层序遍历可以衍生出 BFS 算法。核心内容一、递归遍历（DFS）1.1 遍历框架递归遍历的核心是以下框架，遍历顺序固定（先左后右）：// 基本的二叉树节点 class TreeNode { int val; TreeNode left, right; } // 二叉树的递归遍历框架 void traverse(TreeNode root) {

双端队列实现

type: summary tags: [数据结构, 双端队列, 队列, 链表, 数组, Java] created: 2026-05-03 updated: 2026-05-03双端队列实现[[raw/articles/2026/05/双端队列实现]]核心要点双端队列（Deque）基本原理双端队列（double-ended queue）是一种允许在队头和队尾两端都进行插入和删除操作的线性数据结构。对比标准队列：标准队列（Queue）：FIFO，只能队尾插入、队头删除双端队列（Deque）：队头和队尾都可以插入/删除，不再满足 FIFO类比：标准队列 → 排队买票（先来先买）双端队列 → 过街天桥（两端都可以进出）API 接口class MyDeque<E> { void addFirst(E e); // O(1) 队头插入 void addLast(E e);

数组实现队列和栈

type: summary tags: [数组, 栈, 队列, 动态数组, 环形数组, 时间复杂度] created: 2026-05-03 updated: 2026-05-03数组实现队列和栈[[raw/articles/2026/05/数组实现队列和栈]]一句话总结用数组作为底层数据结构实现栈和队列：栈用动态数组尾部作为栈顶（O(1)），队列用环形数组实现 FIFO 操作（O(1)）。关键要点1. 用数组实现栈方法：把动态数组的尾部作为栈顶时间复杂度：push() - O(1)：arr.add(e)pop() - O(1)：arr.remove(arr.size() - 1)peek() - O(1)：arr.get(arr.size() - 1)为什么不选头部作为栈顶：数组头部增删是 O(n)，不符合栈的效率要求2. 用环形数组实现栈方法：使用 CycleArray 类，以头部作为栈顶时间复杂度：O(1)（环形数组头部增删是 O(1)）API 映射：push() → addFirst()pop() → removeFirst()3. 用环形数组实现队列方法：复用 CycleArray 类实现标准队列时间复杂度：O(1)API 映射：push() → addLast()（入队）pop() →

队列和栈基础

type: summary tags: [队列, 栈, 数据结构, 操作受限] created: 2026-05-03 updated: 2026-05-03队列和栈基础[[raw/articles/2026/05/队列和栈基础]]核心要点队列和栈都是操作受限的数据结构，基于数组（顺序存储）和链表（链式存储）实现。队列（Queue）特性：先进先出（FIFO — First In First Out）操作限制：只能在队尾插入元素，在队头删除元素类比：排队买票，先来的先离开栈（Stack）特性：先进后出（LIFO — Last In First Out）操作限制：只能在栈顶插入和删除元素类比：一摞盘子，最后放的在最上面，最先被拿走基本 API队列 API| 方法 | 描述 | 时间复杂度 | |------|------|-----------| | push(E e) | 向队尾插入元素 | O(1) | | pop() | 从队头删除并返回元素 | O(1) | | peek()

Interactive Graph