相关推荐recommended
【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列)
作者:mmseoamin日期:2024-04-01

=========================================================================

相关代码gitee自取:

C语言学习日记: 加油努力 (gitee.com)

 =========================================================================

接上期:

【数据结构初阶】五、线性表中的栈(C语言 -- 顺序表实现栈)_高高的胖子的博客-CSDN博客

 =========================================================================

                     

1 . 队列(Queue)

队列的概念和结构:

队列的概念

  • 队列是一种只允许在一端执行插入数据操作,在另一端进行删除数据操作的特殊线性表

                      

  • 入队列 -- 进行插入操作的一端称为队尾
    出队列 -- 进行删除操作的一端称为队头

                

  • 队列中的数据元素遵守
    先进先出(FIFO -- First In First Out)的原则 -- 先进入的元素会先出来

    所以可以应用在公平性排队(抽号机)、BFS(广度优先遍历)

                        

    队列的结构

    【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列),第1张

         

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

             

2 . 队列的实现

                

使用 顺序表(数组) 或 链表(链式结构) 都可以实现队列,

使用顺序表的话,入队列比较简单,但在出队列时需要删除和挪动数据,效率较低,

所以下面用链表(链式结构)实现队列  --  单向 + 无头 + 非循环 链表

入队 -- 单链表尾部插入(尾插)         ;      出队 -- 单链表头部删除(头删)

               

(详细解释在图片的注释中,代码分文件放下一标题处)

               

实现具体功能前的准备工作

  • 定义队列(链式结构)中数据域存储的数据类型

                               

  • 定义队列(链式结构)结点类型

    包含 队列指针域 和 队列数据域

                 

  • 定义队列类型

    包含 头结点指针 、尾结点指针 和 队列结点(元素)个数

    图示

    【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列),第2张

                

                

    ---------------------------------------------------------------------------------------------

                

    QueueInit函数 -- 将队列进行初始化

    • assert断言队列类型指针不为空

                                 

    • 将队头结点置为空

      将队尾结点置为空
      队列结点(元素)个数置为0

      图示

      【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列),第3张

                  

                  

      ---------------------------------------------------------------------------------------------

                  

      QueueDestroy函数 -- 将队列销毁

      • assert断言队列类型指针不为空

                                   

      • 创建一个在队列进行遍历的指针cur

        使用while循环进行遍历释放队列结点

                     

      • 结点都释放后,把队头队尾指针都置空

                       

      • 再把队列结点(元素)个数置为0
        图示

        【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列),第4张

                    

                    

        ---------------------------------------------------------------------------------------------

                    

        QueuePush函数 -- 用链表的尾插操作实现入队

        • assert断言队列类型指针不为空

                                     

        • 为队列结点开辟动态空间并检查空间开辟情况

                       

        • 结点开辟成功后

          将尾插值(x)赋给队列结点的数据域并将指针域置为空

                         

        • 空间开辟后进行尾插

          如果队列刚初始化队列为空,将刚开辟的结点newnode地址赋给头尾结点指针
          队列不为空,正常进行尾插操作

                      

        • 插入数据后队列结点(元素)个数++
          图示

          【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列),第5张

          【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列),第6张

                      

                      

          ---------------------------------------------------------------------------------------------

                      

          QueuePop函数 -- 用链表的头删操作实现出队

          • assert断言队列类型指针不为空和队列不为空

                                       

          • 出队(头删)分两种情况:
            队列中只剩一个结点 -- 头删后头指针移动,尾指针也要移动
            队列不止一个结点 -- 头删后只需移动队头结点

                         

          • “删除”后队列结点(元素)个数--
            图示

            【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列),第7张

            【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列),第8张

                        

                        

            ---------------------------------------------------------------------------------------------

                        

            QueueFront函数 -- 返回队头结点的数据域数据

            • assert断言队列类型指针不为空和队列不为空
                                         
            • 队列有数据,则直接返回队头结点数据域数据
              图示

              【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列),第9张

                          

                          

              ---------------------------------------------------------------------------------------------

                          

              QueueBack函数 -- 返回队尾结点的数据域数据

              • assert断言队列类型指针不为空和队列不为空

                                           

              • 队列有数据,则直接返回队尾结点数据域数据
                图示​​​​​​​

                【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列),第10张

                            

                            

                ---------------------------------------------------------------------------------------------

                            

                QueueEmpty函数 -- 判断队列是否为空

                • assert断言队列类型指针不为空

                                             

                • 直接判断队头结点指向的下个结点是否为空,直接返回判断结果
                  图示

                  【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列),第11张

                              

                              

                  ---------------------------------------------------------------------------------------------

                              

                  QueueSize函数 -- 判断队列结点(元素)个数

                  • assert断言队列类型指针不为空

                                               

                  • 直接返回size队列结点(元素)个数
                    图示

                    【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列),第12张

                                

                                

                    ---------------------------------------------------------------------------------------------

                                

                    总体测试:

                    【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列),第13张

         

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

             

3 . 对应代码

Queue.h -- 队列头文件

#pragma once
//包含之后需要的头文件:
#include 
#include 
#include 
#include 
//以链表(链式结构)实现队列:
//双向+循环 的链表可以解决找尾结点的问题,
//定义一个尾指针也可以解决该问题,
//哨兵位 可以解决二级指针的问题,
//且尾插时可以少一层判断,但还有方法可以解决
//定义队列(链式结构)中数据域存储的数据类型:
typedef int QDataType;
//定义队列(链式结构)结点类型:
typedef struct QueueNode
{
	//队列指针域:
	struct QueueNode* next;
	//队列数据域:
	QDataType data;
}QNode; //将类型重命名为Qnode
//定义队列类型:
typedef struct Queue
{
	//因为用链表尾插实现入队,
	//用链表头删实现出队,
	//那么就需要头结点和尾结点的指针,
	//所以可以直接将这两个指针封装为一个类型,
	//队列类型:
	//头结点指针:
	QNode* head;
	//尾结点指针:
	QNode* tail;
	//记录队列结点(元素)个数:
	int size; 
	//这样之后在出队和入队操作时,
	//就不需要用到二级指针,
	//直接接收这个结构体指针,
	//通过结构体指针运用结构体里的头尾结点指针,
	//再用头尾结点指针定义头尾结点
	//来实现 二级指针、带哨兵位头结点 和 返回值 的作用
	//所以现在已知的通过指针定义结点的方法就有4种:
	//		1. 结构体包含结点指针
	//		2. 二级指针调用结点指针
	//		3. 哨兵位头结点指针域next指向结点地址
	//		4. 返回值返回改变的结点指针
}Que; //重命名为Que
//队列初始化函数 -- 将队列进行初始化
//接收队列类型指针(包含链表头尾结点) 
void QueueInit(Que* pq);
//队列销毁函数 -- 将队列销毁
//接收队列类型指针(包含链表头尾结点) 
void QueueDestroy(Que* pq);
//队列入队函数 -- 用链表的尾插操作实现入队
//接收队列类型指针(包含链表头尾结点) 、尾插值
void QueuePush(Que* pq, QDataType x);
//队列出队函数 -- 用链表的头删操作实现出队
//接收队列类型指针(包含链表头尾结点) 
void QueuePop(Que* pq);
//队头函数 -- 返回队头结点的数据域数据
//接收队列类型指针(包含链表头尾结点) 
QDataType QueueFront(Que* pq);
//队尾函数 -- 返回队尾结点的数据域数据
//接收队列类型指针(包含链表头尾结点) 
QDataType QueueBack(Que* pq);
//判空函数 -- 判断队列是否为空
//接收队列类型指针(包含链表头尾结点) 
bool QueueEmpty(Que* pq);
//队列大小函数 -- 判断队列结点(元素)个数
//接收队列类型指针(包含链表头尾结点) 
int QueueSize(Que* pq);

            

            

---------------------------------------------------------------------------------------------

                

Queue.c -- 队列函数实现文件

#define _CRT_SECURE_NO_WARNINGS 1
//包含队列头文件:
#include "Queue.h"
//队列初始化函数 -- 将队列进行初始化
//接收队列类型指针(包含链表头尾结点) 
void QueueInit(Que* pq)
{
	//assert断言队列类型指针不为空:
	assert(pq != NULL);
	//将队头结点置为空:
	pq->head = NULL;
	//将队尾结点置为空:
	pq->tail = NULL;
	//队列结点(元素)个数置为0:
	pq->size = 0;
}
//队列销毁函数 -- 将队列销毁
//接收队列类型指针(包含链表头尾结点) 
void QueueDestroy(Que* pq)
{
	//assert断言队列类型指针不为空:
	assert(pq != NULL);
	//释放队列跟单链表的释放一样
	//先创建一个在队列进行遍历的指针:
	QNode* cur = pq->head; //从队头结点开始
	//使用while循环进行遍历释放队列结点:
	while (cur != NULL)	
	{
		//先保存下个结点:
		QNode* next = cur->next;
		//再释放当前结点:
		free(cur);
		//再指向下个结点:
		cur = next;
	}
	//结点都释放后,把队头队尾指针都置空:
	pq->head = NULL;
	pq->tail = NULL;
	//再把队列结点(元素)个数置为0:
	pq->size = 0;
}
//队列入队函数 -- 用链表的尾插操作实现入队
//接收队列类型指针(包含链表头尾结点) 、尾插值
void QueuePush(Que* pq, QDataType x)
{
	//assert断言队列类型指针不为空:
	assert(pq != NULL);
	//入队放入元素需要空间,
	//所以要先为队列结点开辟动态空间:
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	//检查是否开辟成功:
	if (newnode == NULL)
	{
		//开辟失败则打印错误信息:
		perror("malloc fail");
		//终止程序:
		exit(-1);
	}
	//队列结点完成后将尾插值(x)
	//赋给队列结点数据域:
	newnode->data = x;
	//指针域指向空:
	newnode->next = NULL;
	//空间开辟后进行尾插:
	if (pq->tail == NULL)
		//如果队列刚初始化,队列为空,
		//头结点指针和尾结点指针都为空:
	{
		//那么将刚开辟的结点newnode地址
		//赋给头结点指针和尾结点指针
		pq->head = newnode;
		pq->tail = newnode;
	}
	else
		//队列不为空,进行尾插:
	{
		//将目前队尾结点指针域next指向尾插结点:
		pq->tail->next = newnode;
		//然后再指向尾插结点,成为新队尾结点:
		pq->tail = newnode;
	}
	//插入数据后队列结点(元素)个数++:
	pq->size++;
}
//队列出队函数 -- 用链表的头删操作实现出队
//接收队列类型指针(包含链表头尾结点) 
void QueuePop(Que* pq)
{
	//assert断言队列类型指针不为空:
	assert(pq != NULL);
	//assert断言队列不为空,没数据不能删除:  
	assert(QueueEmpty(pq) != true); //不为空就继续程序
	//如果队列中只剩一个结点:
	if (pq->head->next == NULL)
		//队头指针指向空,说明只剩一个结点,
		//只剩一个结点说明队头队尾指针都指向这一个结点,
		//所以这时头删后头指针移动,尾指针也要移动
	{
		//先释放("删除")队列目前头结点:
		free(pq->head);
		//删除后将队头队尾指针都置为空:
		pq->head = NULL;
		pq->tail = NULL;
	}
	else
		//队列不止一个结点,则头删后只需移动队头结点:
	{
		//用链表的头删操作实现出队,
		//先保存第二个结点地址:
		QNode* next = pq->head->next;
		//释放("删除")队列目前头结点:
		free(pq->head);
		//再将队头结点指针指向原本第二个结点next,
		//让其成为新的队头结点:
		pq->head = next;
	}
	//“删除”后队列结点(元素)个数--:
	pq->size--; 
}
//队头函数 -- 返回队头结点的数据域数据
//接收队列类型指针(包含链表头尾结点) 
QDataType QueueFront(Que* pq)
{
	//assert断言队列类型指针不为空:
	assert(pq != NULL);
	//assert断言队列不为空,没数据不能查找:  
	assert(QueueEmpty(pq) != true); //不为空就继续程序
	//队列有数据,则直接返回队头结点数据域数据:
	return pq->head->data;
}
//队尾函数 -- 返回队尾结点的数据域数据
//接收队列类型指针(包含链表头尾结点) 
QDataType QueueBack(Que* pq)
{
	//assert断言队列类型指针不为空:
	assert(pq != NULL);
	//assert断言队列不为空,没数据不能查找:  
	assert(QueueEmpty(pq) != true); //不为空就继续程序
	//队列有数据,则直接返回队尾结点数据域数据:
	return pq->tail->data;
}
//判空函数 -- 判断队列是否为空
//接收队列类型指针(包含链表头尾结点) 
bool QueueEmpty(Que* pq)
{
	//assert断言队列类型指针不为空:
	assert(pq != NULL);
	//直接判断队头结点指向的下个结点是否为空:
	return pq->head == NULL; 
	//是则返回true -- 队列为空
	//是则返回false -- 队列不为空
}
//队列大小函数 -- 判断队列结点(元素)个数
//接收队列类型指针(包含链表头尾结点) 
int QueueSize(Que* pq)
{
	//assert断言队列类型指针不为空:
	assert(pq != NULL);
	//直接返回size队列结点(元素)个数:
	return pq->size;
}

            

            

---------------------------------------------------------------------------------------------

                

Test.c -- 队列测试文件

#define _CRT_SECURE_NO_WARNINGS 1
//包含队列头文件:
#include "Queue.h"
//队列测试函数:
void TestQueue()
{
	//创建队列类型:
	Que q;
	//对队列类型进行初始化:
	QueueInit(&q);
	//进行入队操作:
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);
	//当前队尾值:
	printf("当前队尾值:%d\n", QueueBack(&q));
	//当前队列元素个数:
	printf("当前队列元素个数:%d\n", QueueSize(&q));
	//换行:
	printf("\n");
	//使用while循环遍历进行出队:
	//(类似抽号机,当前号抽完就到下个号)
	while (!QueueEmpty(&q))
		//队列不为空就继续出队:
	{
		//打印出队值:
		printf("当前出队值为:%d\n", QueueFront(&q));
		//进行出队:
		QueuePop(&q); //出队后打印下个出队值
	}
	//换行:
	printf("\n");
	//当前队列元素个数:
	printf("当前队列元素个数:%d", QueueSize(&q));
	//销毁队列:
	QueueDestroy(&q);
}
//主函数:
int main()
{
	//调用队列测试函数:
	TestQueue();
	return 0;
}