?个人主页:? :✨✨✨初阶牛✨✨✨
?推荐专栏: ???C语言进阶
?个人信条: ?知行合一
?本篇简介:>:分享数据结构之C语言实现"队列".各个接口分别分析,讲解思路已经动图讲解.
金句分享:
✨书要好好读,喜欢的人也要好好争取!✨

前言

一、队列

1.1 队列的介绍:

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表.

队列具有先进先出FIFO(First In First Out)

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

用顺序表还是用链表实现队列比较好呢?

1. 对于链表的缺点,我们可以额外创建一个尾指针用于记录尾结点.这样效率就不是问题了,而顺序表的头插是硬伤.
2. 链表不需要扩容,顺序表需要动态扩容/

综上,咱还是选择链表=实现队列吧!

typedef int QDatatype;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDatatype data;
}QNode;

typedef struct Queue
{
	QNode* head;//记录队首
	QNode* tail;//记录队尾
	int size;//记录长度
}Queue;

图解:

1.2 "队列"的常见接口:

接口介绍:

//队列的初始化操作
void QueueInit(Queue* pq);
//队列的销毁
void QueueDestroy(Queue* pq);

//入队列
void QueuePush(Queue* pq, QDatatype x);
//出队列
void QueuePop(Queue* pq);
//队列的长度
int QueueSize(Queue* pq);
//队列是否为空
bool QueueEmpty(Queue* pq);
//取队头元素
QDatatype QueueFront(Queue* pq);
//取队尾元素
QDatatype QueueBack(Queue* pq);

二、接口的具体实现:

2.1 "队列"的"初始化"操作(QueueInit)

队列的结构是由两个结点指针,加一个记录长度的size变量组成.

队列的初始状态:
头指针=尾指针,长度为0.

代码:

//初始化"队列"操作
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
	int size = 0;
}

2.2 "入队"操作(QueuePush)

步骤:

1. 申请一个结点,将数据域赋值为x(目标值),指针域指向NULL;
2. 一般情况下,"入队"操作只影响尾指针.
3. 链接:将尾指针的指针域指向新节点.
4. 更新尾指针(令尾指针本身指向新节点).

特殊情况:

第一个元素入队时,头指针和尾指针都会收受到影响.需要将头指针和尾指针都指向新节点.

特殊情况:

代码:

//入队列
void QueuePush(Queue* pq, QDatatype x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode->data = x;
	newnode->next = NULL;
	if (pq->head == NULL)//第一个元素入队列时,会影响头指针
	{
		pq->head = pq->tail = newnode;//将头指针和尾指针都指向新节点
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;//更新队尾
	}
	pq->size++;
	return 0;
}

2.3 "队列"判空(QueueEmpty)

如果头指针和尾指针都指向NULL则表示空队列

代码:

//队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	//如果头指针和尾指针都指向NULL则表示空队列
	if (pq->head == pq->tail && pq->tail == NULL)
	{
		return true;
	}
	return false;
}

2.4 “出队”(QueuePop)

步骤:

1. 对于删除元素的"出队"操作,我们首先要进行"判空"操作.空队列不允许删除.
2. 创建一个结点指针(Delete ):用于记录待会要出队的原队首结点.
3. 将队首结点向后移动一步.(即将队首指针指向第二个元素).
4. 释放Delete 结点.
5. 长度(size)减少1;

特殊情况:
剩下最后一个待出队元素时:
会影响头指针,需要将头指针和尾指针都置空NULL;

这里就不画图了,相信聪明的友友们可以理解.

代码:

//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	QNode* Delete = pq->head;//记录原队首

	if (pq->head == pq->tail)//如果是最后一个元素出队列
	{
		pq->head = pq->tail = NULL;
	}
	else pq->head = pq->head->next;//更新队头指针
	free(Delete);//释放原队首
	pq->size--;
}

2.5 "队列"长度函数

这里采用了增加一个变量size用于记录队列的长度.所以直接返回size即可.
如果没有size就需要遍历.

//队列的长度
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

2.6 取"队头"和"队尾"元素

在创建队列时,我们已经分析了链式队列的结构,队首=和队尾元素我们可以直接通过队首指针(head)和队尾指针(tail)访问其数据域即可.

//取队头元素
QDatatype QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}

//取队尾元素
QDatatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail);
	return pq->tail->data;
}

2.7 "队列"的销毁:

与链表的销毁类似:
步骤:

1. 创建两个结点指针

(1):QNode* cur:从头指针开始,遍历整个队列
(2):QNode* next:用于记录下一个结点,方便cur被释放后,继续往下遍历.

2. 释放cur指针指向的结点.
3. 更新cur指针和next指针.
4. 将队首指针(head)和队尾指针(tail)指向NULL.
5. 将size置为0;

代码:

//队列的销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	QNode* next = cur;
	while (next)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

三、结语:

"栈"和"队列"都是很重要的一种数据结构,在计算机中有很多应用,后续会更新==“循环队列”==,和OJ题:用栈模拟队列,用队列模拟栈等.
如果文章对大家有帮助的话,牛牛会很开心的.???

如果文章中有错误,或者不理解的地方,欢迎小伙伴们私信提意见和提问哦！互相交流学习.
最后，小伙伴们的点赞就是给牛牛最大的支持，能不能给牛牛来一个一键三连呢？谢谢支持。

四、总代码:

4.1 主测试区(test.c)

#include"Queue.h"
int main()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	printf("队头数据%d
", QueueFront(&q));
	printf("队头数据%d
", QueueBack(&q));
	while (!QueueEmpty(&q))
	{
		printf("%d ", q.head->data);
		QueuePop(&q);
	}
	QueueDestroy(&q);;
	return 0;
}

4.2 接口实现区(Queue.c):

#include "Queue.h"

//队列的初始化操作
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
	int size = 0;
}



//入队列
void QueuePush(Queue* pq, QDatatype x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode->data = x;
	newnode->next = NULL;
	if (pq->head == NULL)//第一个元素入队列时,会影响头指针
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;//更新队尾
	}
	pq->size++;
	return 0;
}


//队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	if (pq->head == pq->tail && pq->tail == NULL)
	{
		return true;
	}
	return false;
}


//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	QNode* Delete = pq->head;//记录原队首

	if (pq->head == pq->tail)//如果是最后一个元素出队列
	{
		pq->head = pq->tail = NULL;
	}
	else pq->head = pq->head->next;//更新队头指针
	free(Delete);//释放原队首
	pq->size--;
}

//队列的长度
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

//取队头元素
QDatatype QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}

//取队尾元素
QDatatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail);
	return pq->tail->data;
}


//队列的销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	QNode* next = cur;
	while (next)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

4.3 接口声明区(Queue.h):

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int QDatatype;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDatatype data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

//队列的初始化操作
void QueueInit(Queue* pq);
//队列的销毁
void QueueDestroy(Queue* pq);

//入队列
void QueuePush(Queue* pq, QDatatype x);
//出队列
void QueuePop(Queue* pq);
//队列的长度
int QueueSize(Queue* pq);
//队列是否为空
bool QueueEmpty(Queue* pq);
//取队头元素
QDatatype QueueFront(Queue* pq);
//取队尾元素
QDatatype QueueBack(Queue* pq);