快捷導(dǎo)航

Python實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之隊(duì)列詳解

更新時(shí)間：2015年04月22日 14:24:05 作者：RussellLuo

這篇文章主要介紹了Python實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之隊(duì)列,詳細(xì)分析了隊(duì)列的定義、功能與Python實(shí)現(xiàn)隊(duì)列的相關(guān)技巧,以及具體的用法,需要的朋友可以參考下

本文實(shí)例講述了Python實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之隊(duì)列。分享給大家供大家參考。具體分析如下：

一、概述

隊(duì)列（Queue）是一種先進(jìn)先出（FIFO）的線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，插入操作在隊(duì)尾（rear）進(jìn)行，刪除操作在隊(duì)首（front）進(jìn)行。

二、ADT

隊(duì)列ADT（抽象數(shù)據(jù)類(lèi)型）一般提供以下接口：

① Queue() 創(chuàng)建隊(duì)列
② enqueue(item) 向隊(duì)尾插入項(xiàng)
③ dequeue() 返回隊(duì)首的項(xiàng)，并從隊(duì)列中刪除該項(xiàng)
④ empty() 判斷隊(duì)列是否為空
⑤ size() 返回隊(duì)列中項(xiàng)的個(gè)數(shù)

隊(duì)列操作的示意圖如下：

三、Python實(shí)現(xiàn)

使用Python的內(nèi)建類(lèi)型list列表，可以很方便地實(shí)現(xiàn)隊(duì)列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)

四、應(yīng)用

著名的約瑟夫斯問(wèn)題（Josephus Problem）是應(yīng)用隊(duì)列（確切地說(shuō)，是循環(huán)隊(duì)列）的典型案例。在約瑟夫斯問(wèn)題中，參與者圍成一個(gè)圓圈，從某個(gè)人（隊(duì)首）開(kāi)始報(bào)數(shù)，報(bào)數(shù)到n+1的人退出圓圈，然后從退出人的下一位重新開(kāi)始報(bào)數(shù)；重復(fù)以上動(dòng)作，直到只剩下一個(gè)人為止。

值得注意的是，Queue類(lèi)只實(shí)現(xiàn)了簡(jiǎn)單隊(duì)列，上述問(wèn)題實(shí)際上需要用循環(huán)隊(duì)列來(lái)解決。在報(bào)數(shù)過(guò)程中，通過(guò)“將（從隊(duì)首）出隊(duì)的人再入隊(duì)（到隊(duì)尾）”來(lái)模擬循環(huán)隊(duì)列的行為。具體代碼如下：

#!/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))

運(yùn)行結(jié)果：