数据结构之队列

---

前言

今天学习数据结构中另一种特殊的线性表——队列。
我们平时在医院、银行等地方办理业务时，先排队在抽号机进行抽号，服务窗口会根据号码的顺序叫号，再为我们进行业务办理。
其中抽号机的工作原理就类似于是队列，先进入的数据先出（先抽号的人先服务），遵循了先来后到，确保了公平性。

一、队列

只允许在一端进行插入数据的操作，在另一端进行删除数据的操作的特殊线性表。
队列中的元素遵循先进先出（FIFO）的原则。

对队列的操作：
1.入队列：在插入数据的一端插入数据（队尾）；
2.出队列：在删除队列的一端删除数据（队头）。

二、队列应该如何实现

顺序表or链表

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些。因为如果使用数组的结构，出队列在数组上进行头删数据，效率会比较低。

扩展了解

实际中我们有时还会使用一种队列叫循环队列。如操作系统中的生产者消费者模型就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

三、队列的实现

1.队列的声明

typedef int QueueNodeType;
typedef struct QueueNode//队列节点
{
	QueueNodeType node;//存储数据的节点
	struct QueueNode* next;//指向下一个节点
}QueueNode;
typedef struct Queue//队列
{
	QueueNode* head;//指向头结点
	QueueNode* tail;//指向尾节点
	int size;//队列中的元素个数
}Queue;
1
2
3
4
5
6
7
8
9
10
11
12

2.接口（声明）

//队列的初始化
void QueueInit(Queue* ps);
//出队
void QueuePop(Queue* ps);
//入队
void QueuePush(Queue* ps, QueueNodeType x);
//销毁队列
void QueueDistory(Queue* ps);
//队头元素
QueueNodeType QueueFront(Queue* ps);
//判断队列为空(空就返回true，非空就返回false)
bool QueueEmpty(Queue* ps);
1
2
3
4
5
6
7
8
9
10
11
12

3.接口的实现

void QueueInit(Queue* ps)
{
	assert(ps);
	ps->head = ps->tail = NULL;
	ps->size = 0;
}
1
2
3
4
5
6

创建一个新的节点

QueueNode* QueueBuyNode(QueueNodeType x)
{
	QueueNode* t = (QueueNode*)malloc(sizeof(QueueNode));
	if (t == NULL)
	{
		perror("malloc fail");
	}
	t->node = x;
	t->next = NULL;
	return t;
}
1
2
3
4
5
6
7
8
9
10
11

判断队列为空

(空就返回true，非空就返回false)

bool QueueEmpty(Queue* ps)
{
	return ps -> tail == NULL &&ps -> head == NULL;
}
1
2
3
4

队头元素

QueueNodeType QueueFront(Queue* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));
	return ps->head->node;
}
1
2
3
4
5
6

入队

void QueuePush(Queue* ps, QueueNodeType x)
{
	QueueNode* newnode = QueueBuyNode(x);
	if (ps->tail == NULL)
	{
		ps->head = ps->tail = newnode;
	}
	else
	{
		ps->tail->next = newnode;
		ps->tail = newnode;
	}
	ps->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

出队

void QueuePop(Queue* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));
	if (ps->head->next == NULL)
	{
		free(ps->head);
		ps->head = ps->tail = NULL;
	}
	else
	{
		QueueNode* temp = ps->head;
		ps->head = ps->head->next;
		free(temp);
		temp = NULL;
	}
	ps->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

销毁队列

void QueueDistory(Queue* ps)
{
	assert(ps);
	QueueNode* cur = ps->head;
	while (cur)
	{
		QueueNode* del = cur;
		cur = cur->next;
		free(del);
	}
	ps->head = ps->tail = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

注意：

使用某些库函数时要记得包含它对应的头文件，我也给大家整理了本次所需要的头文件。

#include
#include
#include
#include
1
2
3
4

4.主函数（测试）

测试队列的相应功能，以下是我使用的主函数，大家也可以根据需要进行修改，测试其他的测试用例。

void test()
{
	Queue ps;
	QueueInit(&ps);//初始化队列
	QueuePush(&ps, 1);
	QueuePush(&ps, 2);
	QueuePush(&ps, 13);
	QueuePush(&ps, 14);
	//打印队列元素(遍历一边队列的元素，实质上就是出队列)
	while (!QueueEmpty(&ps))
	{
		printf("%d ", QueueFront(&ps));
		QueuePop(&ps);
	}
	QueueDistory(&ps);//销毁队列
}
int main()
{
	test();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

四、相关习题

到这篇文章，我们已经了解了很多栈和队列的相关知识，所以我在这里同大家分享一些与栈和队列有关的概念性的选择题，以便让大家对这些知识掌握更加熟练。
大家可以先自己尝试着做一下这些选择题，我也会将它们的答案公布在下一篇博客的评论区里。

总结

以上就是今天要讲的内容，本文介绍了数据结构中的队列。对队列的概念以及它的具体实现都进行了讲解。大家感兴趣的也可以根据作者所写思路自行实现。
本文作者目前也是正在学习数据结构的知识，如果文章中的内容有错误或者不严谨的部分，欢迎大家在评论区指出也欢迎大家在评论区提问、交流。
最后，如果本篇文章对你有所启发的话，也希望可以多多支持作者，谢谢大家！