概要

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

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

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

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

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

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

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

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

基本操作

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

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

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

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

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

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

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

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

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

完成所有這些后，讓我們開始在 Python 中使用數(shù)組實(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ù)組，是數(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()。在嘗試刪除元素之前，我們需要檢查堆棧中是否有任何元素，因?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)在有一個類，它在 Python 中使用列表實(shí)現(xiàn)堆棧的行為。

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

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

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

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

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

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

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

正如預(yù)期的那樣，該push()方法將一個新元素（在本例中為節(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

注意：兩個類的接口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)堆棧

對于許多開發(fā)人員來說，從頭開始構(gòu)建堆棧雖然具有教育意義，但可能不是在實(shí)際應(yīng)用程序中使用堆棧的最有效方法。幸運(yùn)的是，許多流行的編程語言都配備了自然支持堆棧操作的內(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ù)的方法來實(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（雙端隊列的縮寫）類是堆棧實(shí)現(xiàn)的另一個多功能工具。它針對兩端的快速追加和彈出進(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

• 雖然列表和雙端隊列都可以用作堆棧，但如果您主要將結(jié)構(gòu)用作堆棧（從一端追加和彈出），由于deque其優(yōu)化，速度可能會稍快一些。

• 然而，對于大多數(shù)實(shí)際目的，除非處理性能關(guān)鍵的應(yīng)用程序，Python 的列表應(yīng)該足夠了。

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

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

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

堆棧溢出

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

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

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

堆棧下溢

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

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

內(nèi)存限制

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

線程安全問題

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

• 互斥體和鎖- 使用互斥體（互斥對象）或鎖來確保在給定時間只有一個線程可以在堆棧上執(zhí)行操作。

• 原子操作- 如果環(huán)境支持，則利用原子操作來確保推送和彈出操作期間的數(shù)據(jù)一致性。

• 線程本地堆棧- 在每個線程都需要其堆棧的情況下，請考慮使用線程本地存儲為每個線程提供單獨(dú)的堆棧實(shí)例。

總結(jié)

雖然堆棧確實(shí)很強(qiáng)大，但了解其潛在問題并積極實(shí)施解決方案將確保應(yīng)用程序的健壯和無錯誤。認(rèn)識到這些陷阱就成功了一半，另一半就是采用最佳實(shí)踐來有效解決這些問題。

到此這篇關(guān)于Python堆棧的具體使用的文章就介紹到這了,更多相關(guān)Python堆棧內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論