数据结构—循环队列（环形队列）

最新推荐文章于 2025-03-25 22:15:05 发布

The August

最新推荐文章于 2025-03-25 22:15:05 发布

阅读量4.9k

点赞数 19

分类专栏：数据结构文章标签：数据结构网络 c语言 c++ 面试题

本文链接：https://blog.csdn.net/AI_ELF/article/details/132022961

版权

循环队列的概念及结构

循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

在这里插入图片描述
注：循环队列的空间大小是固定的

环形队列可以使用数组实现（超出数组的范围回到起始位置），也可以使用循环链表实现（尾指针的next指向头节点）。选用数组实现循环队列更好，因为数组缓存利用率更高，没有扩容的代价。

环形队列实际开辟的空间大小要比所存数据的队列长度多开辟一个空间的大小。如果环形队列实际开辟的空间大小和所存储数据个数一样时，会导致环形队列所处空的状态和满的状态是一样的。这样便无法区分。

在这里插入图片描述

因此环形队列必须多留出一个空间，这个空间不能存放数据，这样才能很好的区别环形队列的状态是空还是满。

在这里插入图片描述

在这里插入图片描述
在环形队列中，队列为空时，队头队尾指向同一个位置。当队列不为空时，队头指向插入的第一个数据，队尾指向最后一个数据的下一个位置。当tail+1等于front时，说明环形队列已满。

循环队列的定义

循环队列选择用数组实现，循环队列需要用一个指针来指向存储队列数据的空间，用两个变量来记录队列中存储数据的起始（对头）和末尾（队尾）的数组位置，最后用一个变量记录队列的存储数据的最大容量。

typedef struct {
   
    int *a;
    int front;
    int tail;
    int k;
} MyCircularQueue;

循环队列的初始化

循环队列的初始化首先创建一个循环队列，其次对该结构体的成员进行初始化即可。

MyCircularQueue* myCircularQueueCreate(int k) {
   
    MyCircularQueue* cur=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    cur->a=<