数据结构入门 — 队列

本文属于数据结构专栏文章，适合数据结构入门者学习，涵盖数据结构基础的知识和内容体系，文章在介绍数据结构时会配合上动图演示，方便初学者在学习数据结构时理解和学习，了解数据结构系列专栏点击下方链接。

---

• 博客主页：Duck Bro 博客主页
• 系列专栏：数据结构专栏
• 关注博主，后期持续更新系列文章
• 如果有错误感谢请大家批评指出，及时修改
• 感谢大家点赞👍收藏⭐评论✍

---

数据结构入门 — 队列

本文关键字：队列、队列概念及结构、队列实现

---

一、队列的概念及结构

1. 队列的概念

队列是一种数据结构，它遵循先进先出（First-in, First-out）原则。队列可以看作是一条排队等待服务的线程，其中最先加入队列的元素最先被处理，而最后加入队列的元素最后被处理。

队列有两个端点：队头和队尾。元素从队尾进入队列，从队头出队。队列的基本操作包括入队（enqueue）和出队（dequeue），以及获取队头和队尾元素的操作。队列在计算机科学中有广泛的应用，例如任务调度、缓存管理、路由算法等。

2. 队列的结构

队列的结构组成通常包括以下几个要素：

---

二、队列的实现

1. 队列结构组成

队列结构由链表组成，使用头尾两个指针，用size记录队列里元素个数

typedef int QueDatatype;
typedef struct QueList
{
	struct QueList* next;
	QueDatatype data;
 }QNode;

typedef struct QueHeadTail
{
	QNode* head;
	QNode* tail;
	int size;
}QHT;
1
2
3
4
5
6
7
8
9
10
11
12
13

2. 初始化队列

初始化将头尾两个指针置空，将size置为0

void QueInit(QHT* pc)
{
	assert(pc);
	pc->head = pc->tail = NULL;
	pc->size = 0;
}
1
2
3
4
5
6

3. 队尾入队列

入队，用malloc开辟一个新的空间，分为两种情况当尾指针为空的时候和尾指针不为空时，详细见代码

void QuePush(QHT* pc, QueDatatype x)
{
	assert(pc);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pc->tail == NULL)
	{
		pc->head = pc->tail = newnode;
	}
	else
	{
		pc->tail->next = newnode;
		pc->tail = newnode;
	}
	pc->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

4. 队头出队列

当头指针的下一个为空时要释放头指针指向的空间，并将头尾指针置为0

void QuePop(QHT* pc)
{
	assert(pc);
	assert(!QueEmpty(pc));
	if (pc->head->next == NULL)
	{
		free(pc->head);
		pc->head = pc->tail = NULL;

	}
	else
	{
		QNode* next = pc->head->next;
		free(pc->head);
		pc->head = next;
	}
	pc->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5. 获取队列头部元素

返回头指针所指向的元素

QueDatatype QueFront(QHT* pc)
{
	assert(pc);

	return pc->head->data;
}
1
2
3
4
5
6

6. 获取队列队尾元素

返回尾指针所指向的元素

QueDatatype QueLast(QHT* pc)
{
	assert(pc);
	return pc->tail->data;
}

1
2
3
4
5
6

7. 获取队列中有效元素个数

返回size的个数，即有效元素个数

int QueSize(QHT* pc)
{
	assert(pc);
	return pc->size;

}
1
2
3
4
5
6

8. 检测队列是否为空

当头指针为空时，队列则为空

bool QueEmpty(QHT* pc)
{
	assert(pc);
	return pc->head == NULL;
}
1
2
3
4
5

9. 销毁队列

先保存下一个数据地址，并释放当前位置的内存空间，并将头尾指针置为空，size置为0

void QueDestroy(QHT* pc)
{
	assert(pc);
	QNode* cur = pc->head;
	while (cur)
	{
		QNode* delnext = cur->next;
		free(cur);
		cur = delnext;
	}
	pc->head = pc->tail = NULL;
	pc->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---