队列

队列是一种特殊的线性结构，它只允许在队列的首部（head）进行删除操作，我们称其为“出队”，而在队列的尾部（tail）进行插入操作，我们称之为“入队”。当队列中没有元素时（head==tail），我们称之为空队列。

生活中常见的符合队列特性的例子：

• 排队买火车票
• 打印机打印文件
• 商店排队买东西的顾客

解密QQ号.png

我们尝试着用python的列表来解决上面的解密QQ号的问题。这里我通过将加密后的一串数存储到列表中，并设置两个指针，head和tail,示意图如下所示：

列表指针示意图.png

通过题目中描述的规则编写代码如下所示：

#coding=utf-8
"""
Created on Mon Jul 30 11:31:24 2018

@author: Amica
"""
def Decoder(nums):
    head=0
    tail=len(nums)
    #设置一个新的列表用于存储移除的队首元素
    new_nums=[]
    while(head<tail-1):
        new_nums.append(nums[head])
        print("队首元素：",nums[head])
        print(new_nums)
        #将指针向前移动即删除队首的元素
        head+=1
        
        #将指针指向的元素添加到列表的尾部
        nums.append(nums[head])
        #将队尾的指针向后移动一位
        tail+=1
        #将队首的指针向后移动
        head+=1
    print("队首元素:",nums[head])
    new_nums.append(nums[head])
    return new_nums
if __name__=="__main__":
    nums=[6,3,1,7,5,8,9,2,4]
    print(Decoder(nums))

运行结果.png

其实在Python中，我们可以使用collections模块下的deque函数，它提供了队列所有的接口，collections.deque是双端队列，也就是说在队列的左右两边都是既可以进又可以出的。

双端队列的方法及其描述.png

下面我们通过collections提供的deque进行QQ号的解密：

# -*- coding: utf-8 -*-
"""
Created on Mon Jul 30 14:33:42 2018

@author: Amica
"""
from collections import deque
new_nums=[]
def Decoder(nums):
    #创建一个队列
    q=deque(nums)
    print(q)
    i=0
    while len(q)>1:
        #删除最左侧的元素并将删除的元素添加到列表new_nums中
        i+=1
        new_nums.append(q.popleft())
        print("经过第{}轮删除新列表中存在的元素{}".format(i,new_nums))
        #删除最左侧的元素并将删除的元素添加到队列的最右侧
        q.append(q.popleft())
    i+=1   
    new_nums.append(q.popleft())
    print("经过第{}轮删除新列表中存在的元素{}".format(i,new_nums))
    return new_nums
nums=[6,3,1,7,5,8,9,2,4]
print("小哈的QQ号为：",Decoder(nums))

运行结果.png