企业官网建设流程全解析

Hello 算法·队列详解：从 FIFO 基础操作到环形数组的多语言实现

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本文基于开源教程《Hello 算法》俄语版 queue.md 编写。队列（Queue）是遵从"先进先出（FIFO, First-In First-Out）"规则的最基础线性结构之一，在订单处理、任务调度、树与图的广度优先遍历等场景中无处不在。读完本文，你将掌握队列的队首/队尾概念、入队出队的时间复杂度、各语言内置队列 API 的等价用法，并能够依据仓库源码从链表与"环形数组"两条路线亲手实现一个 $O(1)$ 出入队的队列。

什么是队列：先进先出与队首队尾

队列是一种线性数据结构，严格遵守"先来先服务"规则。正如它的名字所暗示的那样，队列模拟的正是日常排队的场景：新来的人不断站到队伍末尾，排在队首的人则一个个先离开。

用术语表达：队伍的开头称为队首（front），队伍的末尾称为队尾（rear）。把元素放入队尾的操作叫入队（enqueue），把队首元素移出队列的操作叫出队（dequeue）。因为只允许"队尾进、队首出"，队列天然保证了处理顺序与到达顺序一致：

队列的基本操作与时间复杂度

常见的队列操作如下表所示。需要注意的是，不同语言对方法的命名存在差异，此处采用与栈（stack）章节一致的命名约定：

无论是入队、出队还是访问队首，都只涉及一端的一步操作，不依赖队列中已有元素的数量，因此三者均为常数时间 $O(1)$。

直接使用语言内置队列

《Hello 算法》强调：日常开发中通常无需重复造轮子，直接使用编程语言自带的队列类即可。下面的示例均在仓库各语言源码中有完整可运行版本，代码中体现了几种典型思路：

• 有专用队列类型：C++ 的std::queue、Java/C#/Kotlin 的Queue；
• 用双端队列/链表充当队列：Python 的collections.deque、Go 的container/list、Rust 的VecDeque；
• 无内置队列，用数组模拟：Swift、JavaScript、TypeScript、Dart、Ruby；
• C 语言没有内置队列，需要读者自行实现（见 ru/codes/c/chapter_stack_and_queue/ 下的链表/环形数组队列）。

from collections import deque # 初始化队列 # 在 Python 中，我们一般使用双向队列 deque 来当作队列使用 # 虽然 queue.Queue() 是纯正的队列类，但不太好用，因此不建议使用 que: deque[int] = deque() # 元素入队 que.append(1) que.append(3) que.append(2) que.append(5) que.append(4) # 访问队首元素 front: int = que[0] # 元素出队 pop: int = que.popleft() # 获取队列的长度 size: int = len(que) # 判断队列是否为空 is_empty: bool = len(que) == 0

/* 初始化队列 */ queue<int> queue; /* 元素入队 */ queue.push(1); queue.push(3); queue.push(2); queue.push(5); queue.push(4); /* 访问队首元素 */ int front = queue.front(); /* 元素出队 */ queue.pop(); /* 获取队列的长度 */ int size = queue.size(); /* 判断队列是否为空 */ bool empty = queue.empty();

/* 初始化队列 */ Queue<Integer> queue = new LinkedList<>(); /* 元素入队 */ queue.offer(1); queue.offer(3); queue.offer(2); queue.offer(5); queue.offer(4); /* 访问队首元素 */ int peek = queue.peek(); /* 元素出队 */ int pop = queue.poll(); /* 获取队列的长度 */ int size = queue.size(); /* 判断队列是否为空 */ boolean isEmpty = queue.isEmpty();

/* 初始化队列 */ Queue<int> queue = new(); /* 元素入队 */ queue.Enqueue(1); queue.Enqueue(3); queue.Enqueue(2); queue.Enqueue(5); queue.Enqueue(4); /* 访问队首元素 */ int peek = queue.Peek(); /* 元素出队 */ int pop = queue.Dequeue(); /* 获取队列的长度 */ int size = queue.Count; /* 判断队列是否为空 */ bool isEmpty = queue.Count == 0;

/* 初始化队列 */ // 在 Go 中，将 list 作为队列来使用 queue := list.New() /* 元素入队 */ queue.PushBack(1) queue.PushBack(3) queue.PushBack(2) queue.PushBack(5) queue.PushBack(4) /* 访问队首元素 */ peek := queue.Front() /* 元素出队 */ pop := queue.Front() queue.Remove(pop) /* 获取队列的长度 */ size := queue.Len() /* 判断队列是否为空 */ isEmpty := queue.Len() == 0

/* 初始化队列 */ // Swift 没有内置队列类，可以把 Array 当作队列来使用 var queue: [Int] = [] /* 元素入队 */ queue.append(1) queue.append(3) queue.append(2) queue.append(5) queue.append(4) /* 访问队首元素 */ let peek = queue.first! /* 元素出队 */ // 由于是数组，removeFirst 的复杂度为 O(n) let pop = queue.removeFirst() /* 获取队列的长度 */ let size = queue.count /* 判断队列是否为空 */ let isEmpty = queue.isEmpty

/* 初始化队列 */ // JavaScript 没有内置队列，可以把 Array 当作队列来使用 const queue = []; /* 元素入队 */ queue.push(1); queue.push(3); queue.push(2); queue.push(5); queue.push(4); /* 访问队首元素 */ const peek = queue[0]; /* 元素出队 */ // 底层是数组，因此 shift() 方法的复杂度为 O(n) const pop = queue.shift(); /* 获取队列的长度 */ const size = queue.length; /* 判断队列是否为空 */ const empty = queue.length === 0;

/* 初始化队列 */ // TypeScript 没有内置队列，可以把 Array 当作队列来使用 const queue: number[] = []; /* 元素入队 */ queue.push(1); queue.push(3); queue.push(2); queue.push(5); queue.push(4); /* 访问队首元素 */ const peek = queue[0]; /* 元素出队 */ // 底层是数组，因此 shift() 方法的复杂度为 O(n) const pop = queue.shift(); /* 获取队列的长度 */ const size = queue.length; /* 判断队列是否为空 */ const empty = queue.length === 0;

/* 初始化队列 */ // Dart 的 Queue 类是双向队列，可以直接当作队列来使用 Queue<int> queue = Queue(); /* 元素入队 */ queue.add(1); queue.add(3); queue.add(2); queue.add(5); queue.add(4); /* 访问队首元素 */ int peek = queue.first; /* 元素出队 */ int pop = queue.removeFirst(); /* 获取队列的长度 */ int size = queue.length; /* 判断队列是否为空 */ bool isEmpty = queue.isEmpty;

/* 初始化双向队列 */ // Rust 的双向队列可以直接当作队列来使用 let mut deque: VecDeque<u32> = VecDeque::new(); /* 元素入队 */ deque.push_back(1); deque.push_back(3); deque.push_back(2); deque.push_back(5); deque.push_back(4); /* 访问队首元素 */ if let Some(front) = deque.front() { } /* 元素出队 */ if let Some(pop) = deque.pop_front() { } /* 获取队列的长度 */ let size = deque.len(); /* 判断队列是否为空 */ let is_empty = deque.is_empty();

// C 语言没有内置队列

/* 初始化队列 */ val queue = LinkedList<Int>() /* 元素入队 */ queue.offer(1) queue.offer(3) queue.offer(2) queue.offer(5) queue.offer(4) /* 访问队首元素 */ val peek = queue.peek() /* 元素出队 */ val pop = queue.poll() /* 获取队列的长度 */ val size = queue.size /* 判断队列是否为空 */ val isEmpty = queue.isEmpty()

# 初始化队列 # Ruby 内置队列（Thread::Queue）没有 peek 和遍历等方法，因此可以把 Array 当作队列来使用 queue = [] # 元素入队 queue.push(1) queue.push(3) queue.push(2) queue.push(5) queue.push(4) # 访问队首元素 peek = queue.first # 元素出队 # 注意：由于是数组，Array#shift 方法的复杂度为 O(n) pop = queue.shift # 获取队列的长度 size = queue.length # 判断队列是否为空 is_empty = queue.empty?

可以看到一个值得注意的取舍：Python/C++/Java/C#/Go/Rust 等语言的内置队列入队出队均为 $O(1)$，而Swift/JavaScript/TypeScript/Ruby 用数组"假装"成队列时，removeFirst/shift需要搬移后续全部元素，出队退化到 $O(n)$。理解这一点正是下文中"为什么需要自己实现环形数组队列"的动机。

手写实现一：基于链表的队列

要"攒一个"队列，我们需要一种能在一端插入、在另一端删除的数据结构。链表和数组都满足这一要求。

链表方案非常直观：把链表的头节点当作队首 front、尾节点当作队尾 rear，约定只能在rear之后追加节点（入队），只能删除front节点（出队）。仓库中的 Python 实现完整演示了这一过程（linkedlist_queue.py）：

class LinkedListQueue: """基于链表实现的队列""" def __init__(self): self._front: ListNode | None = None # 头节点 front self._rear: ListNode | None = None # 尾节点 rear self._size: int = 0 def size(self) -> int: return self._size def is_empty(self) -> bool: return self._size == 0 def push(self, num: int): """入队：在尾节点之后添加节点""" node = ListNode(num) if self._front is None: # 队列为空，front 与 rear 都指向该节点 self._front = node self._rear = node else: # 否则追加到尾节点之后 self._rear.next = node self._rear = node self._size += 1 def pop(self) -> int: """出队：删除头节点""" num = self.peek() self._front = self._front.next self._size -= 1 return num def peek(self) -> int: """访问队首元素""" if self.is_empty(): raise IndexError("队列为空") return self._front.val

Go 版本（linkedlist_queue.go）的思路完全相同，只是借助标准库container/list封装出push/pop/peek/size/isEmpty接口，其中对空队列的pop/peek返回nil而非抛异常。底层本质都是"只操作链表两端"，因此入队出队都是 $O(1)$。

手写实现二：基于"环形数组"的队列

如果直接拿普通数组实现队列，从头部删除元素需要搬移其后所有元素，复杂度为 $O(n)$，出队变得低效。文档给出了一个巧妙的规避办法：

1. 用变量front记录队首元素所在下标，用变量size记录队列当前长度；
2. 定义rear = front + size，即队尾"后一格"的位置；
3. 于是数组中元素的有效区间恒为[front, rear - 1]。

在此基础上：

• 入队 enqueue：把输入元素写入下标rear处，然后size加 1；
• 出队 dequeue：只需把front加 1、size减 1 即可，"物理删除"被巧妙地推迟为"逻辑跳过"。

入队与出队各自只有一步常数操作，因此两者都能达到 $O(1)$。

但新问题随之而来：随着入队出队不断发生，front与rear会一路向右移动，当它们触碰到数组末尾时便无法继续前进了。解决办法是把数组首尾相接、视为环形数组：当front或rear越过数组尾部后，立即"折返"回数组头部继续推进。这种周期性用取余运算即可优雅表达，仓库中的 Python 版环形数组队列（array_queue.py）核心逻辑如下：

class ArrayQueue: """基于环形数组实现的队列""" def __init__(self, size: int): self._nums: list[int] = [0] * size # 用于存储队列元素的数组 self._front: int = 0 # 队首指针，指向队首元素 self._size: int = 0 # 队列长度 def capacity(self) -> int: return len(self._nums) def push(self, num: int): """入队""" if self._size == self.capacity(): raise IndexError("队列已满") # 计算队尾指针：指向队尾索引 + 1 # 通过取余操作实现 rear 越过数组尾部后回到头部 rear: int = (self._front + self._size) % self.capacity() self._nums[rear] = num self._size += 1 def pop(self) -> int: """出队""" num: int = self.peek() # 队首指针向后移动一位，若越过尾部则返回到数组头部 self._front = (self._front + 1) % self.capacity() self._size -= 1 return num def peek(self) -> int: """访问队首元素""" if self.is_empty(): raise IndexError("队列为空") return self._nums[self._front]

核心只有两处取余：

• 入队时rear = (front + size) % capacity；
• 出队时front = (front + 1) % capacity。

Go 版本 array_queue.go 实现了完全一致的取余逻辑（队列满时push直接返回、pop/peek空队列返回nil），其结构体同时维护nums/front/queSize/queCapacity四个字段。值得注意的是 Go 中push遇到queSize == queCapacity便直接返回，属于"静默忽略"而非报错——不同语言对容量边界的处理策略并不相同，阅读源码时值得留意。

仓库配套测试 queue_test.go 专门用一段循环验证了环形回绕的正确性：在容量为 10 的队列上连续执行 10 轮push(i) + pop()，确保指针越过数组末尾后能正确"折返"而不丢失元素顺序。该文件中还保留了性能基准注释（在注释标注的 Mac M1 Pro 环境下测得的数据，仅作参考）：环形数组队列单次操作约 8 ns/op，链表队列约 62 ns/op，从中可以直观感受到两者内存布局带来的差异。

局限与扩展方向

即便是环形数组实现，队列长度依然固定不可变。文档指出：解决方式是把静态数组替换为动态数组并引入扩容机制（当队列满时申请更大的底层数组并搬运数据），感兴趣的读者可以参照仓库中my_list（动态数组）的做法自行实现。

两种实现的对比与取舍

文档明确说明：队列两种实现的对比结论与栈章节基本一致，因此不重复展开。结合仓库源码可归纳为：

• 链表队列：入队出队均为 $O(1)$，无容量上限，天然支持动态增长；代价是每个节点需要额外的指针/对象开销（Python 的ListNode、Go 内部的双向链表节点），且节点在内存中不连续、缓存不友好。
• 环形数组队列：入队出队同样为 $O(1)$，底层数组内存连续、局部性好，访问速度通常更快；代价是容量固定（需要靠扩容机制补救），且需要小心维护front/size/rear三者的取余关系。
• 边界处理上两者也有差异：链表队列理论上只受内存限制，而数组队列存在"队满"状态，需要显式判断（Python 抛IndexError、Go 直接返回/忽略）。

队列的典型应用

• 订单队列：顾客下单后订单进入队列，系统按先后顺序依次处理。在大型促销活动中，短时间内会产生海量订单洪峰，如何用队列削峰填谷、扛住高并发成为核心工程难题。
• 各类"延时任务"：任何需要实现"先来先服务"的场景都适合用队列建模，例如打印机的任务队列、餐厅后厨的出菜队列。队列能在保持处理顺序的同时让插入与取出都高效到 $O(1)$。
• 更广义地，队列还是广度优先搜索、逐层处理、消息缓冲等经典算法与系统设计的通用积木，理解其 FIFO 语义后即可举一反三。

在仓库中继续阅读与验证

• 俄语版章节正文：ru/docs/chapter_stack_and_queue/queue.md，该章节还配套了 Python Tutor 可视化逐步演示入口；
• 语言内置用法的可运行样例：Go 版见 queue_test.go（可直接go test验证），Python 版驱动代码内嵌于各queue/_queue.py文件；
• 链表队列源码：Python linkedlist_queue.py、Go linkedlist_queue.go、C linkedlist_queue.c；
• 环形数组队列源码：Python array_queue.py、Go array_queue.go；
• 若想亲手运行：进入对应语言的代码目录（例如ru/codes/python/chapter_stack_and_queue/下直接执行python3 array_queue.py，或在ru/codes/go/内执行go test ./chapter_stack_and_queue/），即可看到入队、访问队首、出队、长度与判空的完整打印输出，以及环形数组多轮回绕的验证过程。

掌握队列的 FIFO 语义、内置 API 差异与两类底层实现后，你便打通了从"会用"到"会写"的完整链路，也为后续学习双端队列、广度优先遍历等更复杂结构打下基础。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo