欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python中棧、隊(duì)列與優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)方法

 更新時(shí)間:2019年06月30日 11:01:21   作者:GoT陽仔  
這篇文章主要給大家介紹了關(guān)于Python中棧、隊(duì)列與優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)方法,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家學(xué)習(xí)或者使用python具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧

前言

棧、隊(duì)列和優(yōu)先級(jí)隊(duì)列都是非?;A(chǔ)的數(shù)據(jù)結(jié)構(gòu)。Python作為一種“編碼高效”的語言,對(duì)這些基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)都有比較好的實(shí)現(xiàn)。在業(yè)務(wù)需求開發(fā)過程中,不應(yīng)該重復(fù)造輪子,今天就來看看些數(shù)據(jù)結(jié)構(gòu)都有哪些實(shí)現(xiàn)。

0x00 棧(Stack)

棧是一種LIFO(后進(jìn)先出)的數(shù)據(jù)結(jié)構(gòu),有入棧(push)、出棧(pop)兩種操作,且只能操作棧頂元素。
在Python中有多種可以實(shí)現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)。

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í)就有可能會(huì)觸發(fā)擴(kuò)容操作。如果在list的頭部增減元素,也會(huì)移動(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í)會(huì)阻塞。

>>> 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í),會(huì)發(fā)生整個(gè)元素的移動(dòng)。

使用list來實(shí)現(xiàn)一個(gè)隊(duì)列時(shí),用append()執(zhí)行入隊(duì)操作,使用pop(0)方法在隊(duì)列頭部執(zhí)行出隊(duì)操作。由于在list的第一個(gè)元素進(jìn)行操作,所以后續(xù)的元素都會(huì)向前移動(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í)會(huì)一直阻塞直到有元素入隊(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í),會(huì)一直阻塞直到隊(duì)列不為空

4、multiprocessing.Queue

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

同樣地,它的入隊(duì)出隊(duì)操作分別是put()和get()。get()方法在隊(duì)列為空,會(huì)一直阻塞直到隊(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í),會(huì)一直阻塞直到隊(duì)列不為空

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

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

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

1、list

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

2、heapq

一般來說,優(yōu)先級(jí)隊(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')

0x03 總結(jié)一下

很多基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)在Python中已經(jīng)實(shí)現(xiàn)了的,我們不應(yīng)該重復(fù)造輪子,應(yīng)該選擇這些數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)業(yè)務(wù)需求。
collections.deque是一種雙向鏈表,在單線程的情況下,它可以用來實(shí)現(xiàn)Stack和Queue。而heapq模塊可以幫我們實(shí)現(xiàn)高效的優(yōu)先級(jí)隊(duì)列。

如果要在多并發(fā)的情況下使用Stack、Queue和PriorityQueue的話,那么應(yīng)該選用queue模塊下類:

  • 實(shí)現(xiàn)Stack的queue.LifoQueue
  • 實(shí)現(xiàn)Queue的queue.Queue或multiprocessing.Queue
  • 實(shí)現(xiàn)PriorityQueue的queue.PriorityQueue
  • 以上這些類都有put()和get()方法,且get()會(huì)在棧/隊(duì)列為空時(shí)阻塞。

0x04 學(xué)習(xí)資料

Python Tricks: A Buffet of Awesome Python Features

——Dan Bader

好了,以上就是這篇文章的全部內(nèi)容了,希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,謝謝大家對(duì)腳本之家的支持。

相關(guān)文章

  • Python實(shí)現(xiàn)B站UP主自動(dòng)監(jiān)控功能詳解

    Python實(shí)現(xiàn)B站UP主自動(dòng)監(jiān)控功能詳解

    眾所周知,B站有很多有趣的UP主,可以教大家一些"實(shí)用"的知識(shí),但是他們一般都沒有固定的更新時(shí)間。因此,本文將用Python編寫一個(gè)腳本,自動(dòng)監(jiān)控UP是否更新了視頻,感興趣的可以了解一下
    2022-03-03
  • 在雙python下設(shè)置python3為默認(rèn)的方法

    在雙python下設(shè)置python3為默認(rèn)的方法

    這篇文章主要介紹了如何在雙python下設(shè)置python3為默認(rèn),本文通過一個(gè)例子分步驟給大家介紹的非常詳細(xì),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2018-10-10
  • Django Serializer HiddenField隱藏字段實(shí)例

    Django Serializer HiddenField隱藏字段實(shí)例

    這篇文章主要介紹了Django Serializer HiddenField隱藏字段實(shí)例,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2020-03-03
  • Python第三方庫undetected_chromedriver的使用

    Python第三方庫undetected_chromedriver的使用

    這篇文章主要給大家介紹了關(guān)于Python第三方庫undetected_chromedriver的使用方法,文中通過實(shí)例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2023-01-01
  • 解析django的csrf跨站請(qǐng)求偽造

    解析django的csrf跨站請(qǐng)求偽造

    本文主要介紹了解析django的csrf跨站請(qǐng)求偽造,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2022-08-08
  • Python入門_淺談數(shù)據(jù)結(jié)構(gòu)的4種基本類型

    Python入門_淺談數(shù)據(jù)結(jié)構(gòu)的4種基本類型

    下面小編就為大家?guī)硪黄狿ython入門_淺談數(shù)據(jù)結(jié)構(gòu)的4種基本類型。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2017-05-05
  • python常用的時(shí)間模塊之datetime模塊示例詳解

    python常用的時(shí)間模塊之datetime模塊示例詳解

    這篇文章主要介紹了python常用的時(shí)間模塊之datetime模塊,本文通過示例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2023-05-05
  • Python實(shí)現(xiàn)迪杰斯特拉算法過程解析

    Python實(shí)現(xiàn)迪杰斯特拉算法過程解析

    這篇文章主要介紹了Python實(shí)現(xiàn)迪杰斯特拉算法過程解析,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-09-09
  • 打包FlaskAdmin程序時(shí)關(guān)于static路徑問題的解決

    打包FlaskAdmin程序時(shí)關(guān)于static路徑問題的解決

    近期寫了個(gè)基于Flask-admin的數(shù)據(jù)庫管理程序,通過pyinstaller打包,給別人用,經(jīng)過幾次嘗試,打包的數(shù)據(jù)一直找不到static里面的樣式文件,查閱資料后,最總把問題搞定了。寫下處理流程,供后來人參考
    2021-09-09
  • Python實(shí)現(xiàn)XGBoost算法的應(yīng)用實(shí)戰(zhàn)

    Python實(shí)現(xiàn)XGBoost算法的應(yīng)用實(shí)戰(zhàn)

    XGBoost(Extreme Gradient Boosting)是一種高效且廣泛使用的集成學(xué)習(xí)算法,它屬于梯度提升樹(GBDT)模型的一種改進(jìn),本文將結(jié)合實(shí)際案例,詳細(xì)介紹如何在Python中使用XGBoost算法進(jìn)行模型訓(xùn)練和預(yù)測(cè),需要的朋友可以參考下
    2024-08-08

最新評(píng)論