定義

雙端隊(duì)列（deque，全名double-ended queue），是一種具有隊(duì)列和棧的性質(zhì)的數(shù)據(jù)結(jié)構(gòu)。

雙端隊(duì)列中的元素可以從兩端彈出，其限定插入和刪除操作在表的兩端進(jìn)行。雙端隊(duì)列可以在隊(duì)列任意一端入隊(duì)和出隊(duì)。

python 實(shí)現(xiàn)雙端隊(duì)列

class Deque(object):
    """
    實(shí)現(xiàn)雙端隊(duì)列
    """
    def __init__(self):
        self.items = []

    def is_empty(self):
        """
        判斷隊(duì)列是否為空
        """
        return self.items == []

    def add_front(self, item):
        """
        從隊(duì)頭添加元素
        """
        self.items.insert(0, item)

    def add_end(self, item):
        """
        從隊(duì)尾添加元素
        """
        self.items.append(item)

    def pop_front(self):
        """
        從隊(duì)頭移除元素
        """
        return self.items.pop(0)

    def pop_end(self):
        """
        從隊(duì)尾移除元素
        """
        return self.items.pop()

    def size(self):
        """
        返回大小
        """
        return len(self.items)


if __name__ == '__main__':
    q = Deque()
    print("當(dāng)前隊(duì)列是否為空", q.is_empty())
    print("當(dāng)前隊(duì)列大小：", q.size())

    q.add_front(1)
    q.add_front(96)
    q.add_end(55)
    print("出隊(duì)元素為：", q.pop_front())
    print("出隊(duì)元素為：", q.pop_end())
    print("當(dāng)前隊(duì)列是否為空", q.is_empty())
    print("當(dāng)前隊(duì)列大?。?, q.size())

結(jié)果

當(dāng)前隊(duì)列是否為空 True
當(dāng)前隊(duì)列大?。?0
出隊(duì)元素為： 96
出隊(duì)元素為： 55
當(dāng)前隊(duì)列是否為空 False
當(dāng)前隊(duì)列大小： 1

經(jīng)典算法題

雙端隊(duì)列實(shí)現(xiàn)判定一個(gè)字符串是不是回文，回文從左到右和從右到左讀都一樣，比如：toot，madam
解題思路：

• 將字符串插入雙端隊(duì)列中
• 刪除首尾字符串并比較，如果能持續(xù)匹配到，最終會(huì)消耗完字符串，那么雙端隊(duì)列里要么為空，要么大小為1，這取決于輸入的字符串是奇數(shù)還是偶數(shù)。
  代碼實(shí)現(xiàn)

def is_palindrome(value):
    """
    檢測(cè)是否為回文數(shù)
    """
    q = Deque()
    for char in value:
        q.add_front(char)
    while q.size() > 1:
        # 取出首尾字符
        first = q.pop_front()
        end = q.pop_end()
        if first != end:
            return False
    return True
print(is_palindrome('madam'))
print(is_palindrome('abccb'))

結(jié)果

True
False