什么是雙端隊列?

雙端隊列是與隊列類似的有序集合。它有一前、一后兩端，元素在其中保持自己的位置。與隊列不同的是，雙端隊列對在哪一端添加和移除元素沒有任何限制。新元素既可以被添加到前端，也可以被添加到后端。同理，已有的元素也能從任意一端移除。某種意義上，雙端隊列可以是棧和隊列的結(jié)合。

值得注意的是，盡管雙端隊列有棧和隊列的很多特性，但是它并不要求按照這兩種數(shù)據(jù)結(jié)構(gòu)分別規(guī)定的LIFO原則和FIFO原則操作元素。具體的排序原則取決于其使用者。

?雙端隊列抽象數(shù)據(jù)類型由下面的結(jié)構(gòu)和操作定義。如前所述，雙端隊列是元素的有序集合，其任何一端都允許添加或移除元素。雙端隊列支持以下操作：?

• 創(chuàng)建一個空的雙端隊列。它不需要參數(shù)，且會返回一個空的雙端隊列。 Deque()
• 將一個元素添加到雙端隊列的前端。它接受一個元素作為參數(shù)，沒有返回值。 addFront(item)
• 將一個元素添加到雙端隊列的后端。它接受一個元素作為參數(shù)，沒有返回值。 addRear(item)
• 從雙端隊列的前端移除一個元素。它不需要參數(shù)，且會返回一個元素，并修改雙端隊列的內(nèi)容。 removeFront()
• 從雙端隊列的后端移除一個元素。它不需要參數(shù)，且會返回一個元素， 并修改雙端隊列的內(nèi)容。 removeRear()
• 檢查雙端隊列是否為空。它不需要參數(shù)，且會返回一個布爾值。 isEmpty()
• 返回雙端隊列中元素的數(shù)目。它不需要參數(shù)，且會返回一個整數(shù)。 size()

?用Python實現(xiàn)雙端隊列

我們通過創(chuàng)建一個新類來實現(xiàn)雙端隊列抽象數(shù)據(jù)類型。Python列表再一次提供了 很多簡便的方法來幫助我們構(gòu)建雙端隊列。在下面的代碼中，我們假設(shè)雙端隊列的后端是列表的位置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 方法只能在列表的最后（最右端）添加元素。?

代碼運行效果如下：

運用雙端隊列構(gòu)建回文檢測器

我們現(xiàn)在運用雙端隊列解決一個非常有趣的經(jīng)典問題：回文問題?；匚氖侵?strong>從前往后讀和從后往前讀都一樣的字符串，例如 sos、radar、toot、madam 等等。我們將構(gòu)建一個程序，它接受一個字符串并且檢測其是否為回文。?

該問題的解決方案是使用一個雙端隊列來存儲字符串中的字符。按照從左往右的順序?qū)⒆址械淖址砑拥诫p端隊列的后端或前端。此時，該雙端隊列類似于一個普通的隊列。?

由于可以從前后兩端移除元素，因此我們能夠比較兩個元素，并且只有在二者相等時才繼續(xù)。如果一直匹配第一個和最后一個元素，最終會處理完所有的字符（如果字符數(shù)是偶數(shù)），或者剩下只有一個元素的雙端隊列（如果字符數(shù)是奇數(shù)）。任意一種結(jié)果都表明輸入字符串是回文。?

回文檢測器代碼如下：

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

總結(jié)

本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!   

最新評論