Python常用隊列全面詳細梳理
一，隊列
和棧一樣，隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作。隊列是一種操作受限制的線性表，進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。
二，常見隊列
1，F(xiàn)IFO隊列
基本FIFO隊列 先進先出 FIFO即First in First Out,先進先出。
調(diào)用queue.Queue
from queue import Queue fifo_queue = Queue() fifo_queue.put(1) # 隊尾插入新元素 fifo_queue.put(2) fifo_queue.put(3) print(fifo_queue.queue) print(fifo_queue.get()) # 隊頭取出元素 print(fifo_queue.queue)
鏈表實現(xiàn)
class LNode(object):
def __init__(self, item, next_=None):
self.item = item
self.next = next_
class FIFOQueue(object):
def __init__(self):
"""初始化"""
self.head = None
self.rear = None
def is_empty(self):
"""判斷是否為空"""
return self.head is None
def size(self):
"""獲取隊列長度"""
cur = self.head
count = 0
while True:
count += 1
if cur == self.rear:
break
cur = cur.next
return count
def travel(self):
"""遍歷隊列"""
if self.is_empty():
print('queue is empty')
return
else:
cur = self.head
while True:
print(cur.item, end='')
if cur.next:
print(',', end='')
if cur == self.rear:
break
cur = cur.next
print('')
def push(self, val):
"""隊尾插入新元素"""
p = LNode(val)
if self.is_empty():
self.head = p
self.rear = p
else:
self.rear.next = p
self.rear = self.rear.next
def get(self):
"""獲取隊頭元素"""
if self.is_empty():
print('queue is empty')
return
else:
e = self.head.item
self.head = self.head.next
return e
if __name__ == '__main__':
FIFOQueue = FIFOQueue()
FIFOQueue.push(1)
FIFOQueue.push(2)
FIFOQueue.push(3)
FIFOQueue.push(4)
FIFOQueue.travel() # 1,2,3,4
print(FIFOQueue.get()) # 1
print(FIFOQueue.get()) # 2
FIFOQueue.travel() # 3,4
list實現(xiàn)
# list 實現(xiàn)
class FIFOQueue(object):
def __init__(self):
self.queue = list()
def size(self):
return len(self.queue)
def travel(self):
print(self.queue)
def push(self, val):
self.queue.append(val)
def get(self):
return self.queue.pop(0)
if __name__ == '__main__':
FIFOQueue = FIFOQueue()
FIFOQueue.push(1)
FIFOQueue.push(2)
FIFOQueue.push(3)
FIFOQueue.push(4)
FIFOQueue.travel() # 1,2,3,4
print(FIFOQueue.get()) # 1
print(FIFOQueue.get()) # 2
FIFOQueue.travel() # 3,4
2，LIFO隊列
LIFO即Last in First Out,后進先出。與棧的類似，在隊尾進行插入和刪除操作。
調(diào)用queue.LifoQueue
from queue import LifoQueue lifo_queue = LifoQueue() lifo_queue.put(1) # 隊尾插入新元素 lifo_queue.put(2) lifo_queue.put(3) print(lifo_queue.queue) print(lifo_queue.get()) # 隊尾取出元素 print(lifo_queue.queue)
鏈表實現(xiàn)
將鏈表頭部作為隊列尾部，在鏈表頭部進行插入和刪除操作。
class LNode(object):
def __init__(self, item, next_=None):
self.item = item
self.next = next_
class LIFOQueue(object):
def __init__(self):
"""初始化"""
self.head = None
def is_empty(self):
"""判斷是否為空"""
return self.head is None
def size(self):
"""獲取隊列長度"""
cur = self.head
count = 0
while cur:
count += 1
cur = cur.next
return count
def travel(self):
"""遍歷隊列"""
travel_list = []
cur = self.head
while cur:
travel_list.append(cur.item)
cur = cur.next
travel_list.reverse()
print(travel_list)
def push(self, val):
"""頭部插入"""
self.head = LNode(val, self.head)
def get(self):
"""獲取隊頭元素"""
if self.is_empty():
print('queue is empty')
return
else:
e = self.head.item
self.head = self.head.next
return e
if __name__ == '__main__':
LIFOQueue = LIFOQueue()
LIFOQueue.push(1)
LIFOQueue.push(2)
LIFOQueue.push(3)
LIFOQueue.push(4)
LIFOQueue.travel() # 1,2,3,4
print(LIFOQueue.get()) # 4
print(LIFOQueue.get()) # 3
LIFOQueue.travel() # 1,2
List實現(xiàn)
# list 實現(xiàn)
class LIFOQueue(object):
def __init__(self):
self.queue = list()
def size(self):
return len(self.queue)
def travel(self):
print(self.queue)
def push(self, val):
self.queue.append(val)
def get(self):
return self.queue.pop()
if __name__ == '__main__':
LIFOQueue = LIFOQueue()
LIFOQueue.push(1)
LIFOQueue.push(2)
LIFOQueue.push(3)
LIFOQueue.push(4)
LIFOQueue.travel() # 1,2,3,4
print(LIFOQueue.get()) # 4
print(LIFOQueue.get()) # 3
LIFOQueue.travel() # 1,2
3，雙向隊列
雙端隊列（deque，全名 double-ended queue），是一種具有隊列和棧的性質(zhì)的數(shù)據(jù)結(jié)構(gòu)。雙端隊列中的元素可以從兩端彈出，其限定插入和刪除操作在表的兩端進行。雙端隊列可以在隊列任意一端入隊和出隊。
調(diào)用collections .deque
collections 是 python 內(nèi)建的一個集合模塊，里面封裝了許多集合類，其中隊列相關(guān)的集合只有一個：deque。
deque 是雙邊隊列（double-ended queue），具有隊列和棧的性質(zhì)，在 list 的基礎(chǔ)上增加了移動、旋轉(zhuǎn)和增刪等。
deque(maxlen=3)，通過maxlen參數(shù)，可以創(chuàng)建固定長度的隊列，當(dāng)新元素加入隊列且隊列已滿，會自動從另一端移除首個元素。不指定maxlen，得到無界限的隊列。
from collections import deque
d = deque([])
d.append('a') # 在最右邊添加一個元素，此時 d=deque('a')
print(d)
d.appendleft('b') # 在最左邊添加一個元素，此時 d=deque(['b', 'a'])
print(d)
d.extend(['c', 'd']) # 在最右邊添加所有元素，此時 d=deque(['b', 'a', 'c', 'd'])
print(d)
d.extendleft(['e', 'f']) # 在最左邊添加所有元素，此時 d=deque(['f', 'e', 'b', 'a', 'c', 'd'])
print(d)
d.pop() # 將最右邊的元素取出，返回 'd'，此時 d=deque(['f', 'e', 'b', 'a', 'c'])
print(d)
d.popleft() # 將最左邊的元素取出，返回 'f'，此時 d=deque(['e', 'b', 'a', 'c'])
print(d)
d.rotate(-2) # 向左旋轉(zhuǎn)兩個位置（正數(shù)則向右旋轉(zhuǎn)），此時 d=deque(['a', 'c', 'e', 'b'])
print(d)
雙向鏈表實現(xiàn)
class DLNode(object):
def __init__(self, item, prior_=None, next_=None):
self.item = item
self.prior = prior_
self.next = next_
class DQueue(object):
def __init__(self):
self.head = None # 頭指針
self.rear = None # 尾制造
def is_empty(self):
return self.head is None
def length(self):
if self.is_empty():
print('queue is empty')
return
else:
cur = self.head
count = 0
while True:
count += 1
if cur == self.rear:
break
cur = cur.next
return count
def travel(self):
"""遍歷隊列"""
if self.is_empty():
print('queue is empty')
return
else:
cur = self.head
while True:
print(cur.item, end='')
if cur.next:
print(',', end='')
if cur == self.rear:
break
cur = cur.next
print('')
def push_rear(self, val):
"""隊尾插入元素"""
p = DLNode(val)
if self.is_empty():
self.head = p
self.rear = p
else:
self.rear.next = p
p.prior = self.rear
self.rear = self.rear.next
def push_head(self, val):
"""隊頭插入元素"""
p = DLNode(val)
if self.is_empty():
self.head = p
self.rear = p
else:
p.next = self.head
self.head.prior = p
self.head = p
def pop_rear(self):
"""獲取隊尾元素"""
if self.is_empty():
print('queue is empty')
return
else:
p = self.rear
self.rear = self.rear.prior
self.rear.next = None
return p.item
def pop_head(self):
"""獲取隊頭元素"""
if self.is_empty():
print('queue is empty')
return
else:
e = self.head.item
self.head = self.head.next
return e
if __name__ == '__main__':
DQueue = DQueue()
DQueue.push_head(1)
DQueue.push_head(2)
DQueue.push_head(3)
DQueue.travel() # 3,2,1
DQueue.push_rear('a')
DQueue.push_rear('b')
DQueue.travel() # 3,2,1,a,b
print(DQueue.pop_head()) # 3
print(DQueue.pop_rear()) # b
print(DQueue.pop_rear()) # a
DQueue.travel() # 2,1list實現(xiàn)
class DQueue:
"""雙端隊列"""
def __init__(self):
self.queue = []
def push_head(self, val):
"""從隊頭加入一個元素"""
self.queue.insert(0, val)
def push_rear(self, val):
"""從隊尾加入一個元素"""
self.queue.append(val)
def pop_head(self):
"""從隊頭刪除一個元素"""
return self.queue.pop(0)
def pop_rear(self):
"""從隊尾刪除一個元素"""
return self.queue.pop()
def is_empty(self):
"""是否為空"""
return self.queue == []
def size(self):
"""隊列長度"""
return len(self.queue)
def travel(self):
print(self.queue)
if __name__ == "__main__":
DQueue = DQueue()
DQueue.push_head(1)
DQueue.push_head(2)
DQueue.push_head(3)
DQueue.travel() # [3, 2, 1]
DQueue.push_rear('a')
DQueue.push_rear('b')
DQueue.travel() # [3, 2, 1, 'a', 'b']
print(DQueue.pop_head()) # 3
print(DQueue.pop_rear()) # b
print(DQueue.pop_rear()) # a
DQueue.travel() # [2, 1]4，優(yōu)先級隊列
優(yōu)先級隊列是一種容器型數(shù)據(jù)結(jié)構(gòu)，它能管理一隊記錄，并按照排序字段（例如一個數(shù)字類型的權(quán)重值）為其排序。由于是排序的，所以在優(yōu)先級隊列中你可以快速獲取到最大的和最小的值。
可以認為優(yōu)先級隊列是一種修改過的普通隊列：普通隊列依據(jù)記錄插入的時間來獲取下一個記錄，而優(yōu)先級隊列依據(jù)優(yōu)先級來獲取下一個記錄，優(yōu)先級取決于排序字段的值。
優(yōu)先級隊列常用來解決調(diào)度問題，比如給緊急的任務(wù)更高的優(yōu)先級。以操作系統(tǒng)的任務(wù)調(diào)度為例：高優(yōu)先級的任務(wù)（比如實時游戲）應(yīng)該先于低優(yōu)先級的任務(wù)（比如后臺下載軟件更新）執(zhí)行。
調(diào)用queue.PriorityQueue
在 Python 中，內(nèi)置的標(biāo)準(zhǔn)庫提供了兩種實現(xiàn)優(yōu)先隊列的數(shù)據(jù)結(jié)構(gòu)，分別是 heapq 模塊和 PriorityQueue 模塊，
最小優(yōu)先級隊列
更小的值具有更高的優(yōu)先級，也就是會被最先輸出
# 優(yōu)先級隊列
from queue import PriorityQueue as PQ
Pqueue = PQ()
Pqueue.put((1, 'a'))
Pqueue.put((3, 'c'))
Pqueue.put((2, 'b'))
Pqueue.put((2, 'd'))
Pqueue.put((5, 'e'))
print(Pqueue.queue) # [(1, 'a'), (2, 'd'), (2, 'b'), (3, 'c'), (5, 'e')]
while not Pqueue.empty():
print(Pqueue.get())
# (1, 'a')
# (2, 'b')
# (2, 'd')
# (3, 'c')
# (5, 'e')
最大優(yōu)先級隊列
更大的值具有更高的優(yōu)先級，也就是會被最先輸出。
from queue import PriorityQueue as PQ
Pqueue = PQ()
Pqueue.put((-1, 'a'))
Pqueue.put((-3, 'c'))
Pqueue.put((-2, 'b'))
Pqueue.put((-2, 'd'))
Pqueue.put((-5, 'e'))
print(Pqueue.queue) # [(-5, 'e'), (-3, 'c'), (-2, 'b'), (-1, 'a'), (-2, 'd')]
while not Pqueue.empty():
print(Pqueue.get())
# (-5, 'e')
# (-3, 'c')
# (-2, 'b')
# (-2, 'd') 當(dāng)兩個對象的優(yōu)先級一致時，按照插入順序排列
# (-1, 'a')
基于 heapq 實現(xiàn)
heapq 涉及到另一種數(shù)據(jù)結(jié)構(gòu)“堆”，用heapq 實現(xiàn)優(yōu)先級隊列，也是基于最小堆，最大堆實現(xiàn)，這些在后面“堆”再一起研究下。
import heapq
class PriorityQueue(object):
def __init__(self):
self._queue = []
# self._index = 0
def push(self, item, priority):
"""
隊列由 (priority, index, item) 形式組成
priority 默認是最小優(yōu)先級，增加 "-" 實現(xiàn)最大優(yōu)先級，
index 是為了當(dāng)兩個對象的優(yōu)先級一致時，按照插入順序排列
"""
heapq.heappush(self._queue, (-priority, item))
# self._index += 1
def pop(self):
"""
彈出優(yōu)先級最高的對象
"""
return heapq.heappop(self._queue)[-1]
def qsize(self):
return len(self._queue)
def empty(self):
return True if not self._queue else False
if __name__ == '__main__':
PQueue = PriorityQueue()
PQueue.push('a', 1)
PQueue.push('c', 3)
PQueue.push('b', 2)
PQueue.push('d', 2)
PQueue.push('e', 5)
PQueue.push('f', 1)
while not PQueue.empty():
print(PQueue.pop()) # e c b d a f
5，循環(huán)隊列
在之前實現(xiàn)的隊列時，都為固定隊列長度，都創(chuàng)建無限隊列，當(dāng)隊列空間有限時，插入和刪除元素會有問題呢？
假定用長度為6的數(shù)組，表示長度為6的隊列。隊列中已經(jīng)有三個元素a1、a2、a3。
如果新插入元素，只需要在隊尾插入便可，在下標(biāo)3的位置插入新元素a4，入隊列的時間復(fù)雜度O(1)。
如果刪除元素，當(dāng)a1出隊列后，其后面的a2、a3、a4則需要向前移動一個位置，就好日常排隊時，當(dāng)前面人離開，后面的隊伍都往前移動一步，所以出隊列的時間復(fù)雜度為O(n)。
這種效率顯然是不可以接受的，那么能不能不讓所有成員都往前挪一位呢？
所以在原來的基礎(chǔ)上，加入兩個變量front、rear分別存儲隊頭和隊尾的下標(biāo)。
此時front =0 ,rear = 3。
當(dāng)有新元素插入隊尾時，rear = rear+1。
當(dāng)有元素出隊列時，front = front + 1
這樣一來，似乎不將后面所有成員往前挪，只需維護一下front的指向（front += 1）就可以保證隊首，但是，當(dāng)遇到下面這情況時，就存在“假溢出”的情況。
將a2、a3都出隊列，此時front = 3，在將a6插入隊列，此時rear = 6。
此時，隊列長度為3，隊列未滿，再將a7插入隊列時，就會報錯數(shù)組越界，但是此時數(shù)組空間未滿，前面0、1、2都空著，這種現(xiàn)象稱為“假溢出”。
雖然這種方法不用移動元素，但是卻造成空間上的浪費?？梢钥闯龃藭r數(shù)組是還有空間去容納新元素a7的，因此我們需要將前面浪費的空間重新利用起來，減少空間的浪費，這就是循環(huán)隊列的意義所在了。
1.循環(huán)隊列包括兩個指針(其實就是兩個整數(shù)型變量，因為在這里有指示作用，所以這里理解為指針)， front 指針指向隊頭元素， rear 指針指向隊尾元素的下一個位置。
2.rear和front互相追趕著，這個追趕過程就是隊列添加和刪除的過程，如果rear追到head說明隊列滿了，如果front追到rear說明隊列為空。
3,rear和front位置的移動，關(guān)鍵在于% (取模運算)，這樣就防止rear和front 超過maxsize。
網(wǎng)上最?？吹降膶崿F(xiàn)代碼
class SqQueue(object):
def __init__(self, maxsize):
self.queue = [None] * maxsize
self.maxsize = maxsize
self.front = 0
self.rear = 0
# 返回當(dāng)前隊列的長度
def QueueLength(self):
return (self.rear - self.front + self.maxsize) % self.maxsize
# 如果隊列未滿，則在隊尾插入元素，時間復(fù)雜度O(1)
def EnQueue(self, data):
if (self.rear + 1) % self.maxsize == self.front:
print("The queue is full!")
else:
self.queue[self.rear] = data
# self.queue.insert(self.rear,data)
self.rear = (self.rear + 1) % self.maxsize
# 如果隊列不為空，則刪除隊頭的元素,時間復(fù)雜度O(1)
def DeQueue(self):
if self.rear == self.front:
print("The queue is empty!")
else:
data = self.queue[self.front]
self.queue[self.front] = None
self.front = (self.front + 1) % self.maxsize
return data
# 輸出隊列中的元素
def ShowQueue(self):
for i in range(self.maxsize):
print(self.queue[i],end=',')
print(' ')
這有個bug，由于 self.rear = (self.rear + 1) % self.maxsize 這會造成一個空間的浪費??！ 可以運行下代碼看看。
所以自己寫了一段代碼，直接使用現(xiàn)有元素個數(shù)cnt 與 maxsize 比較來判斷是否為空？是否已滿？
class CycleQueue(object):
def __init__(self, maxsize):
self.queue = [None] * maxsize
self.maxsize = maxsize
self.front = 0
self.rear = 0
self.cnt = 0
def is_empty(self):
return self.cnt == 0
def is_full(self):
return self.cnt == self.maxsize
def push(self, val):
if self.is_full():
print("The queue is full!")
return
if self.is_empty():
self.queue[self.rear] = val
self.cnt += 1
else:
self.rear = (self.rear + 1) % self.maxsize
self.queue[self.rear] = val
self.cnt += 1
def pop(self):
if self.is_empty():
print("The queue is empty!")
return
val = self.queue[self.front]
self.queue[self.front] = None
self.front = (self.front + 1) % self.maxsize
self.cnt -= 1
return val
def travel(self):
travel_list = [self.queue[(self.front + i) % self.maxsize] for i in range(self.cnt)]
print(travel_list)
def size(self):
return self.cnt
if __name__ == '__main__':
CycleQueue = CycleQueue(6)
CycleQueue.push('a1')
CycleQueue.push('a2')
CycleQueue.push('a3')
CycleQueue.push('a4')
CycleQueue.push('a5')
CycleQueue.travel() # ['a1', 'a2', 'a3', 'a4', 'a5']
CycleQueue.push('a6')
CycleQueue.travel() # ['a1', 'a2', 'a3', 'a4', 'a5', 'a6']
CycleQueue.pop()
CycleQueue.push('a7')
CycleQueue.travel() # ['a2', 'a3', 'a4', 'a5', 'a6', 'a7']
CycleQueue.pop()
CycleQueue.pop()
CycleQueue.push('a8')
CycleQueue.travel() # ['a4', 'a5', 'a6', 'a7', 'a8']
到此這篇關(guān)于Python常用隊列全面詳細梳理的文章就介紹到這了,更多相關(guān)Python常用隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Python學(xué)習(xí)之configparser模塊的使用詳解
ConfigParser是用來讀取配置文件的包。這篇文章主要通過一些簡單的實例帶大家了解一下ConfigParser模塊的具體使用，感興趣的小伙伴跟隨小編一起了解一下2023-01-01
下面小編就為大家分享一篇python?接口返回的json字符串實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-03-03
Python?Pandas教程之series 上的轉(zhuǎn)換操作
這篇文章主要介紹了Python?Pandas教程之series上的轉(zhuǎn)換操作，文章通過圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-09-09
這篇文章主要介紹了Matplotlib實現(xiàn)各種條形圖繪制，文章通過利用 plt.bar 方法實現(xiàn)各種條形圖繪制，內(nèi)容詳細具有一定的參考價值，需要的小伙伴可以參考一下2022-03-03
本章中我們將講述Python的對象類型，包括數(shù)字、整型、布爾型、長整形、浮點型、復(fù)數(shù)型、字符串、列表、元組、字典等。2014-10-10
python3 字符串/列表/元組（str/list/tuple）相互轉(zhuǎn)換方法及join()函數(shù)的使用
這篇文章主要介紹了python3 字符串/列表/元組（str/list/tuple）相互轉(zhuǎn)換方法及join()函數(shù)的使用 ,非常不錯，具有一定的參考借鑒價值，需要的朋友可以參考下2019-04-04
這篇文章主要介紹了剖析Python的Twisted框架的核心特性,包括Twisted框架中reacter與Deferred等的關(guān)鍵用法,需要的朋友可以參考下2016-05-05
python簡單幾步獲取各種DOS命令顯示的內(nèi)容詳解流程
你會用python獲取各種DOS命令顯示的內(nèi)容核心嗎？說的可不是返回值，是用system()函數(shù)調(diào)用windows操作系統(tǒng)的DOS命令來做點事情，需要的朋友可以參考下2021-10-10
淺談python中的__init__、__new__和__call__方法
這篇文章主要給大家介紹了關(guān)于python中__init__、__new__和__call__方法的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家具有一定的參考學(xué)習(xí)價值，需要的朋友可以參考學(xué)習(xí)，下面來跟著小編一起看看吧。2017-07-07
Python 序列化 pickle/cPickle模塊使用介紹
這篇文章主要介紹了Python 序列化 pickle/cPickle模塊使用介紹,需要的朋友可以參考下2014-11-11