【数据结构】数组循环队列的实现，数据结构，数组循环队列的实现方法

温馨提示：这篇文章已超过439天没有更新，请注意相关的内容是否还可用！

摘要：本文介绍了数据结构中的数组循环队列的实现。通过数组实现队列，并采用循环的方式提高空间利用率。该实现包括队列的初始化、入队、出队、判断队列是否为空或满等基本操作。通过循环队列，可以有效地解决传统队列在特定情况下空间浪费的问题，提高了数据处理的效率。

队列的数据元素又被称为队列元素，在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队，由于队列只允许在一端插入，在另一端删除，因此它也被称为先进先出（FIFO）线性表。

【数据结构】数组循环队列的实现，数据结构，数组循环队列的实现方法第1张

在程序中，队列常用于处理需要按特定顺序处理的任务，例如打印任务队列、线程任务调度等，队列也在许多算法中发挥着关键作用，如广度优先搜索（BFS）等。

队列的实现方式多种多样，包括基于数组的静态队列、基于链表的动态队列等，实际应用中，可以根据具体需求选择合适的队列实现方式。

队列的主要特点有：

1、先进先出：队列中的元素按照进入队列的先后顺序依次出队。

2、操作受限：队列只允许在队尾插入元素（入队），在队头删除元素（出队），队中其他位置的元素无法直接访问或修改。

3、有序性：由于遵循FIFO原则，队列中的元素始终保持一定的顺序。

我们来看一下队列的链式存储结构：

【数据结构】数组循环队列的实现，数据结构，数组循环队列的实现方法第2张

typedef int QDataType; // 队列数据类型的定义
// 链式结构的节点定义
typedef struct QListNode {
 struct QListNode* next;
 QDataType data;
} QNode;
// 队列的结构定义
typedef struct Queue {
 QNode* front; // 队头指针
 QNode* rear;  // 队尾指针
 int size;     // 队列当前大小
} Queue;

队列的顺序存储结构定义如下：

#define MAXQSIZE 100 // 队列可能达到的最大长度
typedef struct {
 QElemType* base;    // 存储空间的基地址
 int front;          // 头指针，指向队头元素的前一个位置
 int rear;           // 尾指针，指向队尾元素的位置
} SqQueue;

假设当前队列分配的空间最大为6，当队列处于某种状态时，无法继续插入新的队尾元素，否则会出现溢出的情况，这种现象被称为假溢出，为了解决这一问题，我们可以采用循环队列的方法。

循环队列的结构体定义如下：

typedef int QDataType; // 队列数据类型的定义
typedef struct {
 QDataType* a;       // 存储队列元素的数组
 int front;         // 队头指针
 int rear;          // 队尾指针，指向下一个插入位置
 int k;             // 循环队列的长度
} MyCircularQueue;

接下来是创建队列的函数：

MyCircularQueue* myCircularQueueCreate(int k) {
 MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); // 创建循环队列对象
 obj->a = (QDataType*)malloc((k + 1) * sizeof(QDataType)); // 开辟大小为k+1的数组空间，多开一个空间以便判断队列为空还是满，防止假溢出现象
 obj->k = k; // 设置循环队列的长度
 obj->front = obj->rear = 0; // 初始化队头和队尾指针为0
 return obj; // 返回创建的循环队列对象指针
}

以下是判断队空、队满以及入队、出队、获取队头和队尾元素等操作的函数实现：