本篇文章給大家?guī)砹岁P于python的相關知識，其中主要介紹了雙端隊列的相關問題，包括了雙端隊列的基本概念、雙端隊列的實現(xiàn)以及雙端隊列的應用，希望對大家有幫助。

推薦學習：python教程

0. 學習目標

雙端隊列是另一個線性數(shù)據(jù)結構。雖然它也是一種受限線性表，但與棧和隊列不同的是，雙端隊列的限制很少，它的基本操作也是線性表操作的子集，但從數(shù)據(jù)類型的角度來講，它們與線性表又有著巨大的不同。本節(jié)將介紹雙端隊列的定義及其不同實現(xiàn)，并且給出雙端隊列的一些實際應用。
通過本節(jié)學習，應掌握以下內容：

• 雙端隊列的基本概念及不同實現(xiàn)方法
• 雙端隊列基本操作的實現(xiàn)及時間復雜度
• 利用雙端隊列的基本操作實現(xiàn)復雜算法

1. 雙端隊列的基本概念

1.1 雙端隊列的基本概念

雙端隊列 (double-end queue, deque) 也是插入和刪除操作分別被限制在序列兩端的線性表，但與棧和隊列不同的是，雙端隊列的限制很少，對于雙端隊列而言，隊尾 (rear) 和隊頭 (front) 均允許插入元素和刪除元素。新元素既可以被添加到隊頭， 也可以被添加到隊尾。同理，已有的元素也能從任意一端移除。某種意義上，可以認為雙端隊列是棧和隊列的結合。

盡管雙端隊列有棧和隊列的很多特性，但是它并不要求按照這兩種數(shù)據(jù)結構所限定的 LIFO 原則和 FIFO 原則操作元素。

1.2 雙端隊列抽象數(shù)據(jù)類型

除了添加和移除元素外，雙端隊列還具有初始化、判隊空和求隊長度等輔助操作。具體而言，雙端隊列的抽象數(shù)據(jù)類型定義如下：

?基本操作：
??1. __itit__(): 初始化雙端隊列
???創(chuàng)建一個空雙端隊列
??2. size(): 求取并返回雙端隊列中所含元素的個數(shù) n
???若雙端隊列為空，則返回整數(shù)0
??3. isempty(): 判斷是否為空雙端隊列
???判斷雙端隊列中是否存儲元素
??4. addfront(data): 雙端隊列隊頭添加元素
???將元素 data 插入隊頭
??5. addrear(data): 雙端隊列隊尾添加元素
???將元素 data 插入隊尾
??6. removefront(): 刪除雙端隊列隊頭元素
???刪除并返回隊頭元素
??7. removerear(): 刪除雙端隊列隊尾元素
???刪除并返回隊尾元素

2. 雙端隊列的實現(xiàn)

和普通隊列一樣，雙端隊列同樣有順序存儲和鏈式存儲兩種存儲表示方式。

2.1 順序雙端隊列的實現(xiàn)

類似于順序隊列，雙端隊列的順序存儲結構利用一組地址連續(xù)的存儲單元依次存放從雙端隊列頭到雙端隊列尾的元素，同時需要用兩個指針 front 和 rear 分別指示隊列頭元素和隊列尾元素的位置。初始化空雙端隊列時，front=rear=0，當元素入隊時，rear 加 1，而元素出隊時，front 加 1，同時為了重復利用空閑空間，我們將順序雙端隊列假設尾環(huán)狀空間，最后一個空間和第一個空間視為連續(xù)空間(具體原因參考<順序隊列>)：

同樣順序雙端隊列可以是固定長度和動態(tài)長度，當雙端隊列滿時，定長順序雙端隊列會拋出雙端隊列滿異常，動態(tài)順序雙端隊列則會動態(tài)申請空閑空間。

2.1.1 雙端隊列的初始化

順序雙端隊列的初始化需要 4 部分信息：deque 列表用于存儲數(shù)據(jù)元素，max_size 用于存儲 queue 列表的最大長度，以及 front 和 rear 分別用于記錄隊頭元素和隊尾元素的索引：

class Deque:     def __init__(self, max_size=6):         self.max_size = max_size         self.deque = [None] * self.max_size         self.front = 0         self.rear = 0

2.1.2 求雙端隊列長度

由于 front 和 rear 分別用于記錄隊頭元素和隊尾元素的索引，因此我們可以方便的計算出雙端隊列的長度；同時我們需要考慮雙端隊列為循環(huán)隊列，front 可能大于 rear，不能直接通過 rear-front，我們需要利用公式計算解決此問題：

Python 實現(xiàn)如下：

    def size(self):         return (self.rear-self.front+self.max_size) % self.max_size

2.1.3 判雙端隊列空

根據(jù) front 和 rear 的值可以方便的判斷雙端隊列是否為空：

    def isempty(self):         return self.rear==self.front

2.1.4 判雙端隊列滿

根據(jù) front 和 rear 的值可以方便的判斷雙端隊列是否還有空余空間：

    def isfull(self):         return ((self.rear+1) % self.max_size == self.front)

2.1.5 雙端隊列隊頭和隊尾添加元素

添加元素時，需要首先判斷雙端隊列中是否還有空閑空間，然后根據(jù)雙端隊列為定長順序雙端隊列或動態(tài)順序雙端隊列，添加元素操作稍有不同：
[定長順序雙端隊列的添加元素操作] 如果隊滿，則引發(fā)異常：

    # 注意隊頭和隊尾修改索引的添加元素的不同順序     def addrear(self, data):         if not self.isfull():             self.deque[self.rear] = data             self.rear = (self.rear+1) % self.max_size        else:             raise IndexError("Full Deque Exception")          def addfront(self, data):         if self.isfull():             self.resize()         if self.isempty():             # 當雙端隊列             self.deque[self.rear] = data             self.rear = (self.rear+1) % self.max_size        else:             self.front = (self.front - 1 + self.max_size) % self.max_size             self.deque[self.front] = data

[動態(tài)順序雙端隊列的添加元素操作] 如果雙端隊列滿，則首先申請新空間，然后再執(zhí)行添加操作：

    def resize(self):         new_size = 2 * self.max_size         new_deque = [None] * new_size         d = new_size - self.max_size        for i in range(self.max_size):             new_deque[(self.front+i+d) % new_size] = self.deque[(self.front+i) % self.max_size]         self.deque = new_deque         self.front = (self.front+d) % new_size         self.max_size = new_size             # 注意隊頭和隊尾修改索引的添加元素的不同順序     def addrear(self, data):         if self.isfull():             self.resize()         self.deque[self.rear] = data         self.rear = (self.rear+1) % self.max_size    def addfront(self, data):         if self.isfull():             self.resize()         self.front = (self.front - 1 + self.max_size) % self.max_size         self.deque[self.front] = data

與動態(tài)順序隊列類似，我們同樣需要考慮復制之后的索引，否則可能出現(xiàn)存在不能用的空閑空間：

添加元素的時間復雜度為O(1)。雖然當動態(tài)順序雙端隊列滿時，原雙端隊列中的元素需要首先復制到新雙端隊列中，然后添加新元素，但參考《順序表及其操作實現(xiàn)》中順序表追加操作的介紹，由于 n 次添加元素操作的總時間T(n) 與O(n) 成正比，因此其攤銷時間復雜度可以認為O(1)。

2.1.6 刪除隊頭或隊尾的元素

若雙端隊列不空，則刪除并返回指定端元素：

    # 注意隊頭和隊尾修改索引的刪除元素的不同順序     def removefront(self):         if not self.isempty():             result = self.deque[self.front]             self.front = (self.front+1) % self.max_size            return result        else:             raise IndexError("Empty Deque Exception")          def removerear(self):         if not self.isempty():             self.rear = (self.rear - 1 + self.max_size) % self.max_size             result = self.deque[self.rear]             return result        else:             raise IndexError("Empty Deque Exception")

2.2 鏈雙端隊列的實現(xiàn)

雙端隊列的另一種存儲表示方式是使用鏈式存儲結構，因此也常稱為鏈雙端隊列，其中 addfront 操作和 addrear 操作分別是通過在鏈表頭部和尾部插入元素來實現(xiàn)的，而 removefront 操作和 removerear 操作分別是通過從頭部和尾部刪除結點來實現(xiàn)的。為了降低在尾部刪除結點的時間復雜度，接下來基于雙向鏈表實現(xiàn)雙端隊列。

2.2.1 雙端隊列結點

雙端隊列的結點實現(xiàn)與雙向鏈表并無差別：

class Node:     def __init__(self, data=None):         self.data = data         self.next = None     def __str__(self):         return str(self.data)

2.2.2 雙端隊列的初始化

雙端隊列的初始化函數(shù)中，使其隊頭指針 front 和隊尾指針 rear 均指向 None，并初始化雙端隊列長度：

class Deque:     def __init__(self):         self.front = None         self.rear = None         self.num = 0

2.2.3 求雙端隊列長度

返回 num 的值用于求取雙端隊列的長度，如果沒有 num 屬性，則需要遍歷整個鏈表才能得到雙端隊列長度：

    def size(self):         return self.num

2.2.4 判雙端隊列空

根據(jù)雙端隊列的長度可以很容易的判斷其是否為空雙端隊列：

    def isempty(self):         return self.num <= 0

2.2.5 添加元素

雙端隊列添加元素時，可以在隊尾或隊頭插入新元素，因此需要修改 rear 和 front 指針，并且同時也要修改結點的 next 和 previous 指針；如果添加元素前雙端隊列為空，還需要進行相應處理：

    def addrear(self, data):         node = Node(data)         # 如果添加元素前雙端隊列為空，則添加結點時，需要將front指針也指向該結點         if self.front is None:             self.rear = node             self.front = node        else:             node.previous = self.rear             self.rear.next = node             self.rear = node         self.num += 1          def addfront(self, data):         node = Node(data)         # 如果添加元素前雙端隊列為空，則添加結點時，需要將rear指針也指向該結點         if self.rear is None:             self.front = node             self.rear = node        else:             node.next = self.front             self.front.previous = node             self.front = node         self.num += 1

2.2.6 刪除元素

若雙端隊列不空，可以從刪除隊頭或隊尾元素并返回，刪除操作需要更新隊頭指針 front 以及尾指針 rear，同時也要修改結點的 next 和 previous 指針，若出隊元素尾隊中最后一個結點，還需要進行相應處理：

    def removefront(self):         if self.isempty():             raise IndexError("Empty Queue Exception")         result = self.front.data         self.front = self.front.next         self.num -= 1         if self.isempty():             self.rear = self.front        else:             # 若刪除操作完成后，雙端隊列不為空，將 front 指針的前驅指針指向 None             self.front.previous = None         return result         def removerear(self):         if self.isempty():             raise IndexError("Empty Queue Exception")         result = self.rear.data         self.rear = self.rear.previous         self.num -= 1         if self.isempty():             self.front = self.rear        else:             # 若刪除操作完成后，雙端隊列不為空，將 rear 指針的后繼指針指向 None             self.rear.next = None         return result

2.3 雙端隊列的不同實現(xiàn)對比

雙端隊列的不同實現(xiàn)對比與棧的不同實現(xiàn)類似，可以參考《棧及其操作實現(xiàn)》。

3. 雙端隊列應用

接下來，我們首先測試上述實現(xiàn)的雙端隊列，以驗證操作的有效性，然后利用實現(xiàn)的基本操作來解決實際算法問題。

3.1 順序雙端隊列的應用

首先初始化一個順序雙端隊列 deque，然后測試相關操作：

# 初始化一個最大長度為5的雙端隊列dq = Deque(5)print('雙端隊列空?', dq.isempty())for i in range(3):     print('隊頭添加元素：', 2*i)     dq.addfront(2*i)     print('隊尾添加元素：', 2*i+1)     dq.addrear(2*i+1)print('雙端隊列長度為：', dq.size())for i in range(3):     print('隊尾刪除元素：', dq.removerear())     print('隊頭刪除元素：', dq.removefront())print('雙端隊列長度為：', dq.size())

測試程序輸出結果如下：

雙端隊列空? True隊頭添加元素： 0隊尾添加元素： 1隊頭添加元素： 2隊尾添加元素： 3隊頭添加元素： 4隊尾添加元素： 5雙端隊列長度為： 6隊尾刪除元素： 5隊頭刪除元素： 4隊尾刪除元素： 3隊頭刪除元素： 2隊尾刪除元素： 1隊頭刪除元素： 0雙端隊列長度為： 0

3.2 鏈雙端隊列的應用

首先初始化一個鏈雙端隊列 queue，然后測試相關操作：

# 初始化新隊列dq = Deque()print('雙端隊列空?', dq.isempty())for i in range(3):     print('隊頭添加元素：', i)     dq.addfront(2*i)     print('隊尾添加元素：', i+3)     dq.addrear(2*i+1)print('雙端隊列長度為：', dq.size())for i in range(3):     print('隊尾刪除元素：', dq.removerear())     print('隊頭刪除元素：', dq.removefront())print('雙端隊列長度為：', dq.size())

測試程序輸出結果如下：

雙端隊列空? True隊頭添加元素： 0隊尾添加元素： 3隊頭添加元素： 1隊尾添加元素： 4隊頭添加元素： 2隊尾添加元素： 5雙端隊列長度為： 6隊尾刪除元素： 5隊頭刪除元素： 4隊尾刪除元素： 3隊頭刪除元素： 2隊尾刪除元素： 1隊頭刪除元素： 0雙端隊列長度為： 0

3.3 利用雙端隊列基本操作實現(xiàn)復雜算法

[1] 給定一字符串 string (如：abamaba)，檢查其是否為回文。

使用雙端隊列可以快速檢查一字符串是否為回文序列，只需要將字符串中字符依次入隊，然后從雙端隊列兩端依次彈出元素，對比它們是否相等：

def ispalindrome(string):     deque = Deque()     for ch in string:         deque.addfront(ch)     flag = True     while deque.size() > 1 and flag:         ch1 = deque.removefront()         ch2 = deque.removerear()         if ch1 != ch2:             flag = False     return flag

驗證算法有效性：

print('abcba是否為回文序列：', ispalindrome('abcba'))print('charaahc是否為回文序列：', ispalindrome('charaahc'))

結果輸出如下：

abcba是否為回文序列： True charaahc是否為回文序列： False

推薦學習：python教程