队列（Queue）C语言实现 详解

---

前言

你们在用电脑时有没有经历，机器有时会处于疑似死机的状态，鼠标点什么似乎都没用，双击任何快捷方式都不动弹。就当你失去耐心，打算rest时。突然他像酒醒了一样，把你刚才点击的所有操作全部按顺序执行一遍。这其实是因为操作系统中的多个程序因需要通过一个通道输出，而按先后次序排队等待造成的。这里应用了一种数据结构来实现刚才提到的先进先出的排队功能，这就是队列。本文就对算法中的队列进行简单的总结，仅供参考使用。错漏之处，请不吝指正。

---

一、队列的概念及结构

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

二、实现队列

1.实现队列建议用什么结构？

数组可以在一头增添数据很方便，但是在另一头删除数据整个数组中的元素都要挪动，效率很低。所以建议用单链表来实现队列。

2.接口的设计

代码如下（示例）：

typedef int QDataType;

typedef struct QueueNode
{
	QDataType _data;		//用来存储数据
	struct QueueNode* _next;//用来指向下一个结构体
}QueueNode;

typedef struct Queue
{
	QueueNode* _head; //存放整个队列的队头
	QueueNode* _tail; //存放整个队列的队尾
}Queue;

//初始化
void QueueInit(Queue* pq);

//销毁
void QueueDestory(Queue* pq);

//入队
void QueuePush(Queue* pq, QDataType x);

//出队
void QueuePop(Queue* pq);

//访问队首的元素
QDataType QueueFront(Queue* pq);

//访问对尾的元素
QDataType QueueBack(Queue* pq);

//返回1是空，返回0是非空
int QueueEmpty(Queue* pq);

//获取数据的个数
int QueueSize(Queue* pq);

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
26
27
28
29
30
31
32
33
34
35
36
37
38

3.接口的实现

代码如下（示例）：

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);					 //判断指针的有效性
	pq->_head = pq->_tail = NULL;//队头和队尾指向空指针
}
//销毁
void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->_head;
	while (cur)
	{
		QueueNode* next = cur->_next;
		free(cur);
		cur = next;
	}
	pq->_head = pq->_tail = NULL;
}
//入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));//为新节点申请内存空间
	if (newnode == NULL)//判断内存空间是否申请成功
	{
		printf("内存不足!\n");
		exit(-1);
	}
	newnode->_data = x;   //新节点储存数据
	newnode->_next = NULL;//新节点的下一个指向NULL，即新节点作为队尾
	if (pq->_head == NULL)//将新节点入队
	{
		pq->_head = pq->_tail = newnode;
	}
	else
	{
		pq->_tail->_next = newnode;
		pq->_tail = newnode;
	}
}
//出队
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->_head);
	QueueNode* next = pq->_head->_next;
	free(pq->_head);
	pq->_head = next;
	if (pq->_head == NULL)
	{
		pq->_tail = NULL;
	}
}
//访问队首的元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->_head);
	return pq->_head->_data;
}
//访问队尾的元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->_head);
	return pq->_head->_data;
}
//返回1是空，返回0是非空
int QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->_head == NULL ? 1 : 0;
}
获取数据的个数
int QueueSize(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->_head;
	int size = 0;
	while (cur)
	{
		++size;
		cur = cur->_next;
	}
	return size;
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

---

三、测试数据

根据不同的需求调用不用的函数：
代码如下（示例）：

void TestQueue()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	QueueDestory(&q);
}
int main()
{
	TestQueue();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

将1，2，3，4以此入队然后再打印，结果如下：

总结

队列的作用：

• 先进先出场景，比如要保持序列公平，排队抽好机。
• 广度优先遍历。
  以上就是今天要讲的内容，本文仅仅简单介绍了队列的实现。使用队列存储数据，讲究 “先进先出”，即最先进队列的数据，也最先出队列。使用栈结构存储数据，讲究“先进后出”，即最先进栈的数据，最后出栈；不足之处我会多多改进。想了解栈的可以看这篇文章（栈（Stack）C语言实现 详解）。