Python數據結構——雙端隊列

cjie 發布于2019-07-31 10:49 / 3374人閱讀

摘要：在隊尾添加入一個元素，參數是數據項，無返回值。刪除隊首的元素，不需要參數，返回值是被刪除的元素，隊列本身有變化。列表用于隨機訪問和定長數據的操作，包括切片，而雙端隊列適用于在兩端壓入或彈出元素，索引但不包括切片的效率可能低于列表。

雙端隊列（Deque），是一種類似于隊列的元素的有序集合。它擁有兩端，隊首和隊尾，并且元素保持在當前的位置。雙端隊列的一個不同點就是，添加和刪除元素的位置不受限制。新元素可以在隊首或者隊尾添加。同樣地，雙端隊列中的元素可以從兩端彈出。在某種意義上，這種混合的線性結構同時具有棧和隊列的性質。

很重要的一點，即使雙端隊列具有棧和隊列的特性，但它不會被強制執行的LIFO和FIFO操作。這取決于你做出統一的添加和刪除操作。

雙端隊列的操作如下：

Deque()          創建一個空的雙端隊列，無參數，返回值是空隊列。
add_front(item)  在隊首添加入一個元素，參數是數據項，無返回值。
add_rear(item)   在隊尾添加入一個元素，參數是數據項，無返回值。
remove_front()   刪除隊首的元素，不需要參數，返回值是被刪除的元素，隊列本身有變化。
remove_rear()    刪除隊尾的元素，不需要參數，返回值是被刪除的元素，隊列本身有變化。
is_Empty()       檢測隊列是否為空。無參數，返回布爾值。
size()           返回隊列元素的個數。無參數，返回一個整數。

雙端隊列操作舉例：

Deque Operation	Deque Contents	Return Value
d.isEmpty()	[]	True
d.addRear(4)	[4]
d.addRear("dog")	["dog",4,]
d.addFront("cat")	["dog",4,"cat"]
d.addFront(True)	["dog",4,"cat",True]
d.size()	["dog",4,"cat",True]	4
d.isEmpty()	["dog",4,"cat",True]	False
d.addRear(8.4)	[8.4,"dog",4,"cat",True]
d.removeRear()	["dog",4,"cat",True]	8.4
d.removeFront()	["dog",4,"cat"]	True

列表 VS 雙端隊列

雙端隊列支持線程安全，在雙端隊列的任何一端執行添加和刪除操作，它們的內存效率幾乎相同（時間復雜度為O(1)）。

雖然list也支持類似的操作，但是它對定長列表的操作表現很不錯，而當遇到pop(0)和insert(0, v)這樣既改變了列表的長度又改變其元素位置的操作時，其時間復雜度就變為O(n)了。

在雙端隊列中最好不使用切片和索引，你可以用popleft和appendleft方法，雙端隊列對這些操作做了優化。在兩端的索引訪問時間復雜度為O(1)，但是訪問中間元素的時間復雜度為O(n)，速度較慢，對于快速隨機的訪問，還是用列表代替。

列表用于隨機訪問和定長數據的操作，包括切片，而雙端隊列適用于在兩端壓入或彈出元素，索引（但不包括切片）的效率可能低于列表。

實現雙端隊列：

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)

以下是測試代碼：

d=Deque()
print(d.isEmpty())
d.addRear(4)
d.addRear("dog")
d.addFront("cat")
d.addFront(True)
print(d.size())
print(d.isEmpty())
d.addRear(8.4)
print(d.removeRear())
print(d.removeFront())

GPU云服務器云服務器 python隊列 python的隊列 python隊列實現 python多隊列

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/44170.html

Python奇遇記：數據結構窺探

摘要：擠掉了堆中實現了堆排序。你可以用堆排序來查找一個序列中最大的或者最小的幾個元素。除了使用堆排序，中還有排序和，這兩個排序最終生成以列表表示的排序結果，堆排序也是。這次我們來說說python中的數據結構。當然了，不會講很基礎的內容。用過python的都知道，python有著與其他語言很不一樣的數據類型，像什么列表、元組、集合、字典之類。這些數據類型造就了python簡單易用同時又很強...

mrli2016 2019-07-31 11:01 評論0 收藏0
不可不知的python模塊--collections

摘要：原生的也可以從頭部添加和取出對象就像這樣但是值得注意的是，對象的這兩種用法的時間復雜度是，也就是說隨著元素數量的增加耗時呈線性上升。基本介紹 Python擁有一些內置的數據類型，比如str, int, list, tuple, dict等， collections模塊在這些內置數據類型的基礎上，提供了幾個額外的數據類型： namedtuple(): 生成可以使用名字來訪問元素內容的...

韓冰 2019-07-30 16:18 評論0 收藏0
Java 集合 Queue

摘要：除此之外，還有一個接口，代表一個雙端隊列，雙端隊列可以同時從兩端刪除添加元素，因此的實現類既可當成隊列使用，也可當成棧使用。相當于棧方法將一個元素進該雙端隊列所表示的棧的棧頂。 Queue用于模擬隊列這種數據結構，隊列通常是指先進先出（FIFO）的容器。隊列的頭部保存在隊列中存放時間最長的元素，隊列的尾部保存在隊列中存放時間最短的元素。新元素插入（offer）到隊列的尾部，訪問元素（p...

bang590 2019-08-14 17:04 評論0 收藏0
LeetCode 之 JavaScript 解答第641題 —— 設計雙端隊列（Design Cir

摘要：小鹿題目設計實現雙端隊列。你的實現需要支持以下操作構造函數雙端隊列的大小為。獲得雙端隊列的最后一個元素。檢查雙端隊列是否為空。數組頭部刪除第一個數據。以上數組提供的使得更方便的對數組進行操作和模擬其他數據結構的操作，棧隊列等。 Time：2019/4/15Title: Design Circular DequeDifficulty: MediumAuthor: 小鹿題目：Desi...

Freeman 2019-08-23 16:58 評論0 收藏0
LeetCode 232：用棧實現隊列 Implement Queue using Stacks

摘要：題目使用棧實現隊列的下列操作將一個元素放入隊列的尾部。用棧實現隊列，可以用兩個棧完成題解。入隊列時用存入節點，出隊列時內節點順序出棧壓入中。這類編程語言就壓根不需要用隊列實現棧或用棧實現隊列這種問題，因為棧和隊列本身就必須借助實現。題目：使用棧實現隊列的下列操作： push(x) -- 將一個元素放入隊列的尾部。 pop() -- 從隊列首部移除元素。 peek() -- 返回隊...

cloud 2019-08-19 10:26 評論0 收藏0