C++利用链表模板类实现简易队列

前言

队列（queue）是先进先出（first in, first out, FIFO）的线性结构：只在尾部插入，只在头部删除。用链表实现队列的好处是插入和删除都是 O(1)，不需要像动态数组那样在头部删除时搬移元素，也不存在扩容时整体复制的问题。把节点和队列写成类模板，就能用同一份代码存放int、std::string或自定义类型。

这篇文章实现一个教学用的LinkedQueue<T>：单链表、带头尾指针、带元素计数，支持拷贝、移动、push、emplace、pop、front。重点不只是「能跑」，而是把资源管理的几条线讲清楚：析构要逐个释放节点，拷贝要深拷贝，移动后源对象要置空，拷贝构造中途抛异常不能泄漏。

需要先说明：本机没有 C++ 编译环境，下面的代码是按 C++17 标准逐行推演的，没有经过编译或运行。阅读时请重点关注所有权与边界条件，实际使用时再用自己的工具链验证。

一、结构设计与不变量

单链表队列需要两个指针：head_指向队首节点，tail_指向队尾节点；再加一个size_记录元素个数。节点Node含一个T值和一个next指针。只从尾部插入、只从头部删除，所以两个操作都不需要遍历。

这套结构有三条不变量，任何成员函数都必须维持：

为什么强调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()采用迭代。

移动构造直接「偷走」三个成员，然后把源对象的三个成员置成空状态。被移动后的对象仍然可以析构、可以重新赋值，但不要读它的内容——它处于「有效但未指定」的状态。

// 适用于 C++17
#include <cstddef>
#include <stdexcept>
#include <utility>

template <typename T>
class LinkedQueue {
private:
struct Node {
T value;
Node* next;

template <typename... Args>
explicit Node(Args&&... args)
: value(std::forward<Args>(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... Args>
void emplace(Args&&... args) {
Node* node = new Node(std::forward<Args>(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() {
LinkedQueue<int> 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。自己实现队列的价值主要是教学：理解所有权、异常安全和模板类的写法。生产代码优先用标准库容器。

常见坑点

1. 
   
2. ❌pop只移动head_，不delete旧节点。
3. 
   

✅ 先保存Node* node = head_;，移动head_，再delete node;。

1. 
   
2. ❌ 删除最后一个节点后忘记把tail_置空。
3. 
   

✅ 判断head_ == nullptr时同步执行tail_ = nullptr;。

1. 
   
2. ❌ 拷贝构造函数里直接复制head_指针，两个队列共享同一条链。
3. 
   

✅ 遍历源链表，逐节点new一份值，做深拷贝。

1. 
   
2. ❌ 移动构造只复制指针，不把源对象的指针置空。
3. 
   

✅ 偷取后立刻把源对象的head_、tail_置空，size_置零，否则两次析构会重复释放。

1. 
   
2. ❌ 析构函数写成递归释放next，链表很长时栈溢出。
3. 
   

✅ 用while循环逐个保存next再删除当前节点。

1. 
   
2. ❌ 让pop()返回T&或T*，调用方拿到后节点已被释放。
3. 
   

✅ 返回void，取值用front()，先复制再pop()。

1. 
   
2. ❌ 拷贝构造中途push抛异常，已经建立的节点没人释放。
3. 
   

✅ 在copyFrom里捕获所有异常，调用clear()后重新抛出。

1. 
   
2. ❌ 在push里先修改tail_再new，分配失败时链表结构已被破坏。
3. 
   

✅ 先new，成功后再链接并更新tail_与size_。

总结

链表模板队列的难点不在算法，而在所有权：谁分配、谁释放、失败时谁来清理。把这四条不变量和五法则写对，代码就具备可组合的基础；真要用于生产，优先选择std::queue或std::deque，把自研实现留在教学和理解原理的场景。