队列

发表于 分类于
本文详细讲解了队列的结构和操作用C语言的基本实现

概念

队列是一种只允许在一端插入数据操作，另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO（First In First Out）的原则

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

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

队列的结构就像商店排队结账一样，先排队的先结账

如下图的入队顺序1，2，3，那么出队顺序依然是1，2，3
队列的结构示意图
因为考虑到头删和尾插，链队列书写起来更加容易，因此在本篇文章中我们按照链队列进行讲解

关于链表的基础知识可以看我之前的文章: 链表

接下来我们用代码来实现队列的结构和操作

代码实现

结构

链队列中的每个数据通过指针前后链接，用QueueNode作为存放数据的队列节点
队列结构体Queue用于存放头节点、尾节点、队列大小(节点数量)

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef int QDataType;//方便修改储存的数据类型
typedef struct QueueNode//队列节点
{
	QDataType val;//数据区
	QueueNode* next;//指针区
}QNode;

typedef struct Queue//队列
{
	QNode* phead;//头节点
	QNode* ptail;//尾节点
	int size;//队列大小
}Queue;

初始化

对队列的结构初始化

函数接口传入队列的指针
1.断言队列指针
2.头指针、尾指针置空
3.队列大小置0

1
2
3
4
5
6
7
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

销毁

对队列的空间占用销毁

函数接口传入队列的指针
1.断言队列指针
2.创建指针cur指向头节点
3.在while中，用指针next指向cur的下一节点，释放cur，令cur指向next。以此销毁整个队列链表
4.头节点、尾节点置空
5.队列大小置0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

尾插

从队尾插入数据

函数接口传入队列指针和新数据val
1.断言队列指针
2.利用malloc为新节点开辟空间，并判断是否开辟成功
3.新节点next指针置空，数据赋值为val
4.如果队列中没有节点，此时尾节点指针为NULL，那么将头节点和尾节点指针指向新节点
5.如果队列中有节点，那么将新节点尾插在链表中，最后将尾节点指针指向新节点
6.将队列大小加1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void QueuePush(Queue* pq, QDataType val)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->next = NULL;
	newnode->val = val;

	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}

	pq->size++;
}

头删

将队头节点删除

函数结构传入队列指针
1.断言队列指针
2.断言队列大小不为零
3.如果头节点的下一节点为空，那么直接释放头节点，将头尾节点置空
4.如果头节点下一节点不为空，那么用next指针保存头节点的下一节点，释放头节点，将next指向的节点设为头节点
5.将队列大小减1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->size != 0);

	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}

	pq->size--;
}

队列元素数量

获取队列元素的数量

函数接口传入队列指针，返回整型
1.断言队列指针
2.直接返回size

1
2
3
4
5
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

获取队列头

获取队列头数据

函数接口传入队列指针，返回储存的数据类型
1.断言队列指针
2.直接返回头节点的数据

1
2
3
4
5
6
QDataType QueueFront(Queue* pq)
{
	assert(pq);

	return pq->phead->val;
}

获取队列尾

获取队列尾数据

函数接口传入队列指针，返回储存的数据类型
1.断言队列指针
2.直接返回尾节点的数据

1
2
3
4
5
6
QDataType QueueBack(Queue* pq)
{
	assert(pq);

	return pq->ptail->val;
}

判空

判断队列是否为空

函数接口传入队列指针，返回bool类型
1.断言队列指针
2.直接返回比较结果

1
2
3
4
5
6
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->size == 0;
}

注意

所有对结构体和类的操作一定要通过封装的方法实现，即使像判空这种只有一行代码，因为没有函数内部加以限制，直接访问可能会错误修改数据或者访问的并不是想要的数据

如果文章内容有误，欢迎指出