前言队列queue是先进先出first in, first out, FIFO的线性结构只在尾部插入只在头部删除。用链表实现队列的好处是插入和删除都是 O(1)不需要像动态数组那样在头部删除时搬移元素也不存在扩容时整体复制的问题。把节点和队列写成类模板就能用同一份代码存放int、std::string或自定义类型。这篇文章实现一个教学用的LinkedQueueT单链表、带头尾指针、带元素计数支持拷贝、移动、push、emplace、pop、front。重点不只是「能跑」而是把资源管理的几条线讲清楚析构要逐个释放节点拷贝要深拷贝移动后源对象要置空拷贝构造中途抛异常不能泄漏。需要先说明本机没有 C 编译环境下面的代码是按 C17 标准逐行推演的没有经过编译或运行。阅读时请重点关注所有权与边界条件实际使用时再用自己的工具链验证。一、结构设计与不变量单链表队列需要两个指针head_指向队首节点tail_指向队尾节点再加一个size_记录元素个数。节点Node含一个T值和一个next指针。只从尾部插入、只从头部删除所以两个操作都不需要遍历。这套结构有三条不变量任何成员函数都必须维持不变量含义破坏后的后果head_ nullptr当且仅当队列为空空队列没有节点空判断错误访问空指针tail_ nullptr当且仅当队列为空尾指针不能悬空下一次push写入已释放节点size_等于实际节点数计数与链表一致size()撒谎边界判断出错为什么强调tail_的不变量考虑只有一个元素的队列head_和tail_指向同一个节点。执行pop()后这个节点被删除head_变成空此时必须同时把tail_置空否则tail_指向已释放内存下一次push会通过tail_-next写入悬垂指针属于未定义行为undefined behavior, UB。pop()的返回类型设计成void与标准库std::queue一致。如果要取队首值先调用front()取得引用把值拷贝或移动到局部变量再调用pop()。不要让pop()返回引用因为节点随即被释放引用立刻悬垂。二、模板节点与特殊成员函数节点用变参模板构造函数把参数完美转发给T的构造函数。这样push可以复用拷贝或移动emplace可以原地构造省掉一次临时对象。队列本身遵循「五法则」rule of five析构、拷贝构造、拷贝赋值、移动构造、移动赋值。只要手写了其中一个通常五个都要考虑。这里用「拷贝并交换」copy-and-swap实现拷贝赋值先按值构造一个副本再与*this交换。副本构造失败时原对象不受影响满足强异常安全保证交换本身只交换三个指针和计数不会抛异常。析构函数必须逐个delete节点。不要写成递归释放例如if (head_) { Node* n head_-next; delete head_; head_ n; ... }这种迭代写法是安全的如果写成「先递归释放next再释放自己」链表很长时可能耗尽调用栈。下面的clear()采用迭代。移动构造直接「偷走」三个成员然后把源对象的三个成员置成空状态。被移动后的对象仍然可以析构、可以重新赋值但不要读它的内容——它处于「有效但未指定」的状态。// 适用于 C17#include cstddef#include stdexcept#include utilitytemplate typename Tclass LinkedQueue {private:struct Node {T value;Node* next;template typename... Argsexplicit Node(Args... args): value(std::forwardArgs(args)...), next(nullptr) {}};Node* head_ nullptr;Node* tail_ nullptr;std::size_t size_ 0;void clear() noexcept {while (head_ ! nullptr) {Node* next head_-next;delete head_;head_ next;}tail_ nullptr;size_ 0;}void copyFrom(const LinkedQueue other) {try {for (Node* p other.head_; p ! nullptr; p p-next) {push(p-value);}} catch (...) {clear(); // 构造中途失败释放已建立的节点再抛出throw;}}public:LinkedQueue() default;LinkedQueue(const LinkedQueue other) {copyFrom(other);}LinkedQueue(LinkedQueue other) noexcept: head_(other.head_), tail_(other.tail_), size_(other.size_) {other.head_ nullptr;other.tail_ nullptr;other.size_ 0;}LinkedQueue operator(const LinkedQueue other) {if (this ! other) {LinkedQueue tmp(other); // 先复制失败则原对象不变swap(tmp);}return *this;}LinkedQueue operator(LinkedQueue other) noexcept {if (this ! other) {clear();head_ other.head_;tail_ other.tail_;size_ other.size_;other.head_ nullptr;other.tail_ nullptr;other.size_ 0;}return *this;}~LinkedQueue() {clear();}void swap(LinkedQueue other) noexcept {std::swap(head_, other.head_);std::swap(tail_, other.tail_);std::swap(size_, other.size_);}void push(const T value) {Node* node new Node(value);if (tail_ ! nullptr) {tail_-next node;} else {head_ node;}tail_ node;size_;}void push(T value) {Node* node new Node(std::move(value));if (tail_ ! nullptr) {tail_-next node;} else {head_ node;}tail_ node;size_;}template typename... Argsvoid emplace(Args... args) {Node* node new Node(std::forwardArgs(args)...);if (tail_ ! nullptr) {tail_-next node;} else {head_ node;}tail_ node;size_;}void pop() {if (head_ nullptr) {throw std::underflow_error(pop on empty queue);}Node* node head_;head_ head_-next;if (head_ nullptr) {tail_ nullptr; // 删掉最后一个节点后尾指针必须清空}delete node;--size_;}T front() {if (head_ nullptr) {throw std::underflow_error(front on empty queue);}return head_-value;}const T front() const {if (head_ nullptr) {throw std::underflow_error(front on empty queue);}return head_-value;}bool empty() const noexcept { return head_ nullptr; }std::size_t size() const noexcept { return size_; }};int main() {LinkedQueueint q;q.push(1);q.push(2);q.emplace(3);while (!q.empty()) {int value q.front();q.pop();(void)value;}return 0;}三、异常安全与复杂度push的异常安全来自「先分配后链接」new Node(...)要么成功要么抛出抛出时链表完全没变链接和计数递增都是不会抛的操作。emplace同理。pop在空队列上抛std::underflow_error其余操作只是移动指针和delete不抛异常。T的拷贝构造如果抛异常new Node(value)里的new表达式会负责释放已分配的内存节点不会泄漏copyFrom的外层catch负责释放此前已经成功加入的节点。这两层保护缺一不可前者保证单个节点不泄漏后者保证整条链不泄漏。复杂度方面push、pop、front都是 O(1)empty、size也是 O(1)。代价是每个元素一次独立的堆分配节点在内存中不连续遍历时缓存局部性不如std::deque或std::vector。对绝大多数业务场景这个代价可以接受如果是高频入队出队且元素很小标准库的std::deque往往更合适。std::queue本身是容器适配器container adaptor默认基于std::deque只暴露push、pop、front、back、empty、size。自己实现队列的价值主要是教学理解所有权、异常安全和模板类的写法。生产代码优先用标准库容器。操作时间复杂度可能抛异常备注push/emplaceO(1)分配失败或T构造抛出链表保持原状popO(1)空队列时抛underflow_error释放一个节点frontO(1)空队列时抛underflow_error返回引用拷贝构造O(n)T拷贝抛出中途失败会清理移动构造O(1)noexcept源对象置空常见坑点❌pop只移动head_不delete旧节点。✅ 先保存Node* node head_;移动head_再delete node;。❌ 删除最后一个节点后忘记把tail_置空。✅ 判断head_ nullptr时同步执行tail_ nullptr;。❌ 拷贝构造函数里直接复制head_指针两个队列共享同一条链。✅ 遍历源链表逐节点new一份值做深拷贝。❌ 移动构造只复制指针不把源对象的指针置空。✅ 偷取后立刻把源对象的head_、tail_置空size_置零否则两次析构会重复释放。❌ 析构函数写成递归释放next链表很长时栈溢出。✅ 用while循环逐个保存next再删除当前节点。❌ 让pop()返回T或T*调用方拿到后节点已被释放。✅ 返回void取值用front()先复制再pop()。❌ 拷贝构造中途push抛异常已经建立的节点没人释放。✅ 在copyFrom里捕获所有异常调用clear()后重新抛出。❌ 在push里先修改tail_再new分配失败时链表结构已被破坏。✅ 先new成功后再链接并更新tail_与size_。总结设计点做法理由队首/队尾head_删除、tail_插入两个方向都是 O(1)资源释放迭代delete避免递归深度与泄漏拷贝深拷贝 拷贝并交换强异常安全避免自赋值问题移动偷指针并置空源对象O(1)防止重复释放取值front()返回引用pop()返回void避免悬垂引用异常先分配后链接失败时结构不变链表模板队列的难点不在算法而在所有权谁分配、谁释放、失败时谁来清理。把这四条不变量和五法则写对代码就具备可组合的基础真要用于生产优先选择std::queue或std::deque把自研实现留在教学和理解原理的场景。