Python數據結構與算法的雙端隊列詳解
什么是雙端隊列?
雙端隊列是與隊列類似的有序集合。它有一前、一后兩端,元素在其中保持自己的位置。與隊列不同的是,雙端隊列對在哪一端添加和移除元素沒有任何限制。新元素既可以被添加到前端,也可以被添加到后端。同理,已有的元素也能從任意一端移除。某種意義上,雙端隊列可以是棧和隊列的結合。
值得注意的是,盡管雙端隊列有棧和隊列的很多特性,但是它并不要求按照這兩種數據結構分別規(guī)定的LIFO原則和FIFO原則操作元素。具體的排序原則取決于其使用者。
?雙端隊列抽象數據類型由下面的結構和操作定義。如前所述,雙端隊列是元素的有序集合,其任何一端都允許添加或移除元素。雙端隊列支持以下操作:?
- 創(chuàng)建一個空的雙端隊列。它不需要參數,且會返回一個空的雙端隊列。 Deque()
- 將一個元素添加到雙端隊列的前端。它接受一個元素作為參數,沒有返回值。 addFront(item)
- 將一個元素添加到雙端隊列的后端。它接受一個元素作為參數,沒有返回值。 addRear(item)
- 從雙端隊列的前端移除一個元素。它不需要參數,且會返回一個元素,并修改雙端隊列的內容。 removeFront()
- 從雙端隊列的后端移除一個元素。它不需要參數,且會返回一個元素, 并修改雙端隊列的內容。 removeRear()
- 檢查雙端隊列是否為空。它不需要參數,且會返回一個布爾值。 isEmpty()
- 返回雙端隊列中元素的數目。它不需要參數,且會返回一個整數。 size()
?用Python實現雙端隊列
我們通過創(chuàng)建一個新類來實現雙端隊列抽象數據類型。Python列表再一次提供了 很多簡便的方法來幫助我們構建雙端隊列。在下面的代碼中,我們假設雙端隊列的后端是列表的位置0處(列表的最左端)。
class Deque: def __init__(self): self.items = [] def isEmpty(self): return self.items == [] # 往雙端隊列前端添加元素 def addFront(self, item): self.items.append(item) # 往雙端隊列后端添加元素 def addRear(self, item): self.items.insert(0, item) # 在前端移除雙端隊列元素 def removeFront(self): return self.items.pop() # 在后端移除雙端隊列元素 def removeRear(self): return self.items.pop(0) def size(self): return len(self.items) def look(self): print(self.items)
removeFront 使用 pop 方法移除列表中的最后一個元素,removeRear 則使用 pop(0) 方法移除列表中的第一個元素。同理,之所以 addRear 使用 insert 方法,是因為 append 方法只能在列表的最后(最右端)添加元素。?
代碼運行效果如下:
運用雙端隊列構建回文檢測器
我們現在運用雙端隊列解決一個非常有趣的經典問題:回文問題。回文是指從前往后讀和從后往前讀都一樣的字符串,例如 sos、radar、toot、madam 等等。我們將構建一個程序,它接受一個字符串并且檢測其是否為回文。?
該問題的解決方案是使用一個雙端隊列來存儲字符串中的字符。按照從左往右的順序將字符串中的字符添加到雙端隊列的后端或前端。此時,該雙端隊列類似于一個普通的隊列。?
由于可以從前后兩端移除元素,因此我們能夠比較兩個元素,并且只有在二者相等時才繼續(xù)。如果一直匹配第一個和最后一個元素,最終會處理完所有的字符(如果字符數是偶數),或者剩下只有一個元素的雙端隊列(如果字符數是奇數)。任意一種結果都表明輸入字符串是回文。?
回文檢測器代碼如下:
class Deque: def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def addFront(self, item): self.items.append(item) def addRear(self, item): self.items.insert(0, item) def removeFront(self): return self.items.pop() def removeRear(self): return self.items.pop(0) def size(self): return len(self.items) def palchecker(aString): chardeque = Deque() for ch in aString: chardeque.addFront(ch) stillEqual = True while chardeque.size() > 1 and stillEqual: first = chardeque.removeFront() last = chardeque.removeRear() if first != last: stillEqual = False return stillEqual
總結
本篇文章就到這里了,希望能夠給你帶來幫助,也希望您能夠多多關注腳本之家的更多內容!
相關文章
2020年10款優(yōu)秀的Python第三方庫,看看有你中意的嗎?
2020已經過去,在過去的一年里,又有非常多優(yōu)秀的Python庫涌現出來。相對于numpy、TensorFlow、pandas這些已經經過多年維護、迭代,對于大多數Python開發(fā)者耳熟能詳的庫不同。2021-01-01python字符串加密解密的三種方法分享(base64 win32com)
這篇文章主要介紹了python字符串加密解密的三種方法,包括用base64、使用win32com.client、自己寫的加密解密算法三種方法,大家參考使用吧2014-01-01python使用pip安裝SciPy、SymPy、matplotlib教程
今天小編大家分享一篇python使用pip安裝SciPy、SymPy、matplotlib教程,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2019-11-11