Python中的堆棧：如何，為什么以及在哪里？

嘿，您可能已經(jīng)在這里搜索Python中的Stack了，好吧，我們?yōu)槟砹艘幌隆Ｔ诖瞬┛椭校覀儗?duì)如何在Python中使用Stack進(jìn)行如何，為什么和為什么進(jìn)行深入分析。

該博客包含以下主題：

什么是數(shù)據(jù)結(jié)構(gòu)中的堆棧？

為什么以及何時(shí)使用堆棧？

我們?nèi)绾卧赑ython中實(shí)現(xiàn)堆棧？

一個(gè)簡(jiǎn)單的程序來(lái)說(shuō)明Python中的Stack。

有關(guān)在Python和相關(guān)程序中使用堆棧的更多信息

該?表內(nèi)置

該?collections.deque類

該?queue.LifoQueue?類

什么是數(shù)據(jù)結(jié)構(gòu)中的堆棧？

數(shù)據(jù)結(jié)構(gòu)是組織計(jì)算機(jī)中存儲(chǔ)的關(guān)鍵，以便我們可以有效地訪問(wèn)和編輯數(shù)據(jù)。?堆棧?是計(jì)算機(jī)科學(xué)中定義的最早的數(shù)據(jù)結(jié)構(gòu)之一。簡(jiǎn)而言之，Stack是項(xiàng)目的線性集合。它是一組對(duì)象的集合，這些對(duì)象支持用于插入和刪除的快速后進(jìn)先出（LIFO）語(yǔ)義。它是現(xiàn)代計(jì)算機(jī)編程?和CPU架構(gòu)中使用的函數(shù)調(diào)用和參數(shù)的數(shù)組或列表結(jié)構(gòu)?。類似于??餐廳中的一疊盤(pán)子，一疊中的元素按照?“后進(jìn)先出”的順序?從堆棧的頂部添加或刪除。與列表或數(shù)組不同，則不允許對(duì)堆棧中包含的對(duì)象進(jìn)行隨機(jī)訪問(wèn)。

Stack中有兩種類型的操作-

推入–將數(shù)據(jù)添加到堆棧中。

彈出–從堆棧中刪除數(shù)據(jù)。

堆棧簡(jiǎn)單易學(xué)且易于實(shí)現(xiàn)，它們廣泛地集成在許多軟件中以執(zhí)行各種任務(wù)。它們可以用數(shù)組或鏈表實(shí)現(xiàn)?。在?這里，我們將依靠?List數(shù)據(jù)結(jié)構(gòu)。

為什么以及何時(shí)使用Stack？

堆棧是簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，可讓我們按順序存儲(chǔ)和檢索數(shù)據(jù)。

談到性能，正確的堆棧實(shí)現(xiàn)預(yù)期將花費(fèi)?O（1）的?時(shí)間進(jìn)行插入和刪除操作。

要了解底層的Stack，請(qǐng)考慮一堆書(shū)。您在堆棧頂部添加了一本書(shū)，因此要拾取的第一本書(shū)將是添加到堆棧中的最后一本書(shū)。

現(xiàn)實(shí)世界中有很多堆棧用例，對(duì)它們的了解使我們能夠輕松有效地解決許多數(shù)據(jù)存儲(chǔ)問(wèn)題。

假設(shè)您是一名開(kāi)發(fā)人員，并且正在使用全新的文字處理器。您需要?jiǎng)?chuàng)建一個(gè)撤消功能-允許用戶回溯其操作，直到會(huì)話開(kāi)始。堆棧非常適合這種情況。我們可以通過(guò)將用戶的每個(gè)動(dòng)作推入堆棧來(lái)記錄該動(dòng)作。當(dāng)用戶想要撤消某個(gè)動(dòng)作時(shí)，他們可以相應(yīng)地從堆棧中彈出。

我們?nèi)绾卧赑ython中實(shí)現(xiàn)堆棧？

在Python中，我們可以通過(guò)以下方式實(shí)現(xiàn)python堆棧：

使用內(nèi)置的List數(shù)據(jù)結(jié)構(gòu)。Python的內(nèi)置?List?數(shù)據(jù)結(jié)構(gòu)帶有模擬?堆棧?和?隊(duì)列操作的方法。

使用雙端隊(duì)列庫(kù)可以有效地在一個(gè)對(duì)象中提供堆棧和隊(duì)列操作。

使用?queue.LifoQueue類。

如前所述，我們可以使用“ PUSH”操作將項(xiàng)目添加到堆棧中，并使用“ POP”操作刪除項(xiàng)目?。

按鍵操作

推入–在堆棧頂部添加一個(gè)元素。請(qǐng)參考下圖以了解更多信息：

POP操作

Pop?–從堆棧頂部刪除一個(gè)元素。

這是一個(gè)簡(jiǎn)單的程序，用于說(shuō)明Python中的堆棧-

class Stack def_init_(self): self.items=[] def is_empty(self): return self.items==[] def push(self, data): self.items.append(data) def pop(self): return self.items.pop() s= Stack() while True: print(‘push’) print(‘pop’) print(‘quit’) do= input(‘What would you like to do?’).split() operation= do[0].strip().lower() if operation== ‘push’: s.push(int(do[1])) elif operation== ‘pop’: if s.is_empty(): print(‘Stack is empty’) else: print(‘Popped value:’, s.pop()) elif operation==’quit’: break

有關(guān)在Python和相關(guān)程序中使用堆棧的更多信息

堆棧在算法中提供了廣泛的用途，例如在語(yǔ)言解析和?運(yùn)行時(shí)內(nèi)存管理（“調(diào)用堆棧”）中。使用堆棧的一種簡(jiǎn)短而有用的算法是在樹(shù)或圖數(shù)據(jù)結(jié)構(gòu)上進(jìn)行深度優(yōu)先搜索（DFS）。?Python玩幾個(gè)堆棧實(shí)現(xiàn)，每個(gè)都有稍微不同的特征。讓我們簡(jiǎn)單看一下它們：

該?表?內(nèi)置

Python的內(nèi)置列表類型構(gòu)成了不錯(cuò)的堆棧數(shù)據(jù)結(jié)構(gòu)，因?yàn)樗С衷跀備N(xiāo)的O（1）?時(shí)間內(nèi)進(jìn)行推入和彈出操作?。

Python的列表在內(nèi)部以動(dòng)態(tài)數(shù)組的形式實(shí)現(xiàn)，這意味著它們偶爾需要在添加或刪除它們時(shí)調(diào)整存儲(chǔ)在其中的元素的存儲(chǔ)空間大小。存儲(chǔ)空間的分配超出了要求，因此并非每次推送或彈出操作都需要調(diào)整大小，并且?這些操作將獲得攤銷(xiāo)的?O（1）時(shí)間復(fù)雜度。

盡管這會(huì)使它們的性能不如基于鏈接列表的實(shí)現(xiàn)提供的穩(wěn)定的O（1）插入和刪除操作一致?。另一方面，列表提供?對(duì)堆棧上元素的快速O（1）時(shí)間隨機(jī)訪問(wèn)，這可能是一個(gè)附加好處。

使用列表作為堆棧時(shí)，這是一個(gè)重要的性能警告：

為了獲得用于插入和刪除的攤銷(xiāo)?O（1）性能，可使用append（）方法將new添加到列表的末尾，并使用pop（）從末尾刪除new。基于Python列表的堆棧向右擴(kuò)展，向左收縮。

從前面進(jìn)行添加和刪除需要花費(fèi)更多時(shí)間（O（n）?時(shí)間），因?yàn)楝F(xiàn)有元素必須四處移動(dòng)才能為要添加的新元素騰出空間。

＃使用Python列表作為堆棧（LIFO）：

s = [] s.append('eat') s.append('sleep') s.append('code') >>> s ['eat', 'sleep', 'code'] >>> s.pop() 'code' >>> s.pop() 'sleep' >>> s.pop() 'eat' >>> s.pop() IndexError: "pop from empty list"

該?collections.deque?類

deque類實(shí)現(xiàn)了一個(gè)雙端隊(duì)列，該隊(duì)列支持在O（1）?時(shí)間（未分期償還）中從任一端添加和刪除元素?。

由于雙端隊(duì)列在同等程度上支持在兩端添加和刪除元素，因此它們既可以用作隊(duì)列也可以用作堆棧。

Python的雙端隊(duì)列對(duì)象被實(shí)現(xiàn)為雙鏈表，這給它們提供了適當(dāng)而一致的性能插入和刪除元素，但是O（n）?性能差，?因?yàn)樗鼈冊(cè)诙褩Ｖ虚g隨機(jī)訪問(wèn)元素。

如果您正在Python標(biāo)準(zhǔn)庫(kù)中查找具有鏈接列表實(shí)現(xiàn)的性能特征的堆棧數(shù)據(jù)結(jié)構(gòu)，則collections.deque是一個(gè)不錯(cuò)的選擇。

＃使用collections.deque作為堆棧（LIFO）：

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

該?queue.LifoQueue?類

Python標(biāo)準(zhǔn)庫(kù)中的此堆棧實(shí)現(xiàn)是同步的，并提供鎖定語(yǔ)義以支持多個(gè)并發(fā)的生產(chǎn)者和使用者。

的?隊(duì)列模塊?包含其它幾類實(shí)施多生產(chǎn)者，多消費(fèi)者隊(duì)列是用于并行計(jì)算是有用的。

根據(jù)您的用例，鎖定語(yǔ)義可能會(huì)有所幫助，或者只是產(chǎn)生不必要的開(kāi)銷(xiāo)。在這種情況下，最好使用列表或雙端隊(duì)列作為通用堆棧。

＃使用queue.LifoQueue作為堆棧：

from queue import LifoQueue s = LifoQueue() s.put('eat') s.put('sleep') s.put('code') >>> s >>> s.get() 'code' >>> s.get() 'sleep' >>> s.get() 'eat' >>> s.get_nowait() queue.Empty >>> s.get() # Blocks / waits forever...

如果到目前為止，您現(xiàn)在必須可以使用Python中的堆棧，希望此博客可以幫助您了解Python中堆棧的不同實(shí)現(xiàn)方法。

至此，我們的“ python堆棧”文章結(jié)束了。我希望您喜歡閱讀此博客并發(fā)現(xiàn)它有啟發(fā)性。到現(xiàn)在為止，您必須已經(jīng)對(duì)python堆棧及其用法有了很好的了解。現(xiàn)在繼續(xù)練習(xí)所有示例。

數(shù)據(jù)結(jié)構(gòu) Python

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。