本文實例講述了Python實現的數據結構與算法之雙端隊列。分享給大家供大家參考。具體分析如下：
一、概述
雙端隊列（deque，全名double-ended queue）是一種具有隊列和棧性質的線性數據結構。雙端隊列也擁有兩端：隊首（front）、隊尾（rear），但與隊列不同的是，插入操作在兩端（隊首和隊尾）都可以進行，刪除操作也一樣。
二、ADT
雙端隊列ADT（抽象數據類型）一般提供以下接口：
① Deque() 創建雙端隊列
② addFront(item) 向隊首插入項
③ addRear(item) 向隊尾插入項
④ removeFront() 返回隊首的項，并從雙端隊列中刪除該項
⑤ removeRear() 返回隊尾的項，并從雙端隊列中刪除該項
⑥ empty() 判斷雙端隊列是否為空
⑦ size() 返回雙端隊列中項的個數
雙端隊列操作的示意圖如下：
三、Python實現
在Python中，有兩種方式可以實現上述的雙端隊列ADT：使用內建類型list、使用標準庫collections.deque（其實collections.deque就是Python中雙端隊列的標準實現）。
兩種方式的不同主要體現在性能上（具體參考 collections.deque | TimeComplexity）：
|
1
2
3
4
5
6
7
8
9
|
操作|實現方式 list collections.deque-----------------------------------------addFront O(n) O(1)-----------------------------------------addRear O(1) O(1)-----------------------------------------removeFront O(n) O(1)-----------------------------------------removeRear O(1) O(1) |
1、使用內建類型list
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#!/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、使用標準庫collections.deque
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#!/usr/bin/env python# -*- coding: utf-8 -*-from collections import dequeclass 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) |
四、應用
回文（palindrome）是正讀反讀都一樣的單詞或句子，是一種修辭方式和文字游戲。
英文例子：
madam
able was i ere i saw elba
中文例子：
花非花
人人為我、我為人人
如果要實現一個 回文驗證算法（驗證一個給定的字符串是否為回文），使用Deque類將非常容易：將字符串存儲到雙端隊列，同時取出首尾字符并比較是否相等，只要有一對字符不等，則該字符串不是回文；若全部相等，則該字符串為回文。具體代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#!/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 Trueif __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'不')) |
運行結果：
|
1
2
3
4
|
$ python palchecker.py"able was i ere i saw elba" is palindrome"人人為我、我為人人"是回文"What's wrong 怎么啦"不是回文 |
希望本文所述對大家的Python程序設計有所幫助。
