1.队列的概念及结构

2.队列的实现

3.队列的相关实现函数与源代码

3.1初始化队列

3.2 队尾入队列

3.3 队头出队列

3.4获取队列头部元素

3.5 获取队列队尾元素

3.6 获取队列中有效元素个数

3.7检测队列是否为空

3.8销毁队列

4.环形队列

4.1环形队列概念

4.2实现环形队列

4.2.1.实现环形队列的前期准备：相关结构体

4.2.2.创建环形队列，设置队列长度为 k

4.2.3. 实现循环队列判空函数和判满函数

4.2.5.插入和删除元素

4.2.6.从队首和队尾获取元素

4.3环形队列完整代码

在最后

1.队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾。

出队列：进行删除操作的一端称为队头。

2.队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

3.队列的相关实现函数与源代码

对其使用的结构体的定义：

typedef  int QDataType;//用单链表实现队列// 链式结构：表示队列 
typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;// 队列的结构 
typedef struct Queue
{QNode* front;QNode* rear;
}Queue;

通过队头队尾front、rear这两个指针来访问队列，执行队列的基本操作。

3.1初始化队列

// 初始化队列
void QueueInit(Queue* q)
{assert(q);q->front =q->rear= NULL;
}

3.2 队尾入队列

分两种情况队列为空和队列不为空。

在创建新节点的时候直接把新节点的next初始化为空，后续链接就不用重新把尾结点置为空

QNode* AddNode(QDataType data)
{QNode* p = (QNode*)malloc(sizeof(QNode));if (p == NULL){perror("malloc error\n");exit(-1);}p->data = data;p->next = NULL;//直接把新节点的next初始化为空，后续链接就不用重新把尾结点置为空return p;
}
//从队尾添加数据
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{assert(q);//情况1.如果是空队列if (q->front == NULL){q->front = q->rear = AddNode(data);}//情况2.队列不为空else{QNode* tail = AddNode(data);q->rear->next = tail;q->rear = tail;}
}

3.3 队头出队列

删除掉队头的数据

请注意如果队列中只有一个元素时，需要进行判断。

释放这个节点之后把指向队列的头尾指针都置为空，否则只是单纯的q->front=q->front->next,q->rear不变的话，就会造成q->rear指向一个已经释放的节点的情况，会造成野指针的问题。

// 队头出队列 
void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));//如果删除的是最后一个if (q->front->next == NULL){free(q->front);q->front = q->rear = NULL;}QNode* head = q->front;q->front = q->front->next;free(head);head = NULL;}

3.4获取队列头部元素

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->front->data;
}

3.5 获取队列队尾元素

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->rear->data;
}

3.6 获取队列中有效元素个数

遍历整个队列计算长度。

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{assert(q);assert(!QueueEmpty(q));int i = 0;QNode* head = q->front;while (head){i++;head = head->next;}return i;
}

也可以直接在一开始定义的时候直接把结构体改为：

// 队列的结构 
typedef struct Queue
{QNode* front;QNode* rear;int size;
}Queue;

在之后的入队列出队列的时候都进行相应的++或者--

3.7检测队列是否为空

如果为空返回非零结果，如果非空返回0

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{assert(q);return q->front == NULL;
}

3.8销毁队列

记得销毁队列时，把队列的节点全部释放之后，记得在最后把指向队列的前后指针置为空。

// 销毁队列 
void QueueDestroy(Queue* q)
{assert(q);QNode* head = q->front;QNode* next = NULL;while (head){next = head->next;free(head);head=next;}q->front = q->rear = NULL;//销毁队列之后记得把头尾指针置为空
}

4.环形队列

4.1环形队列概念

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

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

环形队列可以使用数组实现，也可以使用循环链表实现。如果使用数组实现，注意数组下标访问越界问题。

以下用数组实现环形队列：

4.2实现环形队列

以力扣622.设计循环队列为例：

622. 设计循环队列 - 力扣（LeetCode）https://leetcode.cn/problems/design-circular-queue/在这个题目中我们一共要实现有关环形队列的七个函数：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。