快捷導(dǎo)航

Python堆棧的具體使用

更新時(shí)間：2023年11月10日 15:31:12 作者：Rocky006

本文主要介紹了Python堆棧的具體使用,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

概要

雖然一些數(shù)據(jù)結(jié)構(gòu)是通用的并且可以在廣泛的應(yīng)用中使用，但其他數(shù)據(jù)結(jié)構(gòu)是專門化的并且被設(shè)計(jì)用于處理特定問題。堆棧就是這樣一種專門的結(jié)構(gòu)，以其簡(jiǎn)單性和非凡的實(shí)用性而聞名。

那么，什么是棧呢？從本質(zhì)上講，堆棧是一種遵循LIFO（后進(jìn)先出）原則的線性數(shù)據(jù)結(jié)構(gòu)。

多年來，堆棧已經(jīng)在許多領(lǐng)域找到了應(yīng)用，從您最喜歡的編程語(yǔ)言中的內(nèi)存管理到 Web 瀏覽器中的后退按鈕功能。這種內(nèi)在的簡(jiǎn)單性與其廣泛的適用性相結(jié)合，使該堆棧成為開發(fā)人員工具庫(kù)中不可或缺的工具。

堆棧數(shù)據(jù)結(jié)構(gòu)的基本概念

從本質(zhì)上講，堆棧看似簡(jiǎn)單，但它所具有的細(xì)微差別使其在計(jì)算領(lǐng)域具有多種應(yīng)用。在深入研究其實(shí)現(xiàn)和實(shí)際用途之前，讓我們確保對(duì)堆棧的核心概念有一個(gè)透徹的理解。

LIFO（后進(jìn)先出）原則

LIFO是堆棧背后的指導(dǎo)原則。這意味著最后進(jìn)入堆棧的項(xiàng)目是第一個(gè)離開的項(xiàng)目。這一特性將堆棧與其他線性數(shù)據(jù)結(jié)構(gòu)（例如隊(duì)列）區(qū)分開來。

注意：另一個(gè)幫助您理解堆棧如何工作的概念的有用示例是想象人們進(jìn)出電梯-最后進(jìn)入電梯的人是第一個(gè)出去的！

基本操作

每個(gè)數(shù)據(jù)結(jié)構(gòu)都是由它支持的操作定義的。對(duì)于堆棧來說，這些操作很簡(jiǎn)單但至關(guān)重要：

Push - 將一個(gè)元素添加到堆棧頂部。如果堆棧已滿，則此操作可能會(huì)導(dǎo)致堆棧溢出。

Pop - 刪除并返回堆棧最頂層的元素。如果堆棧為空，嘗試彈出可能會(huì)導(dǎo)致堆棧下溢。

Peek（或 Top） - 觀察最上面的元素而不刪除它。當(dāng)您想要檢查當(dāng)前頂部元素而不更改堆棧狀態(tài)時(shí)，此操作非常有用。

如何在 Python 中從頭開始實(shí)現(xiàn)堆棧

掌握了堆棧背后的基本原理后，是時(shí)候卷起袖子深入研究事物的實(shí)際方面了。實(shí)現(xiàn)堆棧雖然簡(jiǎn)單，但可以通過多種方式實(shí)現(xiàn)。在本節(jié)中，我們將探討實(shí)現(xiàn)堆棧的兩種主要方法 - 使用數(shù)組和鏈表。

使用數(shù)組實(shí)現(xiàn)堆棧

數(shù)組是連續(xù)的內(nèi)存位置，提供了一種直觀的方式來表示堆棧。它們?cè)试S按索引訪問元素的時(shí)間復(fù)雜度為 O(1)，從而確保快速推送、彈出和查看操作。此外，數(shù)組可以提高內(nèi)存效率，因?yàn)闆]有鏈表中的指針開銷。

另一方面，傳統(tǒng)數(shù)組具有固定大小，這意味著一旦初始化，它們就無法調(diào)整大小。如果不進(jìn)行監(jiān)控，這可能會(huì)導(dǎo)致堆棧溢出。這可以通過動(dòng)態(tài)數(shù)組（如 Python 的list）來克服，它可以調(diào)整大小，但此操作的成本相當(dāng)高。

完成所有這些后，讓我們開始在 Python 中使用數(shù)組實(shí)現(xiàn)我們的堆棧類。首先，讓我們創(chuàng)建一個(gè)類本身，其構(gòu)造函數(shù)將堆棧的大小作為參數(shù)： ???

class Stack:
    def __init__(self, size):
        self.size = size
        self.stack = [None] * size
        self.top = -1

我們?cè)陬愔写鎯?chǔ)了三個(gè)值。是size所需的堆棧大小，是stack用于表示堆棧數(shù)據(jù)結(jié)構(gòu)的實(shí)際數(shù)組，是數(shù)組中最后一個(gè)元素（堆棧頂部）top的索引。stack

從現(xiàn)在開始，我們將為每個(gè)基本堆棧操作創(chuàng)建并解釋一種方法。這些方法中的每一個(gè)都將包含在Stack我們剛剛創(chuàng)建的類中。

我們先從push()方法開始吧。如前所述，入棧操作將一個(gè)元素添加到堆棧頂部。首先，我們將檢查堆棧是否還有空間供我們要添加的元素使用。如果堆棧已滿，我們將引發(fā)Stack Overflow異常。否則，我們只需添加元素并相應(yīng)地調(diào)整top和stack： ?????

def push(self, item):
        if self.top == self.size - 1:
            raise Exception("Stack Overflow")
        self.top += 1
        self.stack[self.top] = item

現(xiàn)在，我們可以定義從棧頂移除元素的方法——方法pop()。在嘗試刪除元素之前，我們需要檢查堆棧中是否有任何元素，因?yàn)閲L試從空堆棧中彈出元素是沒有意義的： ????

def pop(self):
        if self.top == -1:
            raise Exception("Stack Underflow")
        item = self.stack[self.top]
        self.top -= 1
        return item

最后，我們可以定義peek()只返回當(dāng)前堆棧頂部元素的值的方法： ??????

def peek(self):
    if self.top == -1:
        raise Exception("Stack is empty")
    return self.stack[self.top]

我們現(xiàn)在有一個(gè)類，它在 Python 中使用列表實(shí)現(xiàn)堆棧的行為。

使用鏈表實(shí)現(xiàn)堆棧

鏈表是動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以輕松增長(zhǎng)和收縮，這對(duì)于實(shí)現(xiàn)堆棧是有利的。由于鏈表根據(jù)需要分配內(nèi)存，因此堆?？梢詣?dòng)態(tài)增長(zhǎng)和減少，而無需顯式調(diào)整大小。使用鏈表實(shí)現(xiàn)堆棧的另一個(gè)好處是入棧和出棧操作只需要簡(jiǎn)單的指針變化。這樣做的缺點(diǎn)是鏈表中的每個(gè)元素都有一個(gè)額外的指針，與數(shù)組相比會(huì)消耗更多的內(nèi)存。

在實(shí)際鏈表之前我們需要實(shí)現(xiàn)的第一件事是單個(gè)節(jié)點(diǎn)的類： ?????

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

此實(shí)現(xiàn)僅存儲(chǔ)兩點(diǎn)數(shù)據(jù) - 存儲(chǔ)在節(jié)點(diǎn) ( ) 中的值data和對(duì)下一個(gè)節(jié)點(diǎn) ( ) 的引用next。

現(xiàn)在我們可以跳到實(shí)際的堆棧類本身。構(gòu)造函數(shù)與之前的構(gòu)造函數(shù)略有不同。它將只包含一個(gè)變量 - 對(duì)堆棧頂部節(jié)點(diǎn)的引用： ??????

class Stack:
    def __init__(self):
        self.top = None

正如預(yù)期的那樣，該push()方法將一個(gè)新元素（在本例中為節(jié)點(diǎn)）添加到堆棧頂部： ??????

def push(self, item):
        node = Node(item)
        if self.top:
            node.next = self.top
        self.top = node

該pop()方法檢查堆棧中是否有元素，如果堆棧不為空，則刪除最上面的元素： ??????

def pop(self):
        if not self.top:
            raise Exception("Stack Underflow")
        item = self.top.data
        self.top = self.top.next
        return item

最后，該peek()方法只是從堆棧頂部讀取元素的值（如果有的話）： ????

def peek(self):
    if not self.top:
        raise Exception("Stack is empty")
    return self.top.data

注意：兩個(gè)類的接口Stack是相同的 - 唯一的區(qū)別是類方法的內(nèi)部實(shí)現(xiàn)。這意味著您可以輕松地在不同的實(shí)現(xiàn)之間切換，而不必?fù)?dān)心類的內(nèi)部結(jié)構(gòu)。

數(shù)組和鏈表之間的選擇取決于應(yīng)用程序的具體要求和約束。

如何使用 Python 的內(nèi)置結(jié)構(gòu)實(shí)現(xiàn)堆棧

對(duì)于許多開發(fā)人員來說，從頭開始構(gòu)建堆棧雖然具有教育意義，但可能不是在實(shí)際應(yīng)用程序中使用堆棧的最有效方法。幸運(yùn)的是，許多流行的編程語(yǔ)言都配備了自然支持堆棧操作的內(nèi)置數(shù)據(jù)結(jié)構(gòu)和類。

Python 作為一種多功能且動(dòng)態(tài)的語(yǔ)言，沒有專用的堆棧類。然而，它的內(nèi)置數(shù)據(jù)結(jié)構(gòu)，特別是模塊中的列表和雙端隊(duì)列類collections，可以輕松地用作堆棧。

使用 Python 列表作為堆棧

append()由于 Python 列表的動(dòng)態(tài)特性以及和等方法的存在，Python 列表可以非常有效地模擬堆棧pop()。

推送操作- 將元素添加到堆棧頂部就像使用以下append()方法一樣簡(jiǎn)單：

stack = []
stack.append('A')
stack.append('B')

Pop 操作- 刪除最上面的元素可以使用不帶任何參數(shù)的方法來實(shí)現(xiàn)pop()：

top_element = stack.pop()  # This will remove 'B' from the stack

窺視操作可以使用負(fù)索引來訪問頂部而不彈出：

top_element = stack[-1]  # This will return 'A' without removing it

使用集合模塊中的deque類

deque（雙端隊(duì)列的縮寫）類是堆棧實(shí)現(xiàn)的另一個(gè)多功能工具。它針對(duì)兩端的快速追加和彈出進(jìn)行了優(yōu)化，使其堆棧操作比列表稍微高效一些。

初始化：

from collections import deque
stack = deque()

推送操作- 與列表類似，append()使用方法：
```
stack.append('A')
stack.append('B')
```
彈出操作- 與列表類似，pop()方法執(zhí)行以下工作：

top_element = stack.pop()  # This will remove 'B' from the stack

查看操作- 方法與列表相同：

top_element = stack[-1]  # This will return 'A' without removing it

雖然列表和雙端隊(duì)列都可以用作堆棧，但如果您主要將結(jié)構(gòu)用作堆棧（從一端追加和彈出），由于deque其優(yōu)化，速度可能會(huì)稍快一些。
然而，對(duì)于大多數(shù)實(shí)際目的，除非處理性能關(guān)鍵的應(yīng)用程序，Python 的列表應(yīng)該足夠了。

注意：本節(jié)深入探討 Python 的類似堆棧行為的內(nèi)置產(chǎn)品。當(dāng)您手邊擁有如此強(qiáng)大的工具時(shí)，您不一定需要重新發(fā)明輪子（通過從頭開始實(shí)現(xiàn)堆棧）。

堆棧潛在的相關(guān)問題以及如何克服它們

雖然堆棧像任何其他數(shù)據(jù)結(jié)構(gòu)一樣具有令人難以置信的通用性和高效性，但它們也不能避免潛在的陷阱。在使用堆棧時(shí)必須認(rèn)識(shí)到這些挑戰(zhàn)并制定解決這些挑戰(zhàn)的策略。在本節(jié)中，我們將深入探討一些常見的堆棧相關(guān)問題，并探索解決這些問題的方法。

堆棧溢出

當(dāng)嘗試將元素推入已達(dá)到其最大容量的堆棧時(shí)，就會(huì)發(fā)生這種情況。在堆棧大小固定的環(huán)境中（例如在某些低級(jí)編程場(chǎng)景或遞歸函數(shù)調(diào)用中），這尤其是一個(gè)問題。

如果使用基于數(shù)組的堆棧，請(qǐng)考慮切換到動(dòng)態(tài)數(shù)組或鏈表實(shí)現(xiàn)，它們會(huì)自行調(diào)整大小。防止堆棧溢出的另一個(gè)步驟是持續(xù)監(jiān)視堆棧的大小，特別是在壓入操作之前，并針對(duì)堆棧溢出提供明確的錯(cuò)誤消息或提示。

如果由于過多的遞歸調(diào)用而導(dǎo)致堆棧溢出，請(qǐng)考慮迭代解決方案或在環(huán)境允許的情況下增加遞歸限制。

堆棧下溢

當(dāng)嘗試從空堆棧中彈出元素時(shí)會(huì)發(fā)生這種情況。為了防止這種情況發(fā)生，請(qǐng)?jiān)趫?zhí)行彈出或查看操作之前始終檢查堆棧是否為空。返回清晰的錯(cuò)誤消息或優(yōu)雅地處理下溢，而不會(huì)導(dǎo)致程序崩潰。

在可接受的環(huán)境中，請(qǐng)考慮在從空堆棧彈出時(shí)返回一個(gè)特殊值以表示操作無效。

內(nèi)存限制

在內(nèi)存受限的環(huán)境中，即使動(dòng)態(tài)調(diào)整堆棧大?。ɡ缁阪湵淼亩褩＃绻褩Ｗ兊锰?，也可能會(huì)導(dǎo)致內(nèi)存耗盡。因此，請(qǐng)密切關(guān)注應(yīng)用程序的整體內(nèi)存使用情況和堆棧的增長(zhǎng)。也許對(duì)堆棧的大小引入軟上限。

線程安全問題

在多線程環(huán)境中，不同線程對(duì)共享堆棧的同時(shí)操作可能會(huì)導(dǎo)致數(shù)據(jù)不一致或意外行為。此問題的潛在解決方案可能是：