队列是项的有序结合，其中添加新项的一端称为队尾，移除项的一端称为队首。
当一个元素从队尾进入队列时，一直向队首移动，直到它成为下一个需要移除的元素为止这种排序称为 FIFO(First In First Out)，先进先出。
如下图所示，表示一个队列：

队列

队列抽象数据类型

如上所述，队列被构造为在队尾添加项的有序集合，并且从队首移除，队列保持 FIFO 排序属性。
队列操作如下：

操作	描述	返回值
Queue()	创建一个空的新队列，不需要参数	并返回一个空队列
enqueue(item)	将新项添加到队尾，需要 item 作为参数	不返回任何内容
dequeue()	从队首移除项，不需要参数	队列被修改，返回队首项
isEmpty()	查看队列是否为空，不需要参数	返回布尔值
size()	返回队列中的项数，不需要参数	返回一个整数

python实现队列

假定队尾在列表中的位置为 0，这允许我们使用列表的插入函数向队尾添加新元素。弹出操作可用于删除队首的元素（列表的最后一个元素）。这也意味着入队为 O(n)，出队为 O(1)。

class Queue():
    def __init__(self):
        Queue.items = []

    def isEmpty(self):
        return Queue.items == []

    def enqueue(self,item):
        Queue.items.insert(0,item)

    def dequeue(self):
        if Queue.items:
            return  Queue.items.pop()
        else:
            return None

    def size(self):
        return len(Queue.items)

下面是对队列的简单测试：

q = Queue()
print(q.isEmpty())  #True
q.enqueue(8.4)
q.enqueue("dog")
q.enqueue(5)
print(q.size())   #3
print(q.dequeue())  #8.4
print(q.dequeue())  #dog
print(q.dequeue())  #5

队列的应用

烫手山芋

首先，让我们看看孩子们的游戏烫手山芋，在这个游戏中(见下图)，孩子们围成一个圈，并尽可能快的将一个山芋递给旁边的孩子。在某一个时间，动作结束，有山芋的孩子从圈中移除。游戏继续开始直到剩下最后一个孩子。这个游戏相当于著名的约瑟夫问题。
我们将模拟这个烫山芋的过程。我们的程序将输入名称列表和一个称为 num 常量用于报数。它将返回以 num 为单位重复报数后剩余的最后一个人的姓名。

烫手山芋问题
求解的过程可以描述为：假设拿着山芋的孩子在队列的前面。当拿到山芋的时候，这个孩子将先出列再入队列，把他放在队列的最后。经过 num 次的出队入队后，前面的孩子将被永久移除队列。并且另一个周期开始，继续此过程，直到只剩下一个名字（队列的大小为 1）。

def hotPotato(namelist,num):
    #创建队列，将列表中的所有元素入队
    simqueue = Queue()
    for name in namelist:
        simqueue.enqueue(name)

    #当元素多于一个的时候持续循环
    while simqueue.size() > 1:
    #在指定的数据范围内元素出队再入队
        for i in range(num):
            simqueue.enqueue(simqueue.dequeue())

        #指定编号的元素出队
        simqueue.dequeue()

    #返回最后出队的元素
    return  simqueue.dequeue()

print(hotPotato(["Bill","David","Jane","Kobe","Kent","Brad"],7))