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章节一致的命名约定方法名描述时间复杂度push()元素入队即添加至队尾$O(1)$pop()队首元素出队$O(1)$peek()访问队首元素$O(1)$无论是入队、出队还是访问队首都只涉及一端的一步操作不依赖队列中已有元素的数量因此三者均为常数时间 $O(1)$。直接使用语言内置队列《Hello 算法》强调日常开发中通常无需重复造轮子直接使用编程语言自带的队列类即可。下面的示例均在仓库各语言源码中有完整可运行版本代码中体现了几种典型思路有专用队列类型C 的std::queue、Java/C#/Kotlin 的Queue用双端队列/链表充当队列Python 的collections.deque、Go 的container/list、Rust 的VecDeque无内置队列用数组模拟Swift、JavaScript、TypeScript、Dart、RubyC 语言没有内置队列需要读者自行实现见 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/* 初始化队列 */ queueint 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();/* 初始化队列 */ QueueInteger 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();/* 初始化队列 */ Queueint 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 类是双向队列可以直接当作队列来使用 Queueint 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: VecDequeu32 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 LinkedListInt() /* 元素入队 */ 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.pyclass 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.valGo 版本linkedlist_queue.go的思路完全相同只是借助标准库container/list封装出push/pop/peek/size/isEmpty接口其中对空队列的pop/peek返回nil而非抛异常。底层本质都是只操作链表两端因此入队出队都是 $O(1)$。手写实现二基于环形数组的队列如果直接拿普通数组实现队列从头部删除元素需要搬移其后所有元素复杂度为 $O(n)$出队变得低效。文档给出了一个巧妙的规避办法用变量front记录队首元素所在下标用变量size记录队列当前长度定义rear front size即队尾后一格的位置于是数组中元素的有效区间恒为[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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考