• 棧結(jié)構(gòu)：后進者先出，先進者后出

• 棧是一種“操作受限”的線性表

• 當(dāng)某個數(shù)據(jù)集合只涉及在一端插入和刪除數(shù)據(jù)，并且滿足后進先出、先進后出的特性，這時我們就應(yīng)該首選“?！边@種數(shù)據(jù)結(jié)構(gòu)

棧的實現(xiàn)

• 使用數(shù)組實現(xiàn)：順序棧

class ArrayStack:
    """使用數(shù)組實現(xiàn)一個順序棧"""

    def __init__(self):
        '''
        初始化順序棧

        參數(shù)：
            無

        返回值：
            無
        '''
        
        self.items = []

    def push(self, item):
        '''
        入棧操作

        參數(shù)：
            item (任意類型): 待入棧的值

        返回值：
            無
        '''
        self.items.append(item)

    def pop(self):
        '''
        出棧操作

        參數(shù)：
            無

        返回值：
            待出棧的值
        '''
        if not self.is_empty():
            return self.items.pop()

    def is_empty(self):
        '''
        檢查棧是否為空

        參數(shù)：
            無

        返回值：
            bool: 如果棧為空則返回True，否則返回False
        '''
        return len(self.items) == 0

• 使用鏈表實現(xiàn)：鏈?zhǔn)綏?/li>

class Node:
    '''維護鏈表節(jié)點'''
    def __init__(self, value):
        '''
        初始化鏈表節(jié)點

        參數(shù)：
            value (任意類型): 節(jié)點的值

        返回值：
            無
        '''
        # 節(jié)點的值
        self.value = value
        # 指向下一個節(jié)點的指針
        self.next = None

class Stack:
    '''進行出棧或入棧操作'''
    def __init__(self):
        '''
        初始化棧

        參數(shù)：
            無

        返回值：
            無
        '''
        # 棧頂節(jié)點
        self.top = None

    def push(self, value):
        '''
        入棧操作

        參數(shù)：
            value (任意類型): 要入棧的值

        返回值：
            無
        '''
        if self.top is None:
            self.top = Node(value)
        else:
            # 創(chuàng)建新節(jié)點
            new_node = Node(value)
            # 將新節(jié)點指向當(dāng)前的棧頂節(jié)點
            new_node.next = self.top
            # 更新棧頂節(jié)點為新節(jié)點
            self.top = new_node

    def pop(self):
        '''
        出棧操作

        參數(shù)：
            無

        返回值：
            出棧的節(jié)點的值
        '''
        if self.top is None:
            return None
        else:
            # 彈出棧頂節(jié)點
            popped_node = self.top
            # 更新棧頂節(jié)點為下一個節(jié)點
            self.top = self.top.next
            # 將彈出的節(jié)點從鏈表中斷開
            popped_node.next = None
            # 返回彈出節(jié)點的值
            return popped_node.value

棧的應(yīng)用

函數(shù)調(diào)用棧

操作系統(tǒng)給每個線程分配了一塊獨立的內(nèi)存空間，這塊內(nèi)存被組織成“?！边@種結(jié)構(gòu), 用來存儲函數(shù)調(diào)用時的臨時變量。每進入一個函數(shù)，就會將臨時變量作為一個棧幀¹入棧，當(dāng)被調(diào)用函數(shù)執(zhí)行完成，返回之后，將這個函數(shù)對應(yīng)的棧幀出棧。

def main():
    '''
    主函數(shù)，用于執(zhí)行程序的主要邏輯

    參數(shù)：
        無

    返回值：
        int: 表示程序執(zhí)行結(jié)果的返回值
    '''
    a = 1
    ret = 0
    res = 0

    # 調(diào)用add函數(shù)，將返回值賦給ret變量
    ret = add(3, 5)

    # 計算a和ret的和，將結(jié)果賦給res變量
    res = a + ret

    # 打印res的值
    print(res)

    return 0


def add(x, y):
    '''
    將兩個數(shù)字相加

    參數(shù)：
        x (int): 第一個數(shù)字
        y (int): 第二個數(shù)字

    返回值：
        int: 兩個數(shù)字的和
    '''
    sum = 0

    # 計算x和y的和，將結(jié)果賦給sum變量
    sum = x + y

    return sum


if __name__ == '__main__':
    # 調(diào)用main函數(shù)
    main()

能否使用其他數(shù)據(jù)結(jié)構(gòu)實現(xiàn)函數(shù)調(diào)用功能？

• 雖然其他數(shù)據(jù)結(jié)構(gòu)也可以用來保存臨時變量，但是它們的實現(xiàn)可能不如棧那么高效。
• 例如，使用鏈表來保存上下文信息，需要在插入和刪除元素時遍歷鏈表，時間復(fù)雜度為O(n)，而使用棧的時間復(fù)雜度為O(1)。因此，棧是最常用的函數(shù)調(diào)用棧的實現(xiàn)方式。

表達式求值

編譯器通過兩個棧來實現(xiàn)的。其中一個保存操作數(shù)的棧，另一個是保存運算符的棧。

1. 我們從左向右遍歷表達式，當(dāng)遇到數(shù)字，我們就直接壓入操作數(shù)棧；
2. 當(dāng)遇到運算符，就與運算符棧的棧頂元素進行比較。如果比運算符棧頂元素的優(yōu)先級高，就將當(dāng)前運算符壓入棧；
3. 如果比運算符棧頂元素的優(yōu)先級低或者相同，從運算符棧中取棧頂運算符，從操作數(shù)棧的棧頂取 2 個操作數(shù)，然后進行計算，再把計算完的結(jié)果壓入操作數(shù)棧，繼續(xù)比較。

檢查括號是否匹配

假設(shè)表達式中只包含三種括號：

• 圓括號 ()

• 方括號[]

• 花括號{}

它們可以任意嵌套。比如，{[] ()[{}]}或[{()}([])]等都為合法格式，而{[}()]或[({)]為不合法的格式。

那么如何檢查括號是否合法？

1. 我們用棧來保存未匹配的左括號，從左到右依次掃描字符串。

2. 當(dāng)掃描到左括號時，則將其壓入棧中；當(dāng)掃描到右括號時，從棧頂取出一個左括號。如果能夠匹配，比如 ( 跟 ) 匹配，[跟]匹配，{跟}匹配，則繼續(xù)掃描剩下的字符串。如果掃描的過程中，遇到不能配對的右括號，或者棧中沒有數(shù)據(jù)，則說明為非法格式。

3. 當(dāng)所有的括號都掃描完成之后，如果棧為空，則說明字符串為合法格式；否則，說明有未匹配的左括號，為非法格式。

實現(xiàn)瀏覽器的前進和后退功能

• 使用兩個棧，X 和 Y。
• 我們把首次瀏覽的頁面依次壓入棧 X，當(dāng)點擊后退按鈕時，再依次從棧 X 中出棧，并將出棧的數(shù)據(jù)依次放入棧 Y。當(dāng)我們點擊前進按鈕時，我們依次從棧 Y 中取出數(shù)據(jù)，放入棧 X 中。
• 當(dāng)棧 X 中沒有數(shù)據(jù)時，那就說明沒有頁面可以繼續(xù)后退瀏覽了。當(dāng)棧 Y 中沒有數(shù)據(jù)，那就說明沒有頁面可以點擊前進按鈕瀏覽了。

JVM中的堆棧和棧的區(qū)別是什么？

JVM 中的“?！焙蛿?shù)據(jù)結(jié)構(gòu)中的“?！笔穷愃频?，都是一種后進先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)。但是它們的實現(xiàn)和使用方式是不同的。

在JVM中，每個線程都有一個私有的棧，用于存儲方法調(diào)用時的局部變量和操作數(shù)棧。當(dāng)一個方法被調(diào)用時，會在棧上創(chuàng)建一個新的棧幀，用于存儲該方法的局部變量和操作數(shù)棧等信息。當(dāng)方法返回時，該方法對應(yīng)的棧幀就會被銷毀。因此，JVM中的“?！敝饕糜诜椒ㄕ{(diào)用和返回，以及存儲線程私有的數(shù)據(jù)。

在計算機科學(xué)中，棧通常指的是一種數(shù)據(jù)結(jié)構(gòu)，它是一種后進先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，只能在棧頂進行插入和刪除操作。棧通常用于函數(shù)調(diào)用時保存臨時變量和返回地址，以及遞歸等算法實現(xiàn)中。

Leetcode：棧習(xí)題

題目：

• 20
• 155
• 232
• 844
• 224
• 682
• 496

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法之美 | 棧的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！