本篇文章給大家?guī)?lái)了關(guān)于python的相關(guān)知識(shí)，其中主要介紹了雙端隊(duì)列的相關(guān)問(wèn)題，包括了雙端隊(duì)列的基本概念、雙端隊(duì)列的實(shí)現(xiàn)以及雙端隊(duì)列的應(yīng)用，希望對(duì)大家有幫助。

推薦學(xué)習(xí)：python教程

0. 學(xué)習(xí)目標(biāo)

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

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

1. 雙端隊(duì)列的基本概念

1.1 雙端隊(duì)列的基本概念

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

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

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

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

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

2. 雙端隊(duì)列的實(shí)現(xiàn)

和普通隊(duì)列一樣，雙端隊(duì)列同樣有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)表示方式。

2.1 順序雙端隊(duì)列的實(shí)現(xiàn)

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

同樣順序雙端隊(duì)列可以是固定長(zhǎng)度和動(dòng)態(tài)長(zhǎng)度，當(dāng)雙端隊(duì)列滿時(shí)，定長(zhǎng)順序雙端隊(duì)列會(huì)拋出雙端隊(duì)列滿異常，動(dòng)態(tài)順序雙端隊(duì)列則會(huì)動(dòng)態(tài)申請(qǐng)空閑空間。

2.1.1 雙端隊(duì)列的初始化

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

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 求雙端隊(duì)列長(zhǎng)度

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

Python 實(shí)現(xiàn)如下：

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

2.1.3 判雙端隊(duì)列空

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

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

2.1.4 判雙端隊(duì)列滿

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

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

2.1.5 雙端隊(duì)列隊(duì)頭和隊(duì)尾添加元素

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

    # 注意隊(duì)頭和隊(duì)尾修改索引的添加元素的不同順序     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():             # 當(dāng)雙端隊(duì)列             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

[動(dòng)態(tài)順序雙端隊(duì)列的添加元素操作] 如果雙端隊(duì)列滿，則首先申請(qǐng)新空間，然后再執(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             # 注意隊(duì)頭和隊(duì)尾修改索引的添加元素的不同順序     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

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

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

2.1.6 刪除隊(duì)頭或隊(duì)尾的元素

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

    # 注意隊(duì)頭和隊(duì)尾修改索引的刪除元素的不同順序     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 鏈雙端隊(duì)列的實(shí)現(xiàn)

雙端隊(duì)列的另一種存儲(chǔ)表示方式是使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因此也常稱為鏈雙端隊(duì)列，其中 addfront 操作和 addrear 操作分別是通過(guò)在鏈表頭部和尾部插入元素來(lái)實(shí)現(xiàn)的，而 removefront 操作和 removerear 操作分別是通過(guò)從頭部和尾部刪除結(jié)點(diǎn)來(lái)實(shí)現(xiàn)的。為了降低在尾部刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度，接下來(lái)基于雙向鏈表實(shí)現(xiàn)雙端隊(duì)列。

2.2.1 雙端隊(duì)列結(jié)點(diǎn)

雙端隊(duì)列的結(jié)點(diǎn)實(shí)現(xiàn)與雙向鏈表并無(wú)差別：

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

2.2.2 雙端隊(duì)列的初始化

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

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

2.2.3 求雙端隊(duì)列長(zhǎng)度

返回 num 的值用于求取雙端隊(duì)列的長(zhǎng)度，如果沒(méi)有 num 屬性，則需要遍歷整個(gè)鏈表才能得到雙端隊(duì)列長(zhǎng)度：

    def size(self):         return self.num

2.2.4 判雙端隊(duì)列空

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

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

2.2.5 添加元素

雙端隊(duì)列添加元素時(shí)，可以在隊(duì)尾或隊(duì)頭插入新元素，因此需要修改 rear 和 front 指針，并且同時(shí)也要修改結(jié)點(diǎn)的 next 和 previous 指針；如果添加元素前雙端隊(duì)列為空，還需要進(jìn)行相應(yīng)處理：

    def addrear(self, data):         node = Node(data)         # 如果添加元素前雙端隊(duì)列為空，則添加結(jié)點(diǎn)時(shí)，需要將front指針也指向該結(jié)點(diǎn)         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)         # 如果添加元素前雙端隊(duì)列為空，則添加結(jié)點(diǎn)時(shí)，需要將rear指針也指向該結(jié)點(diǎn)         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 刪除元素

若雙端隊(duì)列不空，可以從刪除隊(duì)頭或隊(duì)尾元素并返回，刪除操作需要更新隊(duì)頭指針 front 以及尾指針 rear，同時(shí)也要修改結(jié)點(diǎn)的 next 和 previous 指針，若出隊(duì)元素尾隊(duì)中最后一個(gè)結(jié)點(diǎn)，還需要進(jìn)行相應(yīng)處理：

    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:             # 若刪除操作完成后，雙端隊(duì)列不為空，將 front 指針的前驅(qū)指針指向 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:             # 若刪除操作完成后，雙端隊(duì)列不為空，將 rear 指針的后繼指針指向 None             self.rear.next = None         return result

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

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

3. 雙端隊(duì)列應(yīng)用

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

3.1 順序雙端隊(duì)列的應(yīng)用

首先初始化一個(gè)順序雙端隊(duì)列 deque，然后測(cè)試相關(guān)操作：

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

測(cè)試程序輸出結(jié)果如下：

雙端隊(duì)列空? True隊(duì)頭添加元素： 0隊(duì)尾添加元素： 1隊(duì)頭添加元素： 2隊(duì)尾添加元素： 3隊(duì)頭添加元素： 4隊(duì)尾添加元素： 5雙端隊(duì)列長(zhǎng)度為： 6隊(duì)尾刪除元素： 5隊(duì)頭刪除元素： 4隊(duì)尾刪除元素： 3隊(duì)頭刪除元素： 2隊(duì)尾刪除元素： 1隊(duì)頭刪除元素： 0雙端隊(duì)列長(zhǎng)度為： 0

3.2 鏈雙端隊(duì)列的應(yīng)用

首先初始化一個(gè)鏈雙端隊(duì)列 queue，然后測(cè)試相關(guān)操作：

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

測(cè)試程序輸出結(jié)果如下：

雙端隊(duì)列空? True隊(duì)頭添加元素： 0隊(duì)尾添加元素： 3隊(duì)頭添加元素： 1隊(duì)尾添加元素： 4隊(duì)頭添加元素： 2隊(duì)尾添加元素： 5雙端隊(duì)列長(zhǎng)度為： 6隊(duì)尾刪除元素： 5隊(duì)頭刪除元素： 4隊(duì)尾刪除元素： 3隊(duì)頭刪除元素： 2隊(duì)尾刪除元素： 1隊(duì)頭刪除元素： 0雙端隊(duì)列長(zhǎng)度為： 0

3.3 利用雙端隊(duì)列基本操作實(shí)現(xiàn)復(fù)雜算法

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

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

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

驗(yàn)證算法有效性：

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

結(jié)果輸出如下：

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

推薦學(xué)習(xí)：python教程