Python實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之雙端隊列詳解
本文實例講述了Python實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之雙端隊列。分享給大家供大家參考。具體分析如下:
一、概述
雙端隊列(deque,全名double-ended queue)是一種具有隊列和棧性質(zhì)的線性數(shù)據(jù)結(jié)構(gòu)。雙端隊列也擁有兩端:隊首(front)、隊尾(rear),但與隊列不同的是,插入操作在兩端(隊首和隊尾)都可以進行,刪除操作也一樣。
二、ADT
雙端隊列ADT(抽象數(shù)據(jù)類型)一般提供以下接口:
① Deque() 創(chuàng)建雙端隊列
② addFront(item) 向隊首插入項
③ addRear(item) 向隊尾插入項
④ removeFront() 返回隊首的項,并從雙端隊列中刪除該項
⑤ removeRear() 返回隊尾的項,并從雙端隊列中刪除該項
⑥ empty() 判斷雙端隊列是否為空
⑦ size() 返回雙端隊列中項的個數(shù)
雙端隊列操作的示意圖如下:
三、Python實現(xiàn)
在Python中,有兩種方式可以實現(xiàn)上述的雙端隊列ADT:使用內(nèi)建類型list、使用標準庫collections.deque(其實collections.deque就是Python中雙端隊列的標準實現(xiàn))。
兩種方式的不同主要體現(xiàn)在性能上(具體參考 collections.deque | TimeComplexity):
操作|實現(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)建類型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、使用標準庫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
中文例子:
花非花
人人為我、我為人人
如果要實現(xiàn)一個 回文驗證算法(驗證一個給定的字符串是否為回文),使用Deque類將非常容易:將字符串存儲到雙端隊列,同時取出首尾字符并比較是否相等,只要有一對字符不等,則該字符串不是回文;若全部相等,則該字符串為回文。具體代碼如下:
#!/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'不'))
運行結(jié)果:
$ python palchecker.py "able was i ere i saw elba" is palindrome "人人為我、我為人人"是回文 "What's wrong 怎么啦"不是回文
希望本文所述對大家的Python程序設(shè)計有所幫助。
相關(guān)文章
用Python實現(xiàn)BP神經(jīng)網(wǎng)絡(luò)(附代碼)
這篇文章主要介紹了用Python實現(xiàn)BP神經(jīng)網(wǎng)絡(luò)(附代碼),文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-07-07- 我們知道python只定義了6種數(shù)據(jù)類型,字符串,整數(shù),浮點數(shù),列表,元組,字典。但是C語言中有些字節(jié)型的變量,在python中該如何實現(xiàn)呢?這點頗為重要,特別是要在網(wǎng)絡(luò)上進行數(shù)據(jù)傳輸?shù)脑挕?/div> 2014-06-06
利用Python+Java調(diào)用Shell腳本時的死鎖陷阱詳解
這篇文章主要給大家介紹了關(guān)于利用Python+Java調(diào)用Shell腳本時的死鎖陷阱的相關(guān)資料,文章通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2018-01-01Django框架實現(xiàn)在線考試系統(tǒng)的示例代碼
這篇文章主要介紹了Django框架實現(xiàn)在線考試系統(tǒng)的示例代碼,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11最新評論