什么是雙端隊列?

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

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

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

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

?用Python實現雙端隊列

我們通過創建一個新類來實現雙端隊列抽象數據類型。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 等等。我們將構建一個程序，它接受一個字符串并且檢測其是否為回文。?

該問題的解決方案是使用一個雙端隊列來存儲字符串中的字符。按照從左往右的順序將字符串中的字符添加到雙端隊列的后端或前端。此時，該雙端隊列類似于一個普通的隊列。?

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

回文檢測器代碼如下：

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

總結