目录

前言

1.为什么要使用循环队列

2.队列的顺序存储方式的实现

1.定义

2.队列初始化

3.销毁

4.清空队列

5.队列是否为空

6.队列长度

7.队头

8.入队

9.出队

10.遍历队列

11.完整代码

3.参考资料

---

前言

    这篇文章介绍循环队列的表示和用法。

1.为什么要使用循环队列

        在上一篇文章中，我们知道了顺序的循环表示和实现方法。但是我们会发现当我们在操作顺序链表的时候，我们频繁的操作顺序队列，而队列又不为空的时候，出队列的一些存储空间会变得不可用。

        如下图所示，当我rear=3,front=2的时候，顺序队列中至少有连个存储空间空间是不可以使用的，这无疑会浪费一些存储空间。那么有没有办法让我们在出队列之后，重复利用之前存储空间呢，答案是有的。

        图1.顺序队列的出队列和入队列操作示意图

        这里借鉴了网上老师的三种解决方案：

        1.使用计数器记录队列中的元素个数

        2.加标志位，删除的时候标志位置1，插入置0，当front = rear并且标志位为0，表示队列为空，当front=rear并且标志位为1的时候，表示队列经满。

        3.认为浪费一个存储空间，改成一个循环队列来实现。

        这里下面代码的表示和实现采用的第三种方案。

        关于循环队列的理解，感觉严蔚敏老师的讲解还是不错的，直接贴个图吧。

图2.严蔚敏老师数据结构与算法中关于循环队列的思路

2.队列的顺序存储方式的实现

1.定义

struct CircularQueue {
    int *base;
    int front;
    int rear;
    int maxSize; // 队列的最大容量
};

2.队列初始化

// 队列初始化
Status initQueue(CircularQueue &circularQueue, int maxSize) {
    circularQueue.base = new int[maxSize]; // 为循环队列分配内存
    if (!circularQueue.base) {
        return 0; // 内存分配失败
    }
    circularQueue.front = circularQueue.rear = 0; // 初始化队首和队尾指针
    circularQueue.maxSize = maxSize;
    return 1; // 初始化成功
}

3.销毁

// 销毁队列
void destroyQueue(CircularQueue &circularQueue) {
    if (circularQueue.base) {
        delete[] circularQueue.base; // 释放内存
        circularQueue.base = nullptr; // 将指针置为空
    }
}

4.清空队列

// 清空队列
void clearQueue(CircularQueue &circularQueue) {
    circularQueue.front = circularQueue.rear = 0; // 重置队首和队尾指针
}

5.队列是否为空

// 判断队列是否为空
bool isEmptyQueue(CircularQueue &circularQueue) {
    return circularQueue.front == circularQueue.rear; // 当队首和队尾指针相同时，队列为空
}

6.队列长度

// 获取队列长度
int queueLength(CircularQueue &circularQueue) {
    return (circularQueue.rear - circularQueue.front + circularQueue.maxSize) % circularQueue.maxSize;
}

7.队头

// 获取队首元素
Status getQueueFront(CircularQueue &circularQueue, int &frontElement) {
    if (isEmptyQueue(circularQueue)) {
        return 0; // 队列为空
    }
    frontElement = circularQueue.base[circularQueue.front];
    return 1; // 成功获取队首元素
}

8.入队

// 入队
bool enQueue(CircularQueue &circularQueue, int element) {
    // 检查队列是否已满
    if ((circularQueue.rear + 1) % circularQueue.maxSize == circularQueue.front) {
        return false; // 队列已满
    }
    // 入队操作
    circularQueue.base[circularQueue.rear] = element;
    circularQueue.rear = (circularQueue.rear + 1) % circularQueue.maxSize; // 移动队尾指针
    return true; // 入队成功
}

9.出队

// 出队
bool deQueue(CircularQueue &circularQueue, int &element) {
    // 检查队列是否为空
    if (isEmptyQueue(circularQueue)) {
        return false; // 队列为空，无法出队
    }
    // 出队操作
    element = circularQueue.base[circularQueue.front];
    circularQueue.front = (circularQueue.front + 1) % circularQueue.maxSize; // 移动队首指针
    return true; // 出队成功
}

10.遍历队列

// 遍历队列
void traverseQueue(CircularQueue &circularQueue) {
    // 遍历队列并打印元素
    int i = circularQueue.front;
    while (i != circularQueue.rear) {
        cout << circularQueue.base[i] << " ";
        i = (i + 1) % circularQueue.maxSize;
    }
    cout << endl;
}

11.完整代码

#include <iostream>
using namespace std;

typedef int Status;

struct CircularQueue {
    int *base;
    int front;
    int rear;
    int maxSize; // 队列的最大容量
};

// 队列初始化
Status initQueue(CircularQueue &circularQueue, int maxSize) {
    circularQueue.base = new int[maxSize]; // 为循环队列分配内存
    if (!circularQueue.base) {
        return 0; // 内存分配失败
    }
    circularQueue.front = circularQueue.rear = 0; // 初始化队首和队尾指针
    circularQueue.maxSize = maxSize;
    return 1; // 初始化成功
}

// 销毁队列
void destroyQueue(CircularQueue &circularQueue) {
    if (circularQueue.base) {
        delete[] circularQueue.base; // 释放内存
        circularQueue.base = nullptr; // 将指针置为空
    }
}

// 清空队列
void clearQueue(CircularQueue &circularQueue) {
    circularQueue.front = circularQueue.rear = 0; // 重置队首和队尾指针
}

// 判断队列是否为空
bool isEmptyQueue(CircularQueue &circularQueue) {
    return circularQueue.front == circularQueue.rear; // 当队首和队尾指针相同时，队列为空
}

// 获取队列长度
int queueLength(CircularQueue &circularQueue) {
    return (circularQueue.rear - circularQueue.front + circularQueue.maxSize) % circularQueue.maxSize;
}

// 获取队首元素
Status getQueueFront(CircularQueue &circularQueue, int &frontElement) {
    if (isEmptyQueue(circularQueue)) {
        return 0; // 队列为空
    }
    frontElement = circularQueue.base[circularQueue.front];
    return 1; // 成功获取队首元素
}

// 入队
bool enQueue(CircularQueue &circularQueue, int element) {
    // 检查队列是否已满
    if ((circularQueue.rear + 1) % circularQueue.maxSize == circularQueue.front) {
        return false; // 队列已满
    }
    // 入队操作
    circularQueue.base[circularQueue.rear] = element;
    circularQueue.rear = (circularQueue.rear + 1) % circularQueue.maxSize; // 移动队尾指针
    return true; // 入队成功
}

// 出队
bool deQueue(CircularQueue &circularQueue, int &element) {
    // 检查队列是否为空
    if (isEmptyQueue(circularQueue)) {
        return false; // 队列为空，无法出队
    }
    // 出队操作
    element = circularQueue.base[circularQueue.front];
    circularQueue.front = (circularQueue.front + 1) % circularQueue.maxSize; // 移动队首指针
    return true; // 出队成功
}

// 遍历队列
void traverseQueue(CircularQueue &circularQueue) {
    // 遍历队列并打印元素
    int i = circularQueue.front;
    while (i != circularQueue.rear) {
        cout << circularQueue.base[i] << " ";
        i = (i + 1) % circularQueue.maxSize;
    }
    cout << endl;
}

int main() {
    CircularQueue circularQueue;
    int maxSize = 10; // 队列的最大容量
    initQueue(circularQueue, maxSize); // 初始化循环队列

    // 测试入队
    for (int i = 1; i <= 5; ++i) {
        enQueue(circularQueue, i * 10);
    }

    // 输出队列元素
    cout << "队列元素：";
    traverseQueue(circularQueue);

    // 获取队首元素
    int frontElement;
    if (getQueueFront(circularQueue, frontElement)) {
        cout << "队首元素：" << frontElement << endl;
    }

    // 测试出队
    int element;
    for (int i = 0; i < 3; ++i) {
        if (deQueue(circularQueue, element)) {
            cout << "出队元素：" << element << endl;
        }
    }

    // 输出队列元素
    cout << "队列元素：";
    traverseQueue(circularQueue);

    // 判断队列是否为空
    if (isEmptyQueue(circularQueue)) {
        cout << "队列为空" << endl;
    } else {
        cout << "队列不为空" << endl;
    }

    // 获取队列长度
    cout << "队列长度：" << queueLength(circularQueue) << endl;

    // 清空队列
    clearQueue(circularQueue);

    // 判断清空后队列是否为空
    if (isEmptyQueue(circularQueue)) {
        cout << "清空队列后，队列为空" << endl;
    } else {
        cout << "清空队列后，队列不为空" << endl;
    }

    // 销毁队列
    destroyQueue(circularQueue);

    return 0;
}

3.参考资料

1.B站上看到的一个老师的讲解

2.数据结构C语言版（1997年清华大学出版社出版的图书）_百度百科