c++怎么实现一个环形队列_c++循环队列数据结构实现-C++-PHP中文网

c++怎么实现一个环形队列_c++循环队列数据结构实现

冰火之心

发布： 2025-10-23 18:17:02

原创

353人浏览过

环形队列利用固定数组和取模操作实现FIFO，通过front和rear指针循环移动，采用浪费一个空间的方法区分空满状态，代码简洁高效。

c++怎么实现一个环形队列_c++循环队列数据结构实现

环形队列（也叫循环队列）是一种线性数据结构，它通过固定大小的数组实现队列的先进先出（FIFO）特性，并利用“取模”操作让队尾和队头在数组中循环移动，避免普通队列中因频繁出队导致的空间浪费。

环形队列的基本原理

使用一个固定大小的数组存储元素，配合两个指针（实际是整型索引）：

front：指向队列第一个元素的位置
rear：指向下一个插入位置的索引（即队尾的后一位）

通过 (index + 1) % capacity 实现索引的循环跳转。当 rear == front 时，队列可能为空或为满，因此需要额外处理以区分这两种状态。

如何区分空与满

常见方法有三种：

立即学习“C++免费学习笔记（深入）”；

腾讯智影-AI数字人

基于AI数字人能力，实现7*24小时AI数字人直播带货，低成本实现直播业务快速增增，全天智能在线直播

查看详情

使用一个额外的变量记录当前元素个数
浪费一个数组空间（最常用）
添加一个标志位标记最后一次操作是入队还是出队

下面采用“浪费一个空间”的方式实现，即队列满的条件是 (rear + 1) % capacity == front。

C++ 实现代码

#include <iostream>
using namespace std;
<p>class CircularQueue {
private:
int* arr;           // 存储数据的数组
int front;          // 队头索引
int rear;           // 队尾后一个位置
int capacity;       // 容量</p><p>public:
// 构造函数
CircularQueue(int size) {
capacity = size + 1;  // 多分配一个空间用于判断满
arr = new int[capacity];
front = 0;
rear = 0;
}</p><pre class='brush:php;toolbar:false;'>// 析构函数
~CircularQueue() {
    delete[] arr;
}

// 判断是否为空
bool isEmpty() {
    return front == rear;
}

// 判断是否为满
bool isFull() {
    return (rear + 1) % capacity == front;
}

// 入队
bool enqueue(int value) {
    if (isFull()) {
        cout << "队列已满，无法入队\n";
        return false;
    }
    arr[rear] = value;
    rear = (rear + 1) % capacity;
    return true;
}

// 出队
bool dequeue(int& value) {
    if (isEmpty()) {
        cout << "队列为空，无法出队\n";
        return false;
    }
    value = arr[front];
    front = (front + 1) % capacity;
    return true;
}

// 获取队头元素
bool getFront(int& value) {
    if (isEmpty()) {
        cout << "队列为空\n";
        return false;
    }
    value = arr[front];
    return true;
}

// 获取当前元素个数
int size() {
    return (rear - front + capacity) % capacity;
}

登录后复制

};

// 使用示例 int main() { CircularQueue q(5); // 创建容量为5的队列（实际数组大小6）

q.enqueue(10);
q.enqueue(20);
q.enqueue(30);

int val;
q.getFront(val);
cout << "队头元素: " << val << endl;

q.dequeue(val);
cout << "出队元素: " << val << endl;

cout << "当前大小: " << q.size() << endl;

return 0;

登录后复制

}

这个实现简洁高效，适合嵌入式、实时系统等对性能要求较高的场景。front 和 rear 的更新都通过取模完成循环，逻辑清晰。基本上就这些，不复杂但容易忽略边界判断。

以上就是c++++怎么实现一个环形队列_c++循环队列数据结构实现的详细内容，更多请关注php中文网其它相关文章！