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），但與隊列不同的是，插入操作在兩端（隊首和隊尾）都可以進(jìn)行，刪除操作也一樣。
二、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、使用標(biāo)準(zhǔn)庫collections.deque（其實collections.deque就是Python中雙端隊列的標(biāo)準(zhǔn)實現(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、使用標(biāo)準(zhǔn)庫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)文章
這篇文章主要介紹了如何利用Pytorch計算三角函數(shù),文中有非常詳細(xì)的代碼示例,對正在學(xué)習(xí)python的小伙伴們有很好地幫助,需要的朋友可以參考下2021-05-05
淺談keras 的抽象后端(from keras import backend as K)
這篇文章主要介紹了淺談keras 的抽象后端(from keras import backend as K)，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-06-06
這篇文章主要為大家詳細(xì)介紹了python3.4遠(yuǎn)程控制電腦開關(guān)機，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-05-05
基于python實現(xiàn)分析識別文章/內(nèi)容中的高頻詞和關(guān)鍵詞
要分析一篇文章的高頻詞和關(guān)鍵詞,可以使用 Python 中的 nltk 庫和 collections 庫或者jieba庫來實現(xiàn),本篇文章介紹基于兩種庫分別實現(xiàn)分析內(nèi)容中的高頻詞和關(guān)鍵詞,需要的朋友可以參考下2023-09-09
這篇文章主要為大家介紹了Python入門經(jīng)典必背的18個程序。注意：這是初學(xué)者要牢記的 18 個代碼，入門之后就簡單了，快跟隨小編一起來學(xué)習(xí)一下吧2023-02-02
這篇文章主要介紹了Pandas0.25來了千萬別錯過這10大好用的新功能,都有哪些新功能，文中給大家詳細(xì)介紹，需要的朋友可以參考下2019-08-08
在Anaconda里安裝OpenCV的方法有很多,下面這篇文章主要給大家介紹了關(guān)于Anaconda安裝OpenCV的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-09-09
這篇文章主要介紹了Python?yield?關(guān)鍵詞，要理解yield的作用，你必須理解生成器是什么。在理解生成器之前，必須先理解迭代器。下面文章我們就先從2021-12-12
迭代器開始展開yield關(guān)鍵詞的相關(guān)自資料 ,需要的朋友可以參考一下
python實現(xiàn)去除下載電影和電視劇文件名中的多余字符的方法
這篇文章主要介紹了python實現(xiàn)去除下載電影和電視劇文件名中的多余字符的方法,可以批量修改視頻文件名稱,非常具有實用價值,需要的朋友可以參考下2014-09-09
今天小編就為大家分享一篇python順序的讀取文件夾下名稱有序的文件方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-07-07