开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构：队列和循环队列-C语言实现（有图详讲带注解，超详细，适合入门学习） -> 正文阅读

[数据结构与算法]数据结构：队列和循环队列-C语言实现（有图详讲带注解，超详细，适合入门学习）

之前的文章：

队列

一. 队列的概念

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

在这里插入图片描述

二. 普通的队列

2.1 前言

队列可以用数组和链表的结构实现，使用链表的结构实现更优一些，因为使用数组的结构，出队列在数组头上出数据，效率会比较低。我们这次的队列由链表实现，如下图所示，队列的主体部分为链表，有两个指针，head指针指向队头，tail指针指向队尾，出队在队头，入队在队尾。本次队列的实现共创建了三个文件，分别是Queue.h,Queue.c,和main.c文件。下面我们先把队列的结构体定义和各个函数接口实现，最后再把三个文件的代码分享出来。

在这里插入图片描述

2.2 定义队列

// 重命名数据类型名
typedef int QDataType;


// 定义链表
typedef struct QListNode
{
	// 存放数据
	QDataType data;

	// 指向下一个节点的指针
	struct QListNode* next;
}QListNode;


// 定义队列
typedef struct Queue
{
	// 队头指针
	QListNode* head;

	// 队尾指针
	QListNode* tail;
}Queue;

2.3 函数接口

2.3.1 队列初始化

在这里插入图片描述

// 初始化
void QueueInit(Queue* queue)
{
	// 判空
	assert(queue);  // 防止传进的是空指针

	queue->head = NULL;
	queue->tail = NULL;
}

assert是一个断言函数，程序运行的时候，当括号里面的结果为假时，就会停止运行并且报错。报错显示的信息包括断言语句括号的内容和断言的位置（在哪个文件，哪一行），还有一个错误框，如下图所示。断言能够快速地帮我们定位程序的错误，在实际开发中可以减少很多不必要的麻烦，所以建议大家在写代码的时候也尽量在需要的时候加上断言。

在这里插入图片描述

2.3.2 打印队列

// 打印
void QueuePrint(Queue* queue)
{
	assert(queue);

	// 定义一个指针指向队头
	QListNode* cur = queue->head;

	// 从队头遍历到队尾
	while (cur)
	{
		// 打印当前节点的值
		printf("%d --> ", cur->data);

		// 迭代
		cur = cur->next;
	}
	printf("\n");
}

2.3.3 判断队列为不为空

// 判空
// 为空返回true,不为空返回false
bool QueueEmpty(Queue* queue)
{
	assert(queue);
	return queue->head == NULL;
}

2.3.4 入队

在这里插入图片描述

// 入队
void QueuePush(Queue* queue, QDataType x)
{
	assert(queue);

	// 向内存申请一个节点
	QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));
	
	// 判空
	assert(newnode);  // 防止申请失败而导致崩溃

	// 给新节点初始化赋值
	newnode->data = x;
	newnode->next = NULL;

	// 判断是不是第一个节点入队
	if (queue->head == NULL)
	{
		// 是第一个节点，让head和tail都指向新节点
		queue->head = newnode;
		queue->tail = newnode;
	}
	else
	{
		// 队尾节点的next指向新节点
		queue->tail->next = newnode;

		// 让新节点变成队尾节点
		queue->tail = newnode;
	}
}

2.3.5 出队

在这里插入图片描述

// 出队
void QueuePop(Queue* queue)
{
	assert(queue);

	// 判空
	assert(!QueueEmpty(queue));  // 防止是空队列还出队，导致崩溃

	// 申请一个指针指向队头节点
	QListNode* tmp = queue->head;

	// 判断是不是最后一个节点
	if (queue->head->next == NULL)
	{
		// 是最后节让tail指向NULL
		queue->tail = NULL;
	}

	// 出队
	queue->head = queue->head->next;  // 如果是最后一个节点，head也会指向NULL

	// 释放出队节点
	free(tmp);
	tmp = NULL;
}

2.3.6 获取队头队尾元素

// 取队头元素
QDataType QueueFront(Queue* queue) 
{
	assert(queue);

	// 判空
	assert(!QueueEmpty(queue));

	//返回队头数据
	return queue->head->data;
}

// 取队尾元素
QDataType QueueBack(Queue* queue)
{
	assert(queue);

	// 判空
	assert(!QueueEmpty(queue));

	// 返回队尾数据
	return queue->tail->data;
}

2.3.7 获取队列大小

// 获取队列大小
int QueueSize(Queue* queue)
{
	assert(queue);

	// 定义一个变量统计大小
	int count = 0;

	// 定义一个指针遍历队列
	QListNode* cur = queue->head;
	while (cur)
	{
		count++;

		// 迭代
		cur = cur->next;
	}
	return count;
}

2.3.8 销毁队列

// 销毁
void QueueDestroy(Queue* queue)
{
	assert(queue);

	// 队列不为空，就一直出队
	while (!QueueEmpty(queue))
	{
		// 调用写好的出队接口
		QueuePop(queue);
	}
}

2.4 Queue.h文件

#pragma once  // 防止头文件被重复包含


// 包含头文件
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>


// 重命名数据类型名
typedef int QDataType;


// 定义链表
typedef struct QListNode
{
	// 存放数据
	QDataType data;

	// 指向下一个节点的指针
	struct QListNode* next;
}QListNode;

// 定义队列
typedef struct Queue
{
	// 队头指针
	QListNode* head;

	// 队尾指针
	QListNode* tail;
}Queue;


// 函数的声明

// 初始化
void QueueInit(Queue* queue);

// 打印
void QueuePrint(Queue* queue);

// 入队
void QueuePush(Queue* queue, QDataType x);

// 出队
void QueuePop(Queue* queue);

// 取队头元素
QDataType QueueFront(Queue* queue);

// 取队尾元素
QDataType QueueBack(Queue* queue);

// 获取队列大小
int QueueSize(Queue* queue);

// 判空
bool QueueEmpty(Queue* queue);

// 销毁
void QueueDestroy(Queue* queue);

2.5 Queue.c文件

#define _CRT_SECURE_NO_WARNINGS  // 这句是我的VS2022用scanf报错才加的，大家可以不用理
#include"Queue.h"

// 初始化
void QueueInit(Queue* queue)
{
	// 判空
	assert(queue);  // 防止传进的是空指针

	queue->head = NULL;
	queue->tail = NULL;
}

// 打印
void QueuePrint(Queue* queue)
{
	assert(queue);

	// 定义一个指针指向队头
	QListNode* cur = queue->head;

	// 从队头遍历到队尾
	while (cur)
	{
		// 打印当前节点的值
		printf("%d --> ", cur->data);

		// 迭代
		cur = cur->next;
	}
	printf("\n");
}

// 入队
void QueuePush(Queue* queue, QDataType x)
{
	assert(queue);

	// 向内存申请一个节点
	QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));
	
	// 判空
	assert(newnode);  // 防止申请失败而导致崩溃

	// 给新节点初始化赋值
	newnode->data = x;
	newnode->next = NULL;

	// 判断是不是第一个节点入队
	if (queue->head == NULL)
	{
		// 是第一个节点，让head和tail都指向新节点
		queue->head = newnode;
		queue->tail = newnode;
	}
	else
	{
		// 队尾节点的next指向新节点
		queue->tail->next = newnode;

		// 让新节点变成队尾节点
		queue->tail = newnode;
	}
}

// 出队
void QueuePop(Queue* queue)
{
	assert(queue);

	// 判空
	assert(!QueueEmpty(queue));  // 防止是空队列还出队，导致崩溃

	// 申请一个指针指向队头节点
	QListNode* tmp = queue->head;

	// 判断是不是最后一个节点
	if (queue->head->next == NULL)
	{
		// 是最后节让tail指向NULL
		queue->tail = NULL;
	}

	// 出队
	queue->head = queue->head->next;  // 如果是最后一个节点，head也会指向NULL

	// 释放出队节点
	free(tmp);
	tmp = NULL;
}

// 取队头元素
QDataType QueueFront(Queue* queue) 
{
	assert(queue);

	// 判空
	assert(!QueueEmpty(queue));

	//返回队头数据
	return queue->head->data;
}

// 取队尾元素
QDataType QueueBack(Queue* queue)
{
	assert(queue);

	// 判空
	assert(!QueueEmpty(queue));

	// 返回队尾数据
	return queue->tail->data;
}

// 获取队列大小
int QueueSize(Queue* queue)
{
	assert(queue);

	// 定义一个变量统计大小
	int count = 0;

	// 定义一个指针遍历队列
	QListNode* cur = queue->head;
	while (cur)
	{
		count++;

		// 迭代
		cur = cur->next;
	}
	return count;
}

// 判空
// 为空返回true,不为空返回false
bool QueueEmpty(Queue* queue)
{
	assert(queue);
	return queue->head == NULL;
}

// 销毁
void QueueDestroy(Queue* queue)
{
	assert(queue);

	// 队列不为空，就一直出队
	while (!QueueEmpty(queue))
	{
		// 调用写好的出队接口
		QueuePop(queue);
	}
}

2.6 main.c文件

#define _CRT_SECURE_NO_WARNINGS  // 这句是我的VS2022用scanf报错才加的，大家可以不用理
#include"Queue.h"

int main()
{
	Queue queue;

	QueueInit(&queue);
	QueuePush(&queue, 1);
	QueuePush(&queue, 2);
	QueuePush(&queue, 3);
	QueuePush(&queue, 4);
	//QueuePop(&queue);
	//QueuePop(&queue);
	//QueuePop(&queue);
	//QueuePop(&queue);
	//QueuePop(&queue);
	//QueuePrint(&queue);
	printf("%d\n", QueueSize(&queue));
	//printf("%d\n", QueueFront(&queue));
	//printf("%d\n", QueueBack(&queue));
	QueueDestroy(&queue);
	return 0;
}

三. 循环队列

3.1 前言

循环队列，一般情况下是定长的，有两个指针分别指向队头和队尾的下一个下标。如下图，左边是它的一个逻辑结构，实际上实现是用循环链表或者数组实现，我们这次是采用数组去实现。如下图的右边就是左边对应的状态，**初始状态下队头指针front和队尾指针rear都指向第一个位置。为了方便后面判满、判空，我们在申请数组空间的时候往往会多申请一个空间。**所以说下面的队列大小为7，实际申请的数组大小是8个元素空间。有数据的状态下，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置。本次队列的实现共创建了三个文件，分别是CircleQueue.h,CircleQueue.c,和main.c文件。下面我们先把队列的结构体定义和各个函数接口实现，最后再把三个文件的代码分享出来。

在这里插入图片描述

3.2 定义循环队列

// 重定义数据类型名
typedef int CQDataType;

typedef struct CircleQueue
{
	// 队列存放数据的数组
	CQDataType* arr;

	// 队列的大小
	int size;

	// 队头
	int front;

	// 队尾
	int rear;
}CircleQueue;

3.3 函数接口

3.3.1 初始化

// 初始化
void CircleQueueInit(CircleQueue* cq, int size)
{
	// 判空
	assert(cq);  // 防止cq是空指针

	// 向内存申请队列的空间
	cq->arr = (CQDataType*)malloc(sizeof(CQDataType) * (size + 1));  // 申请的时候申请size + 1个空间

	cq->size = size;
	cq->front = 0;
	cq->rear = 0;
}

3.3.2 打印

循环队列的空间是循环利用的，如下图所示，实际在队列的元素是从队头队尾的三个元素，也就是黑色字体的几个。下图的右边，黑色字体表示在队列的元素，红色字体是不在队列的，当新的数据入队时直接覆盖红色的元素就好了。下图的右边可以看成是实际情况下数组的状态，左边的是想象的状态，也就是说把红色字体的数据忽略。下面代码cur迭代的时候要模上数组大小size + 1，是为了预防想下图这种情况，rear在front的左边。后面代码要模上size + 1，也是这个原因。

在这里插入图片描述

// 打印
void CircleQueuePrint(CircleQueue* cq)
{
	assert(cq);
	
	// 从队头开始遍历
	int cur = cq->front;
	while (cur != cq->rear)
	{
		printf("%d ", cq->arr[cur]);
		cur = (cur + 1) % (cq->size + 1);  // 这里
	}
	printf("\n");
}

3.3.3 判空

在这里插入图片描述

// 判空
bool CircleQueueEmpty(CircleQueue* cq)
{
	assert(cq);
	return cq->front == cq->rear;
}

3.3.4 判满

在这里插入图片描述

// 判满
bool CircleQueueFull(CircleQueue* cq)
{
	assert(cq);
	return (cq->rear + 1) % (cq->size + 1) == cq->front;
}

3.3.4 入队

在这里插入图片描述

// 入队
void CircleQueuePush(CircleQueue* cq, CQDataType x)
{
	assert(cq);

	// 判满
	assert(!CircleQueueFull(cq));  // 防止队列满了还入队

	cq->arr[cq->rear] = x;
	cq->rear = (cq->rear + 1) % (cq->size + 1);
}

3.3.5 出队

在这里插入图片描述

// 出队
CQDataType CircleQueuePop(CircleQueue* cq)
{
	assert(cq);

	// 判空
	assert(!CircleQueueEmpty(cq));  // 防止队列空了，还继续出队

	// 记录出队元素
	CQDataType val = cq->arr[cq->front];

	// 出队
	cq->front = (cq->front + 1) % (cq->size + 1);

	// 返回出队元素
	return val;
}

3.3.6 取队头元素

// 取队头
CQDataType CircleQueueFront(CircleQueue* cq)
{
	assert(cq);
	assert(!CircleQueueEmpty(cq));

	return cq->arr[cq->front];
}

3.3.7 取队尾元素

下面的图片，index表示队尾元素下标，左右两边是不同的两种情况，他们对index的取值都能满足他们各自的情况，把他们综合一下得出的index取值，能满足所有情况。

在这里插入图片描述

// 取队尾
CQDataType CircleQueueRear(CircleQueue* cq)
{
	assert(cq);
	assert(!CircleQueueEmpty(cq));

    // 队尾元素的下标
	int index = (cq->rear -1 + (cq->size + 1)) % (cq->size + 1);
	return cq->arr[index];
}

3.3.8 销毁

// 销毁
void CircleQueueDestroy(CircleQueue* cq)
{
	assert(cq);

	// 释放数组空间
	free(cq->arr);

	// 指针置空，变量置零
	cq->arr = NULL;
	cq->front = 0;
	cq->rear = 0;
	cq->size = 0;
}

3.4 CircleQueue.h文件

#pragma once  // 防止头文件被重复包含


// 包含头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

// 重定义数据类型名
typedef int CQDataType;

typedef struct CircleQueue
{
	// 队列存放数据的数组
	CQDataType* arr;

	// 队列的大小
	int size;

	// 队头
	int front;

	// 队尾
	int rear;
}CircleQueue;


// 函数声明

// 初始化
void CircleQueueInit(CircleQueue* cq, int size);

// 打印
void CircleQueuePrint(CircleQueue* cq);

// 入队
void CircleQueuePush(CircleQueue* cq, CQDataType x);

// 出队
CQDataType CircleQueuePop(CircleQueue* cq);

// 取队头
CQDataType CircleQueueFront(CircleQueue* cq);

// 取队尾
CQDataType CircleQueueRear(CircleQueue* cq);

// 判空
bool CircleQueueEmpty(CircleQueue* cq);

// 判满
bool CircleQueueFull(CircleQueue* cq);

// 销毁
void CircleQueueDestroy(CircleQueue* cq);

3.5 CircleQueue.c文件

#define _CRT_SECURE_NO_WARNINGS  // 这句是我的VS2022用scanf报错才加的，大家可以不用理
#include"CircleQueue.h"

// 初始化
void CircleQueueInit(CircleQueue* cq, int size)
{
	// 判空
	assert(cq);  // 防止cq是空指针

	// 向内存申请队列的空间
	cq->arr = (CQDataType*)malloc(sizeof(CQDataType) * (size + 1));  // 申请的时候申请size + 1个空间

	cq->size = size;
	cq->front = 0;
	cq->rear = 0;
}

// 打印
void CircleQueuePrint(CircleQueue* cq)
{
	assert(cq);
	
	// 从队头开始遍历
	int cur = cq->front;
	while (cur != cq->rear)
	{
		printf("%d ", cq->arr[cur]);
		cur = (cur + 1) % (cq->size + 1);  // 这里
	}
	printf("\n");
}

// 入队
void CircleQueuePush(CircleQueue* cq, CQDataType x)
{
	assert(cq);

	// 判满
	assert(!CircleQueueFull(cq));  // 防止队列满了还入队

	cq->arr[cq->rear] = x;
	cq->rear = (cq->rear + 1) % (cq->size + 1);
}

// 出队
CQDataType CircleQueuePop(CircleQueue* cq)
{
	assert(cq);

	// 判空
	assert(!CircleQueueEmpty(cq));  // 防止队列空了，还继续出队

	// 记录出队元素
	CQDataType val = cq->arr[cq->front];

	// 出队
	cq->front = (cq->front + 1) % (cq->size + 1);

	// 返回出队元素
	return val;
}

// 取队头
CQDataType CircleQueueFront(CircleQueue* cq)
{
	assert(cq);
	assert(!CircleQueueEmpty(cq));

	return cq->arr[cq->front];
}

// 取队尾
CQDataType CircleQueueRear(CircleQueue* cq)
{
	assert(cq);
	assert(!CircleQueueEmpty(cq));  

	// 队尾元素的下标
	int index = (cq->rear -1 + (cq->size + 1)) % (cq->size + 1);
	return cq->arr[index];
}


// 判空
bool CircleQueueEmpty(CircleQueue* cq)
{
	assert(cq);
	return cq->front == cq->rear;
}

// 判满
bool CircleQueueFull(CircleQueue* cq)
{
	assert(cq);
	return (cq->rear + 1) % (cq->size + 1) == cq->front;
}

// 销毁
void CircleQueueDestroy(CircleQueue* cq)
{
	assert(cq);

	// 释放数组空间
	free(cq->arr);

	// 指针置空，变量置零
	cq->arr = NULL;
	cq->front = 0;
	cq->rear = 0;
	cq->size = 0;
}

3.6 main.c文件

#define _CRT_SECURE_NO_WARNINGS  // 这句是我的VS2022用scanf报错才加的，大家可以不用理
#include"CircleQueue.h"

int main()
{
	CircleQueue cq;
	CircleQueueInit(&cq, 4);
	CircleQueuePush(&cq, 1);
	CircleQueuePush(&cq, 2);
	CircleQueuePush(&cq, 3);
	CircleQueuePush(&cq, 4);
	CircleQueuePop(&cq);
	CircleQueuePush(&cq, 5);
	CircleQueuePop(&cq);
	CircleQueuePush(&cq, 6);
	CQDataType front = CircleQueueFront(&cq);
	CQDataType rear = CircleQueueRear(&cq);
	CQDataType pop = CircleQueuePop(&cq);
	printf("%d\n", front);
	printf("%d\n", rear);
	printf("%d\n", pop);

	//CircleQueuePop(&cq);
	//CircleQueuePop(&cq);
	//CircleQueuePop(&cq);
	//CircleQueuePush(&cq, 5);
	//CircleQueuePush(&cq, 6);
	//CircleQueuePush(&cq, 7);
	//CircleQueuePop(&cq);
	//CircleQueuePop(&cq);
	CircleQueuePrint(&cq);
	CircleQueueDestroy(&cq);
	return 0;
}

四. 结语

本文是博主学完这章内容后的个人总结，要是文章里有什么错误还望各位大神指正。或者对我的文章排版和其他方面有什么建议，也可以在评论区告诉我。这篇文章被归纳于《数据结构初级阶段-C语言实现》，这个专栏包括的知识点有顺序表、链表、栈、队列、树、排序算法。按照顺序更新，现在已经更新到队列，树和排序算法会在后面更新。如果我的文章对你的学习有帮助，或者觉得写得不错的话记得分享给你的朋友，非常感谢。