站長資訊網本篇文章給大家帶來了關于python的相關知識，其中主要介紹了雙端隊列的相關問題，包括了雙端隊列的基本概念、雙端隊列的實現以及雙端隊列的應用，希望對大家有幫助。
推薦學習：python教程
0. 學習目標
雙端隊列是另一個線性數據結構。雖然它也是一種受限線性表，但與棧和隊列不同的是，雙端隊列的限制很少，它的基本操作也是線性表操作的子集，但從數據類型的角度來講，它們與線性表又有著巨大的不同。本節將介紹雙端隊列的定義及其不同實現，并且給出雙端隊列的一些實際應用。
通過本節學習，應掌握以下內容：
- 雙端隊列的基本概念及不同實現方法
- 雙端隊列基本操作的實現及時間復雜度
- 利用雙端隊列的基本操作實現復雜算法
1. 雙端隊列的基本概念
1.1 雙端隊列的基本概念
雙端隊列 (double-end queue, deque) 也是插入和刪除操作分別被限制在序列兩端的線性表，但與棧和隊列不同的是，雙端隊列的限制很少，對于雙端隊列而言，隊尾 (rear) 和隊頭 (front) 均允許插入元素和刪除元素。新元素既可以被添加到隊頭， 也可以被添加到隊尾。同理，已有的元素也能從任意一端移除。某種意義上，可以認為雙端隊列是棧和隊列的結合。
盡管雙端隊列有棧和隊列的很多特性，但是它并不要求按照這兩種數據結構所限定的 LIFO 原則和 FIFO 原則操作元素。
1.2 雙端隊列抽象數據類型
除了添加和移除元素外，雙端隊列還具有初始化、判隊空和求隊長度等輔助操作。具體而言，雙端隊列的抽象數據類型定義如下：
?基本操作：
??1. __itit__(): 初始化雙端隊列
???創建一個空雙端隊列
??2. size(): 求取并返回雙端隊列中所含元素的個數 n
???若雙端隊列為空，則返回整數0
??3. isempty(): 判斷是否為空雙端隊列
???判斷雙端隊列中是否存儲元素
??4. addfront(data): 雙端隊列隊頭添加元素
???將元素 data 插入隊頭
??5. addrear(data): 雙端隊列隊尾添加元素
???將元素 data 插入隊尾
??6. removefront(): 刪除雙端隊列隊頭元素
???刪除并返回隊頭元素
??7. removerear(): 刪除雙端隊列隊尾元素
???刪除并返回隊尾元素
2. 雙端隊列的實現
和普通隊列一樣，雙端隊列同樣有順序存儲和鏈式存儲兩種存儲表示方式。
2.1 順序雙端隊列的實現
類似于順序隊列，雙端隊列的順序存儲結構利用一組地址連續的存儲單元依次存放從雙端隊列頭到雙端隊列尾的元素，同時需要用兩個指針 front 和 rear 分別指示隊列頭元素和隊列尾元素的位置。初始化空雙端隊列時，front=rear=0，當元素入隊時，rear 加 1，而元素出隊時，front 加 1，同時為了重復利用空閑空間，我們將順序雙端隊列假設尾環狀空間，最后一個空間和第一個空間視為連續空間(具體原因參考<順序隊列>)：
同樣順序雙端隊列可以是固定長度和動態長度，當雙端隊列滿時，定長順序雙端隊列會拋出雙端隊列滿異常，動態順序雙端隊列則會動態申請空閑空間。
2.1.1 雙端隊列的初始化
順序雙端隊列的初始化需要 4 部分信息：deque 列表用于存儲數據元素，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 分別用于記錄隊頭元素和隊尾元素的索引，因此我們可以方便的計算出雙端隊列的長度；同時我們需要考慮雙端隊列為循環隊列，front 可能大于 rear，不能直接通過 rear-front，我們需要利用公式計算解決此問題：
Python 實現如下：
def size(self): return (self.rear-self.front+self.max_size) % self.max_size
2.1.3 判雙端隊列空
根據 front 和 rear 的值可以方便的判斷雙端隊列是否為空：
def isempty(self): return self.rear==self.front
2.1.4 判雙端隊列滿
根據 front 和 rear 的值可以方便的判斷雙端隊列是否還有空余空間：
def isfull(self): return ((self.rear+1) % self.max_size == self.front)
2.1.5 雙端隊列隊頭和隊尾添加元素
添加元素時，需要首先判斷雙端隊列中是否還有空閑空間，然后根據雙端隊列為定長順序雙端隊列或動態順序雙端隊列，添加元素操作稍有不同：
[定長順序雙端隊列的添加元素操作] 如果隊滿，則引發異常：
# 注意隊頭和隊尾修改索引的添加元素的不同順序 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
[動態順序雙端隊列的添加元素操作] 如果雙端隊列滿，則首先申請新空間，然后再執行添加操作：
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
與動態順序隊列類似，我們同樣需要考慮復制之后的索引，否則可能出現存在不能用的空閑空間：
添加元素的時間復雜度為O(1)。雖然當動態順序雙端隊列滿時，原雙端隊列中的元素需要首先復制到新雙端隊列中，然后添加新元素，但參考《順序表及其操作實現》中順序表追加操作的介紹，由于 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 鏈雙端隊列的實現
雙端隊列的另一種存儲表示方式是使用鏈式存儲結構，因此也常稱為鏈雙端隊列，其中 addfront 操作和 addrear 操作分別是通過在鏈表頭部和尾部插入元素來實現的，而 removefront 操作和 removerear 操作分別是通過從頭部和尾部刪除結點來實現的。為了降低在尾部刪除結點的時間復雜度，接下來基于雙向鏈表實現雙端隊列。
2.2.1 雙端隊列結點
雙端隊列的結點實現與雙向鏈表并無差別：
class Node: def __init__(self, data=None): self.data = data self.next = None def __str__(self): return str(self.data)
2.2.2 雙端隊列的初始化
雙端隊列的初始化函數中，使其隊頭指針 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 判雙端隊列空
根據雙端隊列的長度可以很容易的判斷其是否為空雙端隊列：
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 雙端隊列的不同實現對比
雙端隊列的不同實現對比與棧的不同實現類似，可以參考《棧及其操作實現》。
3. 雙端隊列應用
接下來，我們首先測試上述實現的雙端隊列，以驗證操作的有效性，然后利用實現的基本操作來解決實際算法問題。
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 利用雙端隊列基本操作實現復雜算法
[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教程
