一、概述
隊列(Queue)是一種先進先出(FIFO)的線性數據結構，插入操作在隊尾(rear)進行，刪除操作在隊首(front)進行。
二、ADT
隊列ADT(抽象數據類型)一般提供以下接口：
Queue() 創建隊列
enqueue(item) 向隊尾插入項
dequeue() 返回隊首的項，并從隊列中刪除該項
empty() 判斷隊列是否為空
size() 返回隊列中項的個數
隊列操作的示意圖如下：
三、Python實現
使用Python的內建類型list列表，可以很方便地實現隊列ADT：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
return self.items.pop(0)
def empty(self):
return self.size() == 0
def size(self):
return len(self.items)
四、應用
著名的 約瑟夫斯問題(Josephus Problem)是應用隊列(確切地說，是循環隊列)的典型案例。在 約瑟夫斯問題 中，參與者圍成一個圓圈，從某個人(隊首)開始報數，報數到n+1的人退出圓圈，然后從退出人的下一位重新開始報數；重復以上動作，直到只剩下一個人為止。
值得注意的是，Queue類只實現了簡單隊列，上述問題實際上需要用循環隊列來解決。在報數過程中，通過“將(從隊首)出隊的人再入隊(到隊尾)”來模擬循環隊列的行為。具體代碼如下：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def josephus(namelist, num):
simqueue = Queue()
for name in namelist:
simqueue.enqueue(name)
while simqueue.size() > 1:
for i in xrange(num):
simqueue.enqueue(simqueue.dequeue())
simqueue.dequeue()
return simqueue.dequeue()
if __name__ == '__main__':
print(josephus(["Bill", "David", "Kent", "Jane", "Susan", "Brad"], 3))
運行結果：
$ python josephus.py
Susan
)
）)
