亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

Python數據結構與算法的雙端隊列詳解

 更新時間:2022年03月09日 16:51:58   作者:姜學遷  
這篇文章主要為大家詳細介紹了Python的雙端隊列,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助

什么是雙端隊列?

雙端隊列是與隊列類似的有序集合。它有一、一兩端,元素在其中保持自己的位置。與隊列不同的是,雙端隊列對在哪一端添加和移除元素沒有任何限制。新元素既可以被添加到前端,也可以被添加到后端。同理,已有的元素也能從任意一端移除。某種意義上,雙端隊列可以是棧和隊列的結合。

在這里插入圖片描述

值得注意的是,盡管雙端隊列有棧和隊列的很多特性,但是它并不要求按照這兩種數據結構分別規(guī)定的LIFO原則和FIFO原則操作元素。具體的排序原則取決于其使用者。

?雙端隊列抽象數據類型由下面的結構和操作定義。如前所述,雙端隊列是元素的有序集合,其任何一端都允許添加或移除元素。雙端隊列支持以下操作:?

  • 創(chuàng)建一個空的雙端隊列。它不需要參數,且會返回一個空的雙端隊列。 Deque()
  • 將一個元素添加到雙端隊列的前端。它接受一個元素作為參數,沒有返回值。 addFront(item)
  • 將一個元素添加到雙端隊列的后端。它接受一個元素作為參數,沒有返回值。 addRear(item)
  • 從雙端隊列的前端移除一個元素。它不需要參數,且會返回一個元素,并修改雙端隊列的內容。 removeFront()
  • 從雙端隊列的后端移除一個元素。它不需要參數,且會返回一個元素, 并修改雙端隊列的內容。 removeRear()
  • 檢查雙端隊列是否為空。它不需要參數,且會返回一個布爾值。 isEmpty()
  • 返回雙端隊列中元素的數目。它不需要參數,且會返回一個整數。 size()

?用Python實現雙端隊列

我們通過創(chuàng)建一個新類來實現雙端隊列抽象數據類型。Python列表再一次提供了 很多簡便的方法來幫助我們構建雙端隊列。在下面的代碼中,我們假設雙端隊列的后端是列表的位置0處(列表的最左端)。

class Deque:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    # 往雙端隊列前端添加元素
    def addFront(self, item):
        self.items.append(item)
    # 往雙端隊列后端添加元素
    def addRear(self, item):
        self.items.insert(0, item)
    # 在前端移除雙端隊列元素
    def removeFront(self):
        return self.items.pop()
    # 在后端移除雙端隊列元素
    def removeRear(self):
        return self.items.pop(0)
    def size(self):
        return len(self.items)
    def look(self):
        print(self.items)

removeFront 使用 pop 方法移除列表中的最后一個元素,removeRear 則使用 pop(0) 方法移除列表中的第一個元素。同理,之所以 addRear 使用 insert 方法,是因為 append 方法只能在列表的最后(最右端)添加元素。?

代碼運行效果如下:

在這里插入圖片描述

運用雙端隊列構建回文檢測器

我們現在運用雙端隊列解決一個非常有趣的經典問題:回文問題。回文是指從前往后讀和從后往前讀都一樣的字符串,例如 sos、radar、toot、madam 等等。我們將構建一個程序,它接受一個字符串并且檢測其是否為回文。?

該問題的解決方案是使用一個雙端隊列來存儲字符串中的字符。按照從左往右的順序將字符串中的字符添加到雙端隊列的后端或前端。此時,該雙端隊列類似于一個普通的隊列。?

由于可以從前后兩端移除元素,因此我們能夠比較兩個元素,并且只有在二者相等時才繼續(xù)。如果一直匹配第一個和最后一個元素,最終會處理完所有的字符(如果字符數是偶數),或者剩下只有一個元素的雙端隊列(如果字符數是奇數)。任意一種結果都表明輸入字符串是回文。?

回文檢測器代碼如下:

class Deque:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    def addFront(self, item):
        self.items.append(item)
    def addRear(self, item):
        self.items.insert(0, item)
    def removeFront(self):
        return self.items.pop()
    def removeRear(self):
        return self.items.pop(0)
    def size(self):
        return len(self.items)

def palchecker(aString):
    chardeque = Deque()
    for ch in aString:
        chardeque.addFront(ch)
    stillEqual = True
    while chardeque.size() > 1 and stillEqual:
        first = chardeque.removeFront()
        last = chardeque.removeRear()
        if first != last:
            stillEqual = False
    return stillEqual

總結

本篇文章就到這里了,希望能夠給你帶來幫助,也希望您能夠多多關注腳本之家的更多內容!   

相關文章

  • 幫你快速上手Jenkins并實現自動化部署

    幫你快速上手Jenkins并實現自動化部署

    在未學習Jenkins之前,只是對Jenkins有一個比較模糊的理解,即Jenkins是一個自動化構建項目發(fā)布的工具,可以實現代碼->github或者gitlab庫->jenkins自動部署->訪問的整體的過程,而無需人為重新打包,今天就帶大家詳細了解一下,幫你快速上手Jenkins,需要的朋友可以參考下
    2021-06-06
  • python實現簡單http服務器功能

    python實現簡單http服務器功能

    這篇文章主要為大家詳細介紹了python實現簡單http服務器功能,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-09-09
  • Python時間戳與時間字符串互相轉換實例代碼

    Python時間戳與時間字符串互相轉換實例代碼

    這篇文章主要介紹了Python時間戳與時間字符串互相轉換實例代碼,大家參考使用
    2013-11-11
  • python如何利用traceback獲取詳細的異常信息

    python如何利用traceback獲取詳細的異常信息

    異常信息的獲取對于程序的調試非常重要,可以有助于快速定位有錯誤程序語句的位置。這篇文章主要給大家介紹了關于python如何利用traceback獲取詳細的異常信息的相關資料,需要的朋友可以參考下
    2021-06-06
  • 2020年10款優(yōu)秀的Python第三方庫,看看有你中意的嗎?

    2020年10款優(yōu)秀的Python第三方庫,看看有你中意的嗎?

    2020已經過去,在過去的一年里,又有非常多優(yōu)秀的Python庫涌現出來。相對于numpy、TensorFlow、pandas這些已經經過多年維護、迭代,對于大多數Python開發(fā)者耳熟能詳的庫不同。
    2021-01-01
  • python如何使用騰訊云發(fā)送短信

    python如何使用騰訊云發(fā)送短信

    這篇文章主要介紹了python如何使用騰訊云發(fā)送短信,幫助大家更好的理解和使用python,感興趣的朋友可以了解下
    2020-09-09
  • 如何在Python中將字符串轉換為數組詳解

    如何在Python中將字符串轉換為數組詳解

    最近在用Python,做一個小腳本,有個操作就是要把內容換成數組對象再進行相關操作,下面這篇文章主要給大家介紹了關于如何在Python中將字符串轉換為數組的相關資料,需要的朋友可以參考下
    2022-12-12
  • python字符串加密解密的三種方法分享(base64 win32com)

    python字符串加密解密的三種方法分享(base64 win32com)

    這篇文章主要介紹了python字符串加密解密的三種方法,包括用base64、使用win32com.client、自己寫的加密解密算法三種方法,大家參考使用吧
    2014-01-01
  • python使用pip安裝SciPy、SymPy、matplotlib教程

    python使用pip安裝SciPy、SymPy、matplotlib教程

    今天小編大家分享一篇python使用pip安裝SciPy、SymPy、matplotlib教程,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-11-11
  • 用Python實現讀寫鎖的示例代碼

    用Python實現讀寫鎖的示例代碼

    這篇文章主要介紹了用Python實現讀寫鎖的示例代碼,小編覺得挺不錯的,現在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2018-11-11

最新評論