循环队列：深拷贝、赋值与接口封装实战

1. 引言

循环队列是数据结构中的经典实现，它通过复用底层数组空间，让队列在逻辑上首尾相连，从而高效利用内存。本文围绕循环队列的 C++ 实现展开，重点讲解拷贝构造（深拷贝）、赋值运算符重载、代码复用以及接口封装这几个关键点。

2. 循环队列的基本设计

循环队列通常使用数组作为底层存储，配合头尾指针（或下标）来标记队首和队尾。核心思路是：当尾指针到达数组末尾时，通过取模运算回到数组开头，形成逻辑上的环形结构。

设计要点包括：

• 底层存储：使用动态数组，容量在构造时指定。
• 队首与队尾：用两个下标（或指针）分别指向队首元素和下一个可写入位置。
• 空与满的判断：通常牺牲一个存储单元，或使用计数器来区分空队列和满队列。

3. 基础接口封装

为了让使用者不关心内部实现细节，我们对外提供简洁的接口。常见的接口包括：

• push：向队尾插入元素。
• pop：从队首移除元素。
• front：返回队首元素。
• back：返回队尾元素。
• empty：判断队列是否为空。
• full：判断队列是否已满。
• size：返回当前元素个数。

这些接口统一封装在类内部，外部只通过公有方法访问，体现了封装的思想。

4. 拷贝构造与深拷贝

当类中包含动态分配的内存时，默认的拷贝构造函数只会做浅拷贝，导致两个对象指向同一块内存，析构时会出现重复释放的问题。因此必须自定义拷贝构造函数，实现深拷贝。

深拷贝的核心步骤：

示例代码如下：

CircularQueue(const CircularQueue& other)
: capacity(other.capacity), head(other.head), tail(other.tail), count(other.count) {
data = new int[capacity];
for (int i = 0; i < capacity; ++i) {
data[i] = other.data[i];
}
}

5. 赋值运算符重载

在 C++11 及更高版本中，除了拷贝构造和拷贝赋值，还引入了移动语义。对于像 CircularQueue 这样持有动态数组的类，移动操作可以避免不必要的深拷贝，从而显著提升性能。

移动构造函数的必要性在于：当函数返回一个局部队列对象，或使用 std::move 显式转移所有权时，编译器会优先选择移动构造而非拷贝构造。如果没有移动构造，这些场景会退化为深拷贝，造成额外的内存分配和元素复制开销。移动赋值运算符同理，它允许将临时对象的资源直接转移给已有对象，而不是先拷贝再释放。

移动构造和移动赋值的实现核心是「窃取」源对象的资源，并将源对象置为可安全析构的空状态。示例代码如下：

// 移动构造函数
CircularQueue(CircularQueue&& other) noexcept
: data(other.data), capacity(other.capacity),
head(other.head), tail(other.tail), count(other.count) {
other.data = nullptr;
other.capacity = 0;
other.head = 0;
other.tail = 0;
other.count = 0;
}

// 移动赋值运算符
CircularQueue& operator=(CircularQueue&& other) noexcept {
if (this != &other) {
delete[] data; // 释放当前对象持有的旧内存
data = other.data; // 窃取源对象的底层数组
capacity = other.capacity;
head = other.head;
tail = other.tail;
count = other.count;

other.data = nullptr; // 将源对象置为空状态
other.capacity = 0;
other.head = 0;
other.tail = 0;
other.count = 0;
}
return *this;
}

标记为 noexcept 非常重要：它向编译器承诺移动操作不会抛出异常，这样标准库容器（如 std::vector）在扩容时才会优先使用移动构造而不是拷贝构造，从而避免不必要的深拷贝。

性能提升主要体现在以下场景：

• 函数返回队列对象：返回局部队列时，移动构造直接转移底层数组指针，无需重新分配内存和复制元素，代价为 O(1)。
• 临时对象赋值：如 q = makeQueue();，移动赋值直接接管临时对象的资源，避免先深拷贝再释放旧内存。
• 容器扩容：当 std::vector<CircularQueue> 扩容时，noexcept 移动构造让元素以 O(1) 代价搬移，而不是 O(n) 的深拷贝。

对比来看，拷贝构造和拷贝赋值的时间复杂度为 O(n)（n 为队列容量），而移动构造和移动赋值的时间复杂度为 O(1)，因为它们只交换指针和几个整数成员，不涉及任何元素复制。

赋值运算符同样需要处理深拷贝问题。与拷贝构造不同，赋值时目标对象可能已经持有内存，因此需要先释放旧内存，再分配新内存并复制数据。

推荐使用「拷贝并交换」技巧，既能避免重复代码，又能保证异常安全。示例代码如下：

CircularQueue& operator=(const CircularQueue& other) {
if (this != &other) {
CircularQueue temp(other); // 调用拷贝构造
swap(temp); // 交换内部状态
}
return *this;
}

6. 代码复用

拷贝构造和赋值运算符在逻辑上有大量重叠，都是「复制数据」。通过提取私有辅助函数，可以避免重复代码。例如：

• copyFrom(const CircularQueue& other)：负责复制底层数组和状态。
• swap(CircularQueue& other)：交换两个对象的内部成员。

这样，拷贝构造和赋值运算符都可以复用这些辅助函数，代码更简洁，也更容易维护。

7. 完整实现示例

下面给出一个完整的循环队列实现，包含深拷贝、赋值运算符重载和封装接口：

#include <iostream>

class CircularQueue {
private:
int* data;
int capacity;
int head;
int tail;
int count;

void copyFrom(const CircularQueue& other) {
capacity = other.capacity;
head = other.head;
tail = other.tail;
count = other.count;
data = new int[capacity];
for (int i = 0; i < capacity; ++i) {
data[i] = other.data[i];
}
}

void swap(CircularQueue& other) {
std::swap(data, other.data);
std::swap(capacity, other.capacity);
std::swap(head, other.head);
std::swap(tail, other.tail);
std::swap(count, other.count);
}

public:
explicit CircularQueue(int cap) : capacity(cap), head(0), tail(0), count(0) {
data = new int[capacity];
}

~CircularQueue() {
delete[] data;
}

CircularQueue(const CircularQueue& other) {
copyFrom(other);
}

CircularQueue& operator=(const CircularQueue& other) {
if (this != &other) {
CircularQueue temp(other);
swap(temp);
}
return *this;
}

bool push(int value) {
if (count == capacity) return false;
data[tail] = value;
tail = (tail + 1) % capacity;
++count;
return true;
}

bool pop() {
if (count == 0) return false;
head = (head + 1) % capacity;
–count;
return true;
}

int front() const {
return data[head];
}

int back() const {
return data[(tail – 1 + capacity) % capacity];
}

bool empty() const {
return count == 0;
}

bool full() const {
return count == capacity;
}

int size() const {
return count;
}
};

8. 扩展为模板类

上面的实现只支持 int 类型。为了让循环队列能够支持任意数据类型（如 double、string 等），可以将其改造为模板类。改造的核心思路是：把类声明为 template <typename T>，并将底层数组、接口参数和返回值中的 int 替换为类型参数 T。

模板化后的完整实现如下。这里为 push、pop、front、back 等关键接口加入了异常处理：当队列为空时调用 front、back 或 pop，会抛出 std::runtime_error，而不是返回一个无意义的默认值或产生未定义行为。

#include <iostream>
#include <string>
#include <stdexcept>

template <typename T>
class CircularQueue {
private:
T* data;
int capacity;
int head;
int tail;
int count;

void copyFrom(const CircularQueue& other) {
capacity = other.capacity;
head = other.head;
tail = other.tail;
count = other.count;
data = new T[capacity];
for (int i = 0; i < capacity; ++i) {
data[i] = other.data[i];
}
}

void swap(CircularQueue& other) {
std::swap(data, other.data);
std::swap(capacity, other.capacity);
std::swap(head, other.head);
std::swap(tail, other.tail);
std::swap(count, other.count);
}

public:
explicit CircularQueue(int cap) : capacity(cap), head(0), tail(0), count(0) {
data = new T[capacity];
}

~CircularQueue() {
delete[] data;
}

CircularQueue(const CircularQueue& other) {
copyFrom(other);
}

CircularQueue& operator=(const CircularQueue& other) {
if (this != &other) {
CircularQueue temp(other);
swap(temp);
}
return *this;
}

void push(const T& value) {
if (count == capacity) {
throw std::runtime_error("CircularQueue is full");
}
data[tail] = value;
tail = (tail + 1) % capacity;
++count;
}

void pop() {
if (count == 0) {
throw std::runtime_error("CircularQueue is empty");
}
head = (head + 1) % capacity;
–count;
}

T front() const {
if (count == 0) {
throw std::runtime_error("CircularQueue is empty");
}
return data[head];
}

T back() const {
if (count == 0) {
throw std::runtime_error("CircularQueue is empty");
}
return data[(tail – 1 + capacity) % capacity];
}

bool empty() const {
return count == 0;
}

bool full() const {
return count == capacity;
}

int size() const {
return count;
}
};

使用模板类时，只需在声明对象时指定具体类型即可：

CircularQueue<int> qi(5);
qi.push(10);

CircularQueue<double> qd(5);
qd.push(3.14);

CircularQueue<std::string> qs(5);
qs.push("hello");

模板化的好处主要有三点：

• 代码复用：一份实现即可支持任意数据类型，无需为每种类型重复编写队列逻辑。
• 类型安全：在编译期就能检查类型是否匹配，避免运行时类型错误。
• 通用性强：无论是内置类型还是自定义类型，只要支持拷贝构造和赋值，就能直接使用该队列。

为关键接口添加异常处理的好处主要体现在以下几个方面：

• 避免未定义行为：在队列为空时访问 front 或 back，原实现会直接读取底层数组中的无效位置，属于未定义行为；抛出异常后，程序能明确感知错误并安全终止或回退。
• 错误信息明确：std::runtime_error 携带可读的错误描述（如 "CircularQueue is empty"），便于定位问题，而不是面对一个莫名其妙的返回值。
• 接口语义更严谨：push 在队列满时抛出异常，pop 在队列空时抛出异常，让调用方必须显式处理这些边界情况，从而写出更健壮的代码。
• 与标准库风格一致：C++ 标准库容器（如 std::vector 的 at）在越界时同样抛出异常，这种设计让使用者更容易适应。

8. 测试与验证

编写简单的测试代码，验证深拷贝、赋值以及边界条件是否正确：

int main() {
CircularQueue q1(5);
q1.push(10);
q1.push(20);
q1.push(30);

CircularQueue q2(q1); // 拷贝构造
CircularQueue q3(3);
q3 = q1; // 赋值运算符

std::cout << "q2 front: " << q2.front() << std::endl;
std::cout << "q3 size: " << q3.size() << std::endl;

// 边界条件测试
CircularQueue q4(2);
std::cout << "q4 push(1): " << q4.push(1) << std::endl;
std::cout << "q4 push(2): " << q4.push(2) << std::endl;
std::cout << "q4 push(3) (队列满): " << q4.push(3) << std::endl;

CircularQueue q5(3);
std::cout << "q5 pop() (队列空): " << q5.pop() << std::endl;

CircularQueue q6(3);
q6.push(7);
q6.pop();
std::cout << "q6 front() (队列空): " << q6.front() << std::endl;
std::cout << "q6 back() (队列空): " << q6.back() << std::endl;

return 0;
}

运行结果应输出：

q2 front: 10
q3 size: 3
q4 push(1): 1
q4 push(2): 1
q4 push(3) (队列满): 0
q5 pop() (队列空): 0
q6 front() (队列空): 0
q6 back() (队列空): 0

9. 复杂度与性能分析

循环队列的核心接口都基于数组下标和取模运算实现，不涉及元素移动，因此时间复杂度非常理想。各接口的复杂度如下：

• push：O(1)，直接写入队尾下标并更新尾指针。
• pop：O(1)，直接移动队首下标，无需搬移元素。
• front：O(1)，直接返回队首下标处的元素。
• back：O(1)，通过取模定位队尾元素。
• size：O(1)，直接返回计数器。
• empty：O(1)，判断计数器是否为零。
• full：O(1)，判断计数器是否等于容量。

空间复杂度方面，循环队列需要预先分配固定容量的底层数组，因此空间复杂度为 O(n)，其中 n 为队列容量。与普通数组队列（非循环）相比，循环队列最大的优势在于内存利用率：普通数组队列在队首元素出队后，前面的空间无法再被复用，容易造成「假溢出」；而循环队列通过取模运算让队尾回到数组开头，可以反复利用已出队的空间，在相同容量下能容纳更多有效元素。操作效率上，两者在入队、出队时都是 O(1)，但普通数组队列若采用「出队后整体前移」的策略，则每次出队都需要 O(n) 的元素搬移，效率明显更低。

总体而言，循环队列以 O(1) 的时间复杂度完成所有核心操作，并显著提升了底层数组的空间利用率，是数组实现队列时的更优选择；其代价是需要额外维护队首、队尾下标和计数器，并预先确定容量上限。

下表从多个维度对比循环队列与普通数组队列（非循环）的差异：

从对比可以看出，循环队列在空间利用率和出队效率上具有明显优势，尤其适合频繁入队、出队且对内存敏感的场合；普通数组队列实现更直观，但在长期运行中容易因空间无法复用而浪费内存。实际选型时，应根据队列规模、操作频率和内存约束综合权衡。

10. 动态扩容方案

前面实现的循环队列容量是固定的，一旦队列满，push 就会失败。在实际应用中，队列的规模往往难以预先确定，固定容量容易造成空间浪费或容量不足。为此，可以在队列满时自动扩容：申请一个更大的数组，将原有元素按顺序复制过去，并重置头尾指针。

扩容的核心思路如下：

下面给出在模板类 CircularQueue 中加入自动扩容的完整实现。这里将 push 改为：当队列满时先调用 resize 扩容，再插入元素，从而对外表现为「永不失败」的入队操作。

#include <iostream>
#include <string>
#include <stdexcept>

template <typename T>
class CircularQueue {
private:
T* data;
int capacity;
int head;
int tail;
int count;

void copyFrom(const CircularQueue& other) {
capacity = other.capacity;
head = other.head;
tail = other.tail;
count = other.count;
data = new T[capacity];
for (int i = 0; i < capacity; ++i) {
data[i] = other.data[i];
}
}

void swap(CircularQueue& other) {
std::swap(data, other.data);
std::swap(capacity, other.capacity);
std::swap(head, other.head);
std::swap(tail, other.tail);
std::swap(count, other.count);
}

// 扩容：申请新数组，按队列顺序复制元素，重置头尾指针
void resize(int newCapacity) {
T* newData = new T[newCapacity];
for (int i = 0; i < count; ++i) {
newData[i] = data[(head + i) % capacity];
}
delete[] data;
data = newData;
head = 0;
tail = count;
capacity = newCapacity;
}

public:
explicit CircularQueue(int cap) : capacity(cap), head(0), tail(0), count(0) {
data = new T[capacity];
}

~CircularQueue() {
delete[] data;
}

CircularQueue(const CircularQueue& other) {
copyFrom(other);
}

CircularQueue& operator=(const CircularQueue& other) {
if (this != &other) {
CircularQueue temp(other);
swap(temp);
}
return *this;
}

void push(const T& value) {
if (count == capacity) {
resize(capacity * 2); // 队列满时自动扩容为原来的两倍
}
data[tail] = value;
tail = (tail + 1) % capacity;
++count;
}

void pop() {
if (count == 0) {
throw std::runtime_error("CircularQueue is empty");
}
head = (head + 1) % capacity;
–count;
}

T front() const {
if (count == 0) {
throw std::runtime_error("CircularQueue is empty");
}
return data[head];
}

T back() const {
if (count == 0) {
throw std::runtime_error("CircularQueue is empty");
}
return data[(tail – 1 + capacity) % capacity];
}

bool empty() const {
return count == 0;
}

bool full() const {
return count == capacity;
}

int size() const {
return count;
}

int getCapacity() const {
return capacity;
}
};

使用示例：

int main() {
CircularQueue<int> q(2);
q.push(1);
q.push(2);
std::cout << "capacity: " << q.getCapacity() << std::endl; // 2
q.push(3); // 触发扩容
std::cout << "capacity: " << q.getCapacity() << std::endl; // 4
std::cout << "front: " << q.front() << std::endl; // 1
std::cout << "size: " << q.size() << std::endl; // 3
return 0;
}

运行结果应输出：

capacity: 2
capacity: 4
front: 1
size: 3

关于时间复杂度：扩容操作本身需要将全部 n 个元素复制到新数组，代价为 O(n)。但扩容并不是每次 push 都会发生，只有当队列满时才触发。采用「容量翻倍」的策略后，扩容频率会随着容量增大而指数级下降。可以证明，连续执行 m 次 push 的总代价为 O(m)，因此单次 push 的均摊时间复杂度为 O(1)。这与 std::vector 的扩容策略一致。

关于空间开销：扩容时新数组的容量是旧数组的两倍，因此在扩容瞬间会同时存在新旧两块内存，峰值空间约为原容量的 3 倍（旧数组 + 新数组 + 已复制部分）。扩容完成后旧数组被释放，长期来看空间复杂度仍为 O(n)，其中 n 为当前容量。若队列频繁扩容后又大量出队，容量不会自动收缩，可能造成一定的空间浪费；如需回收，可类似地实现 shrink 操作，在元素个数远小于容量时按比例缩小数组。

9. 总结

本文从循环队列的基本设计出发，重点讲解了深拷贝、赋值运算符重载、代码复用和接口封装。掌握这些技巧，不仅能写出正确的循环队列，也能迁移到其他涉及动态内存管理的类设计中。建议读者动手实现一遍，并尝试扩展为模板类，以加深理解。