数据结构与算法学习（day5）——队列算法

前言

本章我们学习队列。

本章的学习目标：

（1）能够使用队列算法解决简单的实际问题。

（2）能够用结构体来优化队列算法，并实际应用中使用。

题目

先看题目，题目就是应用场景，先明白是什么应用场景，更好的理解队列算法的原理。

（1）小明给了小亮一串加密过的数字{631758924}，解密规则是首先将第一个数字删除，紧接着将第二个数字放到这串数的末尾，再将第三个数删除，并将第四个数放到这串数的末尾，再将第五个数删除……直到剩下最后一个数，将最后一个数也删除。按照刚才删除的顺序，把这些删除的数连在一起就是小明的qq号。

（2）解密后的数字是615947283；

思路：

1. 定义一个数组来存储这一串数。
2. 两个整型变量head和tail。head用来记录队列的队首（即第一位），tail用来记录队列的队尾（即最后一位）的下一个位置。
3. 你可能会问：为什么tail不直接记录队尾，却要记录队尾的下一个位置呢？这是因为当队列中剩下一个元素时，队首和队尾重合会带来一些麻烦，所以还不如多申请一个空间，程序好写一些。
4. 我们这里规定队首和队尾重合时，队列为空。

#include 
int main()
{
	int q[102] = {0,6,3,1,7,5,8,9,2,4},head,tail;
	int i;
	//初始化队列
	head = 1;
	tail = 10;  //队列中已经有9个元素了，tail指向队尾的后一个位置
	while (head < tail)  //当队列不为空的时候执行循环
	{
		//打印队首并将队首移出队列，因为他是将第一个元素删除，最后删除的元素是解密的数字
		printf("%d ",q[head]);
		head++;

		//先将新队首的数添加到队尾
		q[tail] = q[head];
		tail++;  //队尾多申请一个位置

		//再将队首移出队,因为这个队首前面是移到队尾去了，所以这个队首就不存在了，新的队首是下一个元素
		head++;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

优化

上面的代码运行成功以后，我们总结一下队列的概念。

1. 队列是一种特殊的线性结构。
2. 它只允许在队列的首部（head）进行删除操作，这称为”出队“，而在队列的尾部（tail）进行插入操作，这就称为“入队”。
3. 当队列中没有元素时（即head == tail），称为空队列。
4. 在我们的日常生活中有很多情况都符合队列的特性。比如买票，每个排队买票的窗口就是一个队列，在这个队列中，新来的人总是站在队列的最后面，来的越早的人越靠前，也就越早能买到票，就是先来的人先服务，我们称之为“先进先出”（First In First Out,FIFO）原则。
5. 队列将是我们今后学习广度优先搜索以及队列优化的Bellman-Ford最短路径算法的核心数据结构。
6. 所以我们现在将队列的三个基本元素（一个数组，两个变量）封装为一个结构体类型进行优化，如下

struct queue
{
	int data[100];  //队列的主体，用来存储内容
	int head;  //队首
	int tail;  //队尾
};
1
2
3
4
5
6

#include 
struct queue
{
	int data[100];  //队列的主体，用来存储内容
	int head;  //队首
	int tail;  //队尾
};

int main()
{
	struct queue q;
	int i;

	//初始化队列
	q.head = 1;
	q.tail = 1;

	for (i = 1; i <= 9; i++)
	{
		//依次向队列插入9个数
		scanf("%d",&q.data[q.tail]);
		q.tail++;  //队尾比元素个数多一个
	}

	while (q.head < q.tail)  //当队列不为空的时候执行循环
	{
		//打印队首并将队首出队
		printf("%d ",q.data[q.head]);
		q.head++;

		//先将新队首的数添加到队尾
		q.data[q.tail] = q.data[q.head];
		q.tail++;

		//再将队首出队
		q.head++;
	}
	return 0;
}
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

上面的写法看起来虽然冗余了一些，但是可以加钱你对队列这个算法的理解。

我们生活中队列的例子也比比皆是，比如买票，又或者吃饭时候用来排队等候的叫号机，需要按照时间顺序，先到先得。