什么是雙端隊(duì)列?

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

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

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

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

?用Python實(shí)現(xiàn)雙端隊(duì)列

我們通過創(chuàng)建一個(gè)新類來實(shí)現(xiàn)雙端隊(duì)列抽象數(shù)據(jù)類型。Python列表再一次提供了 很多簡便的方法來幫助我們構(gòu)建雙端隊(duì)列。在下面的代碼中，我們假設(shè)雙端隊(duì)列的后端是列表的位置0處（列表的最左端）。

class Deque:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    # 往雙端隊(duì)列前端添加元素
    def addFront(self, item):
        self.items.append(item)
    # 往雙端隊(duì)列后端添加元素
    def addRear(self, item):
        self.items.insert(0, item)
    # 在前端移除雙端隊(duì)列元素
    def removeFront(self):
        return self.items.pop()
    # 在后端移除雙端隊(duì)列元素
    def removeRear(self):
        return self.items.pop(0)
    def size(self):
        return len(self.items)
    def look(self):
        print(self.items)

removeFront 使用?pop?方法移除列表中的最后一個(gè)元素，removeRear 則使用?pop(0)?方法移除列表中的第一個(gè)元素。同理，之所以 addRear 使用?insert?方法，是因?yàn)?append?方法只能在列表的最后（最右端）添加元素。?

代碼運(yùn)行效果如下：

運(yùn)用雙端隊(duì)列構(gòu)建回文檢測(cè)器

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

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

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

回文檢測(cè)器代碼如下：

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é)