本文主要是介绍【坐在马桶上看算法】算法4：队列——解密QQ号--作者：ahalei，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
新学期开始了，小哈是小哼的新同桌（小哈是个小美女哦~），小哼向小哈询问QQ号，小哈当然不会直接告诉小哼啦，原因嘛你懂的。所以小哈给了小哼一串加密过的数字，同时小哈也告诉了小哼解密规则。规则是这样的：首先将第1个数删除，紧接着将第2个数放到这串数的末尾，再将第3个数删除并将第4个数再放到这串数的末尾，再将第5个数删除……直到剩下最后一个数，将最后一个数也删除。按照刚才删除的顺序，把这些删除的数连在一起就是小哈的QQ啦。现在你来帮帮小哼吧。小哈给小哼加密过的一串数是“6 3 1 75 8 9 2 4”。
在这里，我将引入两个整型变量head和tail。head用来记录队列的队首（即第一位），tail用来记录队列的队尾（即最后一位）的下一个位置。你可能会问为什么tail不直接记录队尾，却要记录队尾的下一个位置呢？这是因为当队列当中只剩下一个元素时，队首和队尾重合会带来一些麻烦。我们这里规定队首和队尾重合时，队列为空。
在队尾增加一个数（假设这个数是x）的操作是q[tail]=x;tail++;
整个解密过程，请看下面这个霸气外漏的图。
最后的输出就是6 1 5 94 7 2 8 3，代码实现如下。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #include <stdio.h> 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++; } getchar (); getchar (); return 0; } |
怎么样上面的代码运行成功没有？现在我们再来总结一下队列的概念。队列是一种特殊的线性结构，它只允许在队列的首部（head）进行删除操作称之为“出队”，而在队列的尾部（tail）进行插入操作称之为“入队”。当队列中没有元素时（即head==tail），称为空队列。在我们的日常生活中有很多情况都符合队列的特性。比如我们之前提到过的买票，每个排队买票的窗口就是一个队列。在这个队列当中，新来的人总是站在队列的最后面，来的越早的人越靠前也就越早能买到票，就是先来的人先服务，我们称为“先进先出”（First InFirst Out，FIFO）原则。
队列将是我们今后学习广度优先搜索以及队列优化的Bellman-Ford最短路算法的核心数据结构。所以现在将队列的三个基本元素（一个数组，两个变量）封装为一个结构体类型，如下。
| 1 2 3 4 5 6 | struct queue { int data[100]; //队列的主体，用来存储内容 int head; //队首 int tail; //队尾 }; |
上面我们定义了一个结构体类型，我们通常将其放在main函数的外面，请注意结构体的定义末尾有个;号。struct是结构体的关键字，queue是我们为这个结构体起的名字。这个结构体有三个成员分别是：整型数组data、整型head和整型tail。这样我们就可以把这三个部分放在一起作为一个整体来对待。你可以这么理解：我们定义了一个新的数据类型，这个新类型非常强大，用这个新类型定义出的每一个变量可以同时存储一个整型数组和两个整数。
有了新的结构体类型，如何定义结构体变量呢？很简单，这与我们之前定义变量的方式是一样，如下。
| 1 | struct queue q; |
请注意struct queue需要整体使用，不能直接写queue q;这样我们就定义了一个结构体变量q。这个结构体变量q就可以满足队列的所有操作了。那又该如何访问结构体变量的内部成员呢？可以使用.号，它叫做成员运算符或者点号运算符，如下：
| 1 2 3 | q.head=1; q.tail=1; scanf ( "%d" ,&q.data[q.tail]); |
好了，下面这段代码就是使用结构体来实现的队列操作。
| 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 | #include <stdio.h> 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++; } getchar (); getchar (); return 0; } |
这篇关于【坐在马桶上看算法】算法4：队列——解密QQ号--作者：ahalei的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
