快捷導航

Python堆棧的具體使用

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

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

概要

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

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

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

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

從本質(zhì)上講，堆?？此坪唵危哂械募毼⒉顒e使其在計算領(lǐng)域具有多種應(yīng)用。在深入研究其實現(xiàn)和實際用途之前，讓我們確保對堆棧的核心概念有一個透徹的理解。

LIFO（后進先出）原則

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

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

基本操作

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

Push - 將一個元素添加到堆棧頂部。如果堆棧已滿，則此操作可能會導致堆棧溢出。

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

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

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

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

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

數(shù)組是連續(xù)的內(nèi)存位置，提供了一種直觀的方式來表示堆棧。它們允許按索引訪問元素的時間復(fù)雜度為 O(1)，從而確?？焖偻扑?、彈出和查看操作。此外，數(shù)組可以提高內(nèi)存效率，因為沒有鏈表中的指針開銷。

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

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

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

我們在類中存儲了三個值。是size所需的堆棧大小，是stack用于表示堆棧數(shù)據(jù)結(jié)構(gòu)的實際數(shù)組，是數(shù)組中最后一個元素（堆棧頂部）top的索引。stack

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

我們先從push()方法開始吧。如前所述，入棧操作將一個元素添加到堆棧頂部。首先，我們將檢查堆棧是否還有空間供我們要添加的元素使用。如果堆棧已滿，我們將引發(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()。在嘗試刪除元素之前，我們需要檢查堆棧中是否有任何元素，因為嘗試從空堆棧中彈出元素是沒有意義的： ????

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

使用 Python 列表作為堆棧

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

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

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

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

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

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

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

使用集合模塊中的deque類

deque（雙端隊列的縮寫）類是堆棧實現(xià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

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

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

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

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

堆棧溢出

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

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

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

堆棧下溢

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

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

內(nèi)存限制

在內(nèi)存受限的環(huán)境中，即使動態(tài)調(diào)整堆棧大小（例如基于鏈表的堆棧），如果堆棧變得太大，也可能會導致內(nèi)存耗盡。因此，請密切關(guān)注應(yīng)用程序的整體內(nèi)存使用情況和堆棧的增長。也許對堆棧的大小引入軟上限。

線程安全問題

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