資訊專欄INFORMATION COLUMN
摘要：在隊(duì)尾添加入一個(gè)元素，參數(shù)是數(shù)據(jù)項(xiàng)，無返回值。刪除隊(duì)首的元素，不需要參數(shù)，返回值是被刪除的元素，隊(duì)列本身有變化。列表用于隨機(jī)訪問和定長數(shù)據(jù)的操作，包括切片，而雙端隊(duì)列適用于在兩端壓入或彈出元素，索引但不包括切片的效率可能低于列表。
雙端隊(duì)列（Deque），是一種類似于隊(duì)列的元素的有序集合。它擁有兩端，隊(duì)首和隊(duì)尾，并且元素保持在當(dāng)前的位置。雙端隊(duì)列的一個(gè)不同點(diǎn)就是，添加和刪除元素的位置不受限制。新元素可以在隊(duì)首或者隊(duì)尾添加。同樣地，雙端隊(duì)列中的元素可以從兩端彈出。在某種意義上，這種混合的線性結(jié)構(gòu)同時(shí)具有棧和隊(duì)列的性質(zhì)。
很重要的一點(diǎn)，即使雙端隊(duì)列具有棧和隊(duì)列的特性，但它不會(huì)被強(qiáng)制執(zhí)行的LIFO和FIFO操作。這取決于你做出統(tǒng)一的添加和刪除操作。
雙端隊(duì)列的操作如下：
Deque() 創(chuàng)建一個(gè)空的雙端隊(duì)列，無參數(shù)，返回值是空隊(duì)列。 add_front(item) 在隊(duì)首添加入一個(gè)元素，參數(shù)是數(shù)據(jù)項(xiàng)，無返回值。 add_rear(item) 在隊(duì)尾添加入一個(gè)元素，參數(shù)是數(shù)據(jù)項(xiàng)，無返回值。 remove_front() 刪除隊(duì)首的元素，不需要參數(shù)，返回值是被刪除的元素，隊(duì)列本身有變化。 remove_rear() 刪除隊(duì)尾的元素，不需要參數(shù)，返回值是被刪除的元素，隊(duì)列本身有變化。 is_Empty() 檢測隊(duì)列是否為空。無參數(shù)，返回布爾值。 size() 返回隊(duì)列元素的個(gè)數(shù)。無參數(shù)，返回一個(gè)整數(shù)。
雙端隊(duì)列操作舉例：
| 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 雙端隊(duì)列雙端隊(duì)列支持線程安全，在雙端隊(duì)列的任何一端執(zhí)行添加和刪除操作，它們的內(nèi)存效率幾乎相同（時(shí)間復(fù)雜度為O(1)）。
雖然list也支持類似的操作，但是它對(duì)定長列表的操作表現(xiàn)很不錯(cuò)，而當(dāng)遇到pop(0)和insert(0, v)這樣既改變了列表的長度又改變其元素位置的操作時(shí)，其時(shí)間復(fù)雜度就變?yōu)镺(n)了。
在雙端隊(duì)列中最好不使用切片和索引，你可以用popleft和appendleft方法，雙端隊(duì)列對(duì)這些操作做了優(yōu)化。在兩端的索引訪問時(shí)間復(fù)雜度為O(1)，但是訪問中間元素的時(shí)間復(fù)雜度為O(n)，速度較慢，對(duì)于快速隨機(jī)的訪問，還是用列表代替。
列表用于隨機(jī)訪問和定長數(shù)據(jù)的操作，包括切片，而雙端隊(duì)列適用于在兩端壓入或彈出元素，索引（但不包括切片）的效率可能低于列表。
實(shí)現(xiàn)雙端隊(duì)列：
class Deque:
"""模擬雙端隊(duì)列"""
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())
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/44170.html
摘要：擠掉了堆中實(shí)現(xiàn)了堆排序。你可以用堆排序來查找一個(gè)序列中最大的或者最小的幾個(gè)元素。除了使用堆排序，中還有排序和，這兩個(gè)排序最終生成以列表表示的排序結(jié)果，堆排序也是。 這次我們來說說python中的數(shù)據(jù)結(jié)構(gòu)。當(dāng)然了，不會(huì)講很基礎(chǔ)的內(nèi)容。 用過python的都知道，python有著與其他語言很不一樣的數(shù)據(jù)類型，像什么列表、元組、集合、字典之類。這些數(shù)據(jù)類型造就了python簡單易用同時(shí)又很強(qiáng)...
摘要：原生的也可以從頭部添加和取出對(duì)象就像這樣但是值得注意的是，對(duì)象的這兩種用法的時(shí)間復(fù)雜度是，也就是說隨著元素?cái)?shù)量的增加耗時(shí)呈線性上升。 基本介紹 Python擁有一些內(nèi)置的數(shù)據(jù)類型，比如str, int, list, tuple, dict等， collections模塊在這些內(nèi)置數(shù)據(jù)類型的基礎(chǔ)上，提供了幾個(gè)額外的數(shù)據(jù)類型： namedtuple(): 生成可以使用名字來訪問元素內(nèi)容的...
摘要：除此之外，還有一個(gè)接口，代表一個(gè)雙端隊(duì)列，雙端隊(duì)列可以同時(shí)從兩端刪除添加元素，因此的實(shí)現(xiàn)類既可當(dāng)成隊(duì)列使用，也可當(dāng)成棧使用。相當(dāng)于棧方法將一個(gè)元素進(jìn)該雙端隊(duì)列所表示的棧的棧頂。 Queue用于模擬隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)，隊(duì)列通常是指先進(jìn)先出（FIFO）的容器。隊(duì)列的頭部保存在隊(duì)列中存放時(shí)間最長的元素，隊(duì)列的尾部保存在隊(duì)列中存放時(shí)間最短的元素。新元素插入（offer）到隊(duì)列的尾部，訪問元素（p...
摘要：小鹿題目設(shè)計(jì)實(shí)現(xiàn)雙端隊(duì)列。你的實(shí)現(xiàn)需要支持以下操作構(gòu)造函數(shù)雙端隊(duì)列的大小為。獲得雙端隊(duì)列的最后一個(gè)元素。檢查雙端隊(duì)列是否為空。數(shù)組頭部刪除第一個(gè)數(shù)據(jù)。以上數(shù)組提供的使得更方便的對(duì)數(shù)組進(jìn)行操作和模擬其他數(shù)據(jù)結(jié)構(gòu)的操作，棧隊(duì)列等。 Time：2019/4/15Title: Design Circular DequeDifficulty: MediumAuthor: 小鹿 題目：Desi...
摘要：題目使用棧實(shí)現(xiàn)隊(duì)列的下列操作將一個(gè)元素放入隊(duì)列的尾部。用棧實(shí)現(xiàn)隊(duì)列，可以用兩個(gè)棧完成題解。入隊(duì)列時(shí)用存入節(jié)點(diǎn)，出隊(duì)列時(shí)內(nèi)節(jié)點(diǎn)順序出棧壓入中。這類編程語言就壓根不需要用隊(duì)列實(shí)現(xiàn)?；蛴脳?shí)現(xiàn)隊(duì)列這種問題，因?yàn)闂：完?duì)列本身就必須借助實(shí)現(xiàn)。 題目： 使用棧實(shí)現(xiàn)隊(duì)列的下列操作： push(x) -- 將一個(gè)元素放入隊(duì)列的尾部。 pop() -- 從隊(duì)列首部移除元素。 peek() -- 返回隊(duì)...
閱讀 3063·2023-04-26 00:40
閱讀 2408·2021-09-27 13:47
閱讀 4267·2021-09-07 10:22
閱讀 2974·2021-09-06 15:02
閱讀 3322·2021-09-04 16:45
閱讀 2507·2021-08-11 10:23
閱讀 3612·2021-07-26 23:38
閱讀 2908·2019-08-30 15:54
