Python中棧、隊列與優(yōu)先級隊列的實現(xiàn)方法
前言
棧、隊列和優(yōu)先級隊列都是非常基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。Python作為一種“編碼高效”的語言,對這些基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)都有比較好的實現(xiàn)。在業(yè)務(wù)需求開發(fā)過程中,不應(yīng)該重復(fù)造輪子,今天就來看看些數(shù)據(jù)結(jié)構(gòu)都有哪些實現(xiàn)。
0x00 棧(Stack)
棧是一種LIFO(后進先出)的數(shù)據(jù)結(jié)構(gòu),有入棧(push)、出棧(pop)兩種操作,且只能操作棧頂元素。
在Python中有多種可以實現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)。
1、list
list是Python內(nèi)置的列表數(shù)據(jù)結(jié)構(gòu),它支持棧的特性,有入棧和出棧操作。只不過用list實現(xiàn)棧性能不是特別好。
因為list內(nèi)部是通過一個動態(tài)擴容的數(shù)組來實現(xiàn)的。當增減元素時就有可能會觸發(fā)擴容操作。如果在list的頭部增減元素,也會移動整個列表。
如要使用list來實現(xiàn)一個棧的話,可以使用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類是一種雙端隊列。在Python中它就是一個雙向列表,可以以常用時間在兩端執(zhí)行添加和刪除元素的操作,非常高效,所以它既可以實現(xiàn)棧也可以實現(xiàn)隊列。
如果要在Python實現(xiàn)一個棧,那么應(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
顧名思義,這個就是一個棧。不過它是線程安全的,如果要在并發(fā)的環(huán)境下使用,那么就可以選擇使用LifoQueue。
它入棧和出棧操作是使用put()和get(),其中g(shù)et()在LifoQueue為空時會阻塞。
>>> 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 隊列(Queue)
隊列是一種FIFO(先進先出)的數(shù)據(jù)結(jié)構(gòu)。它有入隊(enqueue)、出隊(dequeue)兩種操作,而且也是常數(shù)時間的操作。
在Python中可以使用哪些數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)一個隊列呢?
1、list
list可以實現(xiàn)一個隊列,但它的入隊、出隊操作就不是非常高效了。因為list是一個動態(tài)列表,在隊列的頭部執(zhí)行出隊操作時,會發(fā)生整個元素的移動。
使用list來實現(xiàn)一個隊列時,用append()執(zhí)行入隊操作,使用pop(0)方法在隊列頭部執(zhí)行出隊操作。由于在list的第一個元素進行操作,所以后續(xù)的元素都會向前移動一位。因此用list來實現(xiàn)隊列是不推薦的。
>>> 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是一個雙向列表,它可以在列表兩端以常數(shù)時間進行添加刪除操作。所以用deque來實現(xiàn)一個隊列是非常高效的。
deque入隊操作使用append()方法,出隊操作使用popleft()方法。
>>> from collections import deque >>> q = deque() >>> q.append('eat') >>> q.append('sleep') >>> q.append('code') >>> q deque(['eat', 'sleep', 'code']) # 使用popleft出隊 >>> q.popleft() 'eat' >>> q.popleft() 'sleep' >>> q.popleft() 'code' >>> q.popleft() IndexError: pop from an empty deque
3、queue.Queue
同樣地,如果要在并發(fā)環(huán)境下使用隊列,那么選擇線程安全的queue.Queue。
與LifoQueue類似,入隊和出隊操作分別是put()和get()方法,get()在隊列為空時會一直阻塞直到有元素入隊。
>>> 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' # 隊列為空不要執(zhí)行等待 >>> q.get_nowait() _queue.Empty >>> q.put('111') >>> q.get_nowait() '111' >>> q.get() # 隊列為空時,會一直阻塞直到隊列不為空
4、multiprocessing.Queue
多進程版本的隊列。如果要在多進程環(huán)境下使用隊列,那么應(yīng)該選擇multiprocessing.Queue。
同樣地,它的入隊出隊操作分別是put()和get()。get()方法在隊列為空,會一直阻塞直到隊列不為空。
>>> 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() # 隊列為空時,會一直阻塞直到隊列不為空
0x02 優(yōu)先級隊列(PriorityQueue)
一個近乎排序的序列里可以使用優(yōu)先級隊列這種數(shù)據(jù)結(jié)構(gòu),它能高效獲取最大或最小的元素。
在調(diào)度問題的場景中經(jīng)常會用到優(yōu)先級隊列。它主要有獲取最大值或最小值的操作和入隊操作。
1、list
使用list可以實現(xiàn)一個優(yōu)先級隊列,但它并不高效。因為當要獲取最值時需要排序,然后再獲取最值。一旦有新的元素加入,再次獲取最值時,又要重新排序。所以并推薦使用。
2、heapq
一般來說,優(yōu)先級隊列都是使用堆這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。而heapq就是Python標準庫中堆的實現(xiàn)。heapq默認情況下實現(xiàn)的是最小堆。
入隊操作使用heappush(),出隊操作使用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')
0x03 總結(jié)一下
很多基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)在Python中已經(jīng)實現(xiàn)了的,我們不應(yīng)該重復(fù)造輪子,應(yīng)該選擇這些數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)業(yè)務(wù)需求。
collections.deque是一種雙向鏈表,在單線程的情況下,它可以用來實現(xiàn)Stack和Queue。而heapq模塊可以幫我們實現(xiàn)高效的優(yōu)先級隊列。
如果要在多并發(fā)的情況下使用Stack、Queue和PriorityQueue的話,那么應(yīng)該選用queue模塊下類:
- 實現(xiàn)Stack的queue.LifoQueue
- 實現(xiàn)Queue的queue.Queue或multiprocessing.Queue
- 實現(xiàn)PriorityQueue的queue.PriorityQueue
- 以上這些類都有put()和get()方法,且get()會在棧/隊列為空時阻塞。
0x04 學習資料
Python Tricks: A Buffet of Awesome Python Features
——Dan Bader
好了,以上就是這篇文章的全部內(nèi)容了,希望本文的內(nèi)容對大家的學習或者工作具有一定的參考學習價值,謝謝大家對腳本之家的支持。
相關(guān)文章
Python實現(xiàn)B站UP主自動監(jiān)控功能詳解
眾所周知,B站有很多有趣的UP主,可以教大家一些"實用"的知識,但是他們一般都沒有固定的更新時間。因此,本文將用Python編寫一個腳本,自動監(jiān)控UP是否更新了視頻,感興趣的可以了解一下2022-03-03Django Serializer HiddenField隱藏字段實例
這篇文章主要介紹了Django Serializer HiddenField隱藏字段實例,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-03-03Python第三方庫undetected_chromedriver的使用
這篇文章主要給大家介紹了關(guān)于Python第三方庫undetected_chromedriver的使用方法,文中通過實例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2023-01-01Python入門_淺談數(shù)據(jù)結(jié)構(gòu)的4種基本類型
下面小編就為大家?guī)硪黄狿ython入門_淺談數(shù)據(jù)結(jié)構(gòu)的4種基本類型。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2017-05-05打包FlaskAdmin程序時關(guān)于static路徑問題的解決
近期寫了個基于Flask-admin的數(shù)據(jù)庫管理程序,通過pyinstaller打包,給別人用,經(jīng)過幾次嘗試,打包的數(shù)據(jù)一直找不到static里面的樣式文件,查閱資料后,最總把問題搞定了。寫下處理流程,供后來人參考2021-09-09Python實現(xiàn)XGBoost算法的應(yīng)用實戰(zhàn)
XGBoost(Extreme Gradient Boosting)是一種高效且廣泛使用的集成學習算法,它屬于梯度提升樹(GBDT)模型的一種改進,本文將結(jié)合實際案例,詳細介紹如何在Python中使用XGBoost算法進行模型訓練和預(yù)測,需要的朋友可以參考下2024-08-08