当前位置：首页 > news >正文

C++STL循环队列实现

news 来源：原创 2025/8/27 3:53:19

核心概念

循环队列（Circular Queue），也称为环形队列，是一种特殊的队列数据结构。它通过将队列的首尾相连，解决了传统队列因出队操作导致的空间浪费问题（即“假溢出”），从而更高效地利用固定大小的内存空间。

传统队列的问题：
- 普通队列基于数组实现时，一旦队尾指针（tail）到达数组末尾，即使队列头部有空闲位置，也无法再插入新元素，导致空间无法复用。
- 例如：数组大小为5，队列经过多次入队和出队后，可能出现头部有空位，但尾部已满的情况，无法继续入队。
循环队列的解决方案：
- 将数组的逻辑首尾相连，形成一个环。
- 通过模运算（%）控制队首（head）和队尾（tail）指针的移动，使其在到达数组末尾后能回到起始位置，重复利用空间。

关键特性

核心指针：
- head：指向队列的第一个元素。
- tail：指向下一个可插入元素的位置。
关键操作：
- 入队（Enqueue）：向队尾插入元素，tail 指针后移。
- 出队（Dequeue）：从队首移除元素，head 指针后移。
空和满的判定：
- 队列空：head == tail 且 count == 0。
- 队列满：head == tail 且 count == capacity（通过计数器实现，无需浪费空间）。
  （传统方法可能用 (tail + 1) % capacity == head 判断队列满，但会浪费一个位置）

实现原理

1. 指针移动规则

入队时：tail = (tail + 1) % capacity
出队时：head = (head + 1) % capacity

2. 元素数量计算

通过 count 变量直接记录当前元素数量，无需依赖 head 和 tail 的位置关系。
元素数量：count = (tail - head + capacity) % capacity（未使用 count 时）。

3. 空间复用

当指针移动到数组末尾时，通过模运算回到数组头部，形成一个逻辑上的“环”。

示例分析

假设队列容量为5，初始状态如下：
head = 0, tail = 0, count = 0，数组为 [ , , , , ]。

入队4个元素（62, 84, 26, 89）：
- head=0, tail=4, count=4，队列为 [62,84,26,89, ]。
- 打印结果：62<-84<-26<-89。
继续入队45：
- vec[4] = 45, tail = 0, count=5，队列已满。
- 队列为 [62,84,26,89,45]，打印结果：62<-84<-26<-89<-45。
尝试入队46：
- 队列已满，操作失败。
出队一次：
- head=1, count=4，队列为 [ ,84,26,89,45]。
- 打印结果：84<-26<-89<-45。

优缺点

优点：

高效利用固定内存空间，避免假溢出。
入队和出队的时间复杂度均为 O(1)。
适用于需要严格限制内存的场景（如嵌入式系统、实时系统）。

缺点：

需要预先分配固定大小，扩容困难。
空和满的判定需谨慎处理，容易出错。

应用场景

缓冲区管理：如键盘输入缓存、网络数据包缓冲。
任务调度：操作系统中的进程就绪队列。
生产者-消费者模型：多线程环境下高效传递数据。
循环任务队列：如打印机任务队列、消息队列。

STL（标准模板库）中没有直接提供固定容量的循环队列（Circular Queue）实现，但可以通过组合现有容器（如 vector 或 deque）及索引管理来模拟循环队列的特性。以下是具体说明和实现示例：

使用vector底层容器实现

通过 vector 存储元素，并用 head 和 tail 索引标记队列的起止位置，利用模运算实现循环。

这个程序实现了一个循环队列（cirqueue），使用C++的模板类和vector作为底层容器。以下是对程序的详细分析：

程序结构

主函数（文档1）:
- 创建容量为5的整型循环队列。
- 连续入队4个元素（62, 84, 26, 89），打印队列。
- 继续尝试入队45（成功）和46（失败，队列已满），再次打印。
- 执行一次出队操作，打印最终队列。
循环队列实现（文档2）:
- 使用vector存储元素，维护head（队首索引）、tail（下一个插入位置）、count（当前元素数量）和capacity（队列容量）。
- 提供enqueue（入队）、dequeue（出队）、isempty（判空）和printqueue（打印队列）方法。

核心逻辑分析

1. 构造函数

explicit cirqueue(size_t capacity) : vec(capacity), head(0), tail(0), count(0), capacity(capacity) {}

初始化vector大小为capacity，元素默认初始化（对于int可能为未定义值）。
head和tail初始为0，count记录当前元素数量。

2. 入队操作（enqueue）

void enqueue(T text) {if (count == capacity) {cout << "" << endl; // 应输出明确提示，如"Queue is full"return;}vec[tail] = text;tail = (tail + 1) % capacity;count++;
}

队列满条件：count == capacity。
元素插入到tail位置，tail循环后移。
当队列满时，拒绝新元素并输出空提示（需改进）。

3. 出队操作（dequeue）

void dequeue() {if (count == 0) {cout << "" << endl; // 应输出明确提示，如"Queue is empty"return;}head = (head + 1) % capacity;count--;
}

队列空条件：count == 0。
移动head指针，不实际删除元素，仅减少count。

4. 打印队列（printqueue）

void printqueue() {for (auto i = 0; i < count; ++i) {auto k = (i + head) % capacity;cout << vec[k];if (i != count - 1) cout << "<-";}cout << endl;
}

按逻辑顺序（从head开始）遍历count个元素，用<-连接。

主函数执行流程

初始状态:
- head=0, tail=0, count=0, capacity=5.
- vector初始值为未定义的int（可能为随机值）。
四次入队（62, 84, 26, 89）:
- tail依次移动到4，count=4。
- 打印结果：62<-84<-26<-89。
第五次入队（45）:
- vec[4] = 45，tail=0，count=5（队列满）。
- 打印结果：62<-84<-26<-89<-45。
第六次入队（46）:
- 队列已满，操作失败，无提示（需改进）。
一次出队:
- head移动到1，count=4。
- 打印结果：84<-26<-89<-45。

主函数测试

#include"cirqueue.h"
int main() {cirqueue<int>que(5);que.enqueue(62);que.enqueue(84);que.enqueue(26);que.enqueue(89);que.printqueue();que.enqueue(45);que.enqueue(46);que.printqueue(); que.dequeue();que.printqueue();

输出结果：

deque为底层容器实现

通过限制 deque 的最大容量并在队列满时删除旧元素：

#include <deque>template<typename T>
class FixedSizeQueue {
public:explicit FixedSizeQueue(size_t max_size) : max_size(max_size) {}void push(T value) {if (dq.size() == max_size) {dq.pop_front(); // 满时删除队首}dq.push_back(value);}// 其他接口与 std::queue 类似private:std::deque<T> dq;size_t max_size;
};

性能对比

实现方式	入队/出队时间复杂度	内存连续性	是否支持动态扩容
基于 `vector`	O(1)	连续	否
基于 `deque`	O(1)	分段连续	否（手动限制）
`boost::circular_buffer`	O(1)	连续	是

如何选择？

需要严格内存控制：用 vector + 环形索引（方法 1）。
需要动态扩容：使用 boost::circular_buffer。
简单场景：基于 deque 手动限制容量（方法 2）。

如果追求 STL 的纯粹性，推荐自己实现方法 1；若允许使用第三方库，直接采用 Boost 的实现更高效且功能完整。