问题是这样的,有一串数字,需要进行一系列的解码,解密规则是:首先将第1个数删除,紧接着第2个数放到这串数的末尾,再将第3个数删除并将第4个数放到这串数的末尾,再将第5个数删除……,直到剩下最后一个数,将最后一个数也删除。按照删除的顺序,把这些删除的数连再一起,就是得到的密码。 我们使用 631758924 作为样例,得到的结果应该是 615947283 。
我们先来分析一下思路,这串数字就是一个队列,再排队,从头到尾,从前面开始,每次拿掉最前面的两个,第1个扔掉,第2个放到尾部。然后再考虑排在第3个和第4个的数,这满足 先进先出 的原理,所以是队列。
具体过程是这样的:刚开始这串数是“6 3 1 7 5 8 9 2 4”,首先删除6并将3放到这串数的末尾,这串数跟新为“1 7 5 8 9 2 4 3”,依次这样操作后,最后剩下一个3,在将3放在末尾后,删除。
这里我们使用了一个数组来保存着一串数字。解密的第一步是将第一个数删除,最简单的方法是将所有后面的数都往前面挪动一位,将前面的数覆盖。就好比我们排队买票,最前面的人买好离开了,后面所有的人就需要往全部向前面走一步,补上之前的空位,但是这样的做法很耗费时间。
在这里,我们引入两个整型变量 head 和 tail 。head用来记录队列的队首(即第一位),tail用来记录队列的队尾(即最后一位)的下一个位置(这样可以避免head和tail重复带来的麻烦,并规定队首和队尾重合时,队列为空)。
现在就上操作流程图和实例代码。
这里使用了高效率的System数组拷贝方法,使的在原密码的最后一个数字后面还有多的空间给前面的数字排队。
删除一个数时,可以使用另一个数组来保存,这里直接使用了打印在控制台上来输出显示。我们使用循环来打印密码的每一个数字,直到当head与tail相等时,代表队列为空,跳出循环。
现在我们来总结一下队列的概念,队列使一种特殊的线性结构,它只允许在队列的首部(head)进行删除操作,这称为“出队”,而在队列的尾部(tail)进行插入操作,这称为“入队”。当队列中没有元素时(即head == tail),称为空队列。队列就像上面提到的排队买票一样,在整个队列中,新来的人总是站在队列的最后面,来得越早的人越靠前,也能越早买到票,就是先来的人先服务,我们称为“先进先出”(First In First Out,FIFO)原则。队列将时我们以后要学习的广搜(BFS)以及 Bellman-Ford最短路径 算法的核心数据结构。
所以,我们现在可以将队列的三个基本元素(一个数组,两个变量)封装为一个类。如下。
到这里,我们使用一个封装好了的简单队列来实现这个问题。这里才用内部类的方式封装,方便主函数调用。