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資料結構與演演算法學習之雙端佇列的詳細內容，更多請關注TW511.COM其它相關文章！