本篇文章為大家展示了Python中棧、隊(duì)列與優(yōu)先級隊(duì)列的實(shí)現(xiàn)，內(nèi)容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細(xì)介紹希望你能有所收獲。

網(wǎng)站建設(shè)哪家好，找創(chuàng)新互聯(lián)！專注于網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、成都小程序開發(fā)、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了尼木免費(fèi)建站歡迎大家使用！

1、list

list是Python內(nèi)置的列表數(shù)據(jù)結(jié)構(gòu)，它支持棧的特性，有入棧和出棧操作。只不過用list實(shí)現(xiàn)棧性能不是特別好。

因?yàn)閘ist內(nèi)部是通過一個(gè)動(dòng)態(tài)擴(kuò)容的數(shù)組來實(shí)現(xiàn)的。當(dāng)增減元素時(shí)就有可能會觸發(fā)擴(kuò)容操作。如果在list的頭部增減元素，也會移動(dòng)整個(gè)列表。

如要使用list來實(shí)現(xiàn)一個(gè)棧的話，可以使用list的append()(入棧)、pop()(出棧)方法。

>>> s = []
>>> s.append('one')
>>> s.append('two')
>>> s.append(3)
>>> s
['one', 'two', 3]
>>> s.pop()
3
>>> s.pop()
'two'
>>> s.pop()
'one'
>>> s.pop()
IndexError: pop from empty list

2、collections.deque

deque類是一種雙端隊(duì)列。在Python中它就是一個(gè)雙向列表，可以以常用時(shí)間在兩端執(zhí)行添加和刪除元素的操作，非常高效，所以它既可以實(shí)現(xiàn)棧也可以實(shí)現(xiàn)隊(duì)列。

如果要在Python實(shí)現(xiàn)一個(gè)棧，那么應(yīng)該優(yōu)先選擇deque，而不是list。

deque的入棧和出棧方法也分別是append()和pop()。

>>> from collections import deque
>>> s = deque()
>>> s.append('eat')
>>> s.append('sleep')
>>> s.append('code')
>>> s
deque(['eat', 'sleep', 'code'])
>>> s.pop()
'code'
>>> s.pop()
'sleep'
>>> s.pop()
'eat'
>>> s.pop()
IndexError: pop from an empty deque

3、queue.LifoQueue

顧名思義，這個(gè)就是一個(gè)棧。不過它是線程安全的，如果要在并發(fā)的環(huán)境下使用，那么就可以選擇使用LifoQueue。

它入棧和出棧操作是使用put()和get()，其中g(shù)et()在LifoQueue為空時(shí)會阻塞。

>>> from queue import LifoQueue
>>> s = LifoQueue()
>>> s.put('eat')
>>> s.put('sleep')
>>> s.put('code')
>>> s
<queue.LifoQueue object at 0x109dcfe48>
>>> s.get()
'code'
>>> s.get()
'sleep'
>>> s.get()
'eat'
>>> s.get()
# 阻塞并一直等待直到棧不為空

0x01 隊(duì)列(Queue)

隊(duì)列是一種FIFO(先進(jìn)先出)的數(shù)據(jù)結(jié)構(gòu)。它有入隊(duì)(enqueue)、出隊(duì)(dequeue)兩種操作，而且也是常數(shù)時(shí)間的操作。
在Python中可以使用哪些數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)一個(gè)隊(duì)列呢？

1、list

list可以實(shí)現(xiàn)一個(gè)隊(duì)列，但它的入隊(duì)、出隊(duì)操作就不是非常高效了。因?yàn)閘ist是一個(gè)動(dòng)態(tài)列表，在隊(duì)列的頭部執(zhí)行出隊(duì)操作時(shí)，會發(fā)生整個(gè)元素的移動(dòng)。

使用list來實(shí)現(xiàn)一個(gè)隊(duì)列時(shí)，用append()執(zhí)行入隊(duì)操作，使用pop(0)方法在隊(duì)列頭部執(zhí)行出隊(duì)操作。由于在list的第一個(gè)元素進(jìn)行操作，所以后續(xù)的元素都會向前移動(dòng)一位。因此用list來實(shí)現(xiàn)隊(duì)列是不推薦的。

>>> q = []
>>> q.append('1')
>>> q.append('2')
>>> q.append('three')

>>> q.pop(0)
'1'
>>> q.pop(0)
'2'
>>> q.pop(0)
'three'
>>> q.pop(0)
IndexError: pop from empty list

2、collections.deque

從上文我們已經(jīng)知道deque是一個(gè)雙向列表，它可以在列表兩端以常數(shù)時(shí)間進(jìn)行添加刪除操作。所以用deque來實(shí)現(xiàn)一個(gè)隊(duì)列是非常高效的。

deque入隊(duì)操作使用append()方法，出隊(duì)操作使用popleft()方法。

>>> from collections import deque
>>> q = deque()
>>> q.append('eat')
>>> q.append('sleep')
>>> q.append('code')
>>> q
deque(['eat', 'sleep', 'code'])
# 使用popleft出隊(duì)
>>> q.popleft()
'eat'
>>> q.popleft()
'sleep'
>>> q.popleft()
'code'
>>> q.popleft()
IndexError: pop from an empty deque

3、queue.Queue

同樣地，如果要在并發(fā)環(huán)境下使用隊(duì)列，那么選擇線程安全的queue.Queue。

與LifoQueue類似，入隊(duì)和出隊(duì)操作分別是put()和get()方法，get()在隊(duì)列為空時(shí)會一直阻塞直到有元素入隊(duì)。

>>> from queue import Queue
>>> q = Queue()
>>> q.put('eat')
>>> q.put('sleep')
>>> q.put('code')
>>> q
<queue.Queue object at 0x110564780>
>>> q.get()
'eat'
>>> q.get()
'sleep'
>>> q.get()
'code'
# 隊(duì)列為空不要執(zhí)行等待
>>> q.get_nowait()
_queue.Empty
>>> q.put('111')
>>> q.get_nowait()
'111'
>>> q.get()
# 隊(duì)列為空時(shí)，會一直阻塞直到隊(duì)列不為空

4、multiprocessing.Queue

多進(jìn)程版本的隊(duì)列。如果要在多進(jìn)程環(huán)境下使用隊(duì)列，那么應(yīng)該選擇multiprocessing.Queue。

同樣地，它的入隊(duì)出隊(duì)操作分別是put()和get()。get()方法在隊(duì)列為空，會一直阻塞直到隊(duì)列不為空。

>>> from multiprocessing import Queue
>>> q = Queue()
>>> q.put('eat')
>>> q.put('sleep')
>>> q.put('code')
>>> q
<multiprocessing.queues.Queue object at 0x110567ef0>
>>> q.get()
'eat'
>>> q.get()
'sleep'
>>> q.get()
'code'
>>> q.get_nowait()
_queue.Empty
>>> q.get()
# 隊(duì)列為空時(shí)，會一直阻塞直到隊(duì)列不為空

0x02 優(yōu)先級隊(duì)列(PriorityQueue)

一個(gè)近乎排序的序列里可以使用優(yōu)先級隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)，它能高效獲取大或最小的元素。

在調(diào)度問題的場景中經(jīng)常會用到優(yōu)先級隊(duì)列。它主要有獲取大值或最小值的操作和入隊(duì)操作。

1、list

使用list可以實(shí)現(xiàn)一個(gè)優(yōu)先級隊(duì)列，但它并不高效。因?yàn)楫?dāng)要獲取最值時(shí)需要排序，然后再獲取最值。一旦有新的元素加入，再次獲取最值時(shí)，又要重新排序。所以并推薦使用。

2、heapq

一般來說，優(yōu)先級隊(duì)列都是使用堆這種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。而heapq就是Python標(biāo)準(zhǔn)庫中堆的實(shí)現(xiàn)。heapq默認(rèn)情況下實(shí)現(xiàn)的是最小堆。

入隊(duì)操作使用heappush()，出隊(duì)操作使用heappop()。

>>> import heapq
>>> q = []
>>> heapq.heappush(q, (2, 'code'))
>>> heapq.heappush(q, (1, 'eat'))
>>> heapq.heappush(q, (3, 'sleep'))
>>> q
[(1, 'eat'), (2, 'code'), (3, 'sleep')]
>>> while q:
	next_item = heapq.heappop(q)
	print(next_item)

	
(1, 'eat')
(2, 'code')
(3, 'sleep')

3、queue.PriorityQueue

queue.PriorityQueue內(nèi)部封裝了heapq，不同的是它是線程安全的。在并發(fā)環(huán)境下應(yīng)該選擇使用PriorityQueue。

>>> from queue import PriorityQueue
>>> q = PriorityQueue()
>>> q.put((2, 'code'))
>>> q.put((1, 'eat'))
>>> q.put((3, 'sleep'))
>>> while not q.empty():
	next_item = q.get()
	print(next_item)

(1, 'eat')
(2, 'code')
(3, 'sleep')

上述內(nèi)容就是Python中棧、隊(duì)列與優(yōu)先級隊(duì)列的實(shí)現(xiàn)，你們學(xué)到知識或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識儲備，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

當(dāng)前題目：Python中棧、隊(duì)列與優(yōu)先級隊(duì)列的實(shí)現(xiàn)-創(chuàng)新互聯(lián)
本文來源：http://jinyejixie.com/article48/depdhp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站收錄、虛擬主機(jī)、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站建設(shè)、Google、網(wǎng)站內(nèi)鏈

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)