久久久久久久视色,久久电影免费精品,中文亚洲欧美乱码在线观看,在线免费播放AV片

<center id="vfaef"><input id="vfaef"><table id="vfaef"></table></input></center>

    <p id="vfaef"><kbd id="vfaef"></kbd></p>

    
    
    <pre id="vfaef"><u id="vfaef"></u></pre>

      <thead id="vfaef"><input id="vfaef"></input></thead>

    1. 站長資訊網
      最全最豐富的資訊網站

      Python數(shù)據(jù)結構與算法學習之雙端隊列

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

      Python數(shù)據(jù)結構與算法學習之雙端隊列

      推薦學習: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) 均允許插入元素和刪除元素。新元素既可以被添加到隊頭, 也可以被添加到隊尾。同理,已有的元素也能從任意一端移除。某種意義上,可以認為雙端隊列是棧和隊列的結合。

      Python數(shù)據(jù)結構與算法學習之雙端隊列

      盡管雙端隊列有棧和隊列的很多特性,但是它并不要求按照這兩種數(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ù)的存儲單元依次存放從雙端隊列頭到雙端隊列尾的元素,同時需要用兩個指針 frontrear 分別指示隊列頭元素和隊列尾元素的位置。初始化空雙端隊列時,front=rear=0,當元素入隊時,rear 加 1,而元素出隊時,front 加 1,同時為了重復利用空閑空間,我們將順序雙端隊列假設尾環(huán)狀空間,最后一個空間和第一個空間視為連續(xù)空間(具體原因參考<順序隊列>):

      Python數(shù)據(jù)結構與算法學習之雙端隊列

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

      2.1.1 雙端隊列的初始化

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

      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 求雙端隊列長度

      由于 frontrear 分別用于記錄隊頭元素和隊尾元素的索引,因此我們可以方便的計算出雙端隊列的長度;同時我們需要考慮雙端隊列為循環(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ù) frontrear 的值可以方便的判斷雙端隊列是否為空:

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

      2.1.4 判雙端隊列滿

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

          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)存在不能用的空閑空間:

      Python數(shù)據(jù)結構與算法學習之雙端隊列

      添加元素的時間復雜度為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)雙端隊列。

      Python數(shù)據(jù)結構與算法學習之雙端隊列

      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 添加元素

      雙端隊列添加元素時,可以在隊尾或隊頭插入新元素,因此需要修改 rearfront 指針,并且同時也要修改結點的 nextprevious 指針;如果添加元素前雙端隊列為空,還需要進行相應處理:

          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,同時也要修改結點的 nextprevious 指針,若出隊元素尾隊中最后一個結點,還需要進行相應處理:

          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教程

      贊(0)
      分享到: 更多 (0)
      網站地圖   滬ICP備18035694號-2    滬公網安備31011702889846號