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

本文實(shí)例講述了Python實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之雙端隊(duì)列。分享給大家供大家參考。具體分析如下：
一、概述
雙端隊(duì)列（deque，全名double-ended queue）是一種具有隊(duì)列和棧性質(zhì)的線性數(shù)據(jù)結(jié)構(gòu)。雙端隊(duì)列也擁有兩端：隊(duì)首（front）、隊(duì)尾（rear），但與隊(duì)列不同的是，插入操作在兩端（隊(duì)首和隊(duì)尾）都可以進(jìn)行，刪除操作也一樣。
二、ADT
雙端隊(duì)列ADT（抽象數(shù)據(jù)類(lèi)型）一般提供以下接口：
① Deque() 創(chuàng)建雙端隊(duì)列
② addFront(item) 向隊(duì)首插入項(xiàng)
③ addRear(item) 向隊(duì)尾插入項(xiàng)
④ removeFront() 返回隊(duì)首的項(xiàng)，并從雙端隊(duì)列中刪除該項(xiàng)
⑤ removeRear() 返回隊(duì)尾的項(xiàng)，并從雙端隊(duì)列中刪除該項(xiàng)
⑥ empty() 判斷雙端隊(duì)列是否為空
⑦ size() 返回雙端隊(duì)列中項(xiàng)的個(gè)數(shù)

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

三、Python實(shí)現(xiàn)
在Python中，有兩種方式可以實(shí)現(xiàn)上述的雙端隊(duì)列ADT：使用內(nèi)建類(lèi)型list、使用標(biāo)準(zhǔn)庫(kù)collections.deque（其實(shí)collections.deque就是Python中雙端隊(duì)列的標(biāo)準(zhǔn)實(shí)現(xiàn)）。

兩種方式的不同主要體現(xiàn)在性能上（具體參考 collections.deque | TimeComplexity）：
    
操作|實(shí)現(xiàn)方式  list  collections.deque
-----------------------------------------
addFront    O(n)  O(1)
-----------------------------------------
addRear     O(1)  O(1)
-----------------------------------------
removeFront   O(n)  O(1)
-----------------------------------------
removeRear   O(1)  O(1)

1、使用內(nèi)建類(lèi)型list
    
#!/usr/bin/env python
# -*- coding: utf-8 -*-
class Deque:
  def __init__(self):
    self.items = []
  def addFront(self, item):
    self.items.insert(0, item)
  def addRear(self, item):
    self.items.append(item)
  def removeFront(self):
    return self.items.pop(0)
  def removeRear(self):
    return self.items.pop()
  def empty(self):
    return self.size() == 0
  def size(self):
    return len(self.items)

2、使用標(biāo)準(zhǔn)庫(kù)collections.deque    
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from collections import deque
class Deque:
  def __init__(self):
    self.items = deque()
  def addFront(self, item):
    self.items.appendleft(item)
  def addRear(self, item):
    self.items.append(item)
  def removeFront(self):
    return self.items.popleft()
  def removeRear(self):
    return self.items.pop()
  def empty(self):
    return self.size() == 0
  def size(self):
    return len(self.items)

四、應(yīng)用

回文（palindrome）是正讀反讀都一樣的單詞或句子，是一種修辭方式和文字游戲。

英文例子：

madam
able was i ere i saw elba

中文例子：

花非花
人人為我、我為人人
如果要實(shí)現(xiàn)一個(gè) 回文驗(yàn)證算法（驗(yàn)證一個(gè)給定的字符串是否為回文），使用Deque類(lèi)將非常容易：將字符串存儲(chǔ)到雙端隊(duì)列，同時(shí)取出首尾字符并比較是否相等，只要有一對(duì)字符不等，則該字符串不是回文；若全部相等，則該字符串為回文。具體代碼如下：    
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def palchecker(aString):
  chardeque = Deque()
  for ch in aString:
    chardeque.addRear(ch)
  while chardeque.size() > 1:
    first = chardeque.removeFront()
    last = chardeque.removeRear()
    if first != last:
      return False
  return True
if __name__ == '__main__':
  str1 = 'able was i ere i saw elba'
  print('"%s" is%s palindrome' % (str1, '' if palchecker(str1) else ' not'))
  str2 = u'人人為我、我為人人'
  print(u'"%s"%s是回文' % (str2, u'' if palchecker(str2) else u'不'))
  str3 = u"What's wrong 怎么啦"
  print(u'"%s"%s是回文' % (str3, u'' if palchecker(str3) else u'不'))

運(yùn)行結(jié)果：    
$ python palchecker.py
"able was i ere i saw elba" is palindrome
"人人為我、我為人人"是回文
"What's wrong 怎么啦"不是回文

希望本文所述對(duì)大家的Python程序設(shè)計(jì)有所幫助。