參考鏈接：https://github.com/itcharge/LeetCode-Py

一讥巡、堆棧基礎(chǔ)知識

堆棧（Stack）：簡稱棧不脯。是一種線性表數(shù)據(jù)結(jié)構(gòu)摔吏，它只允許在表的一端進(jìn)行插入和刪除汰瘫。其中怀读，允許插入和刪除的一端稱為 「棧頂（top）」，另一端稱為 「棧底（bottom）」鲫尊，表中沒有任何數(shù)據(jù)元素稱為 「空棧」惜犀。
基本操作（插入和刪除）：

• 插入操作又稱為「入楊醣」或者「進(jìn)棧」虽界。

• 刪除操作又稱為「出椘常」或者「退棧」莉御。

  
  
  image.png

1.1 堆棧的順序存儲與鏈?zhǔn)酱鎯?/h2>

和線性表類似撇吞，棧有兩種存儲表示方法：「順序棧」 和 「鏈?zhǔn)綏礁叔！埂?br> 「順序楇咕保」：即堆棧的順序存儲結(jié)構(gòu)。利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)脑乩殴兀瑫r(shí)使用指針 top 指示棧頂元素在順序棧中的位置煮岁。
「鏈?zhǔn)綏！?/strong>：即堆棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)涣易。利用單鏈表的方式來實(shí)現(xiàn)堆棧画机。棧中元素按照插入順序依次插入到鏈表的第一個(gè)節(jié)點(diǎn)之前，并使用棧頂指針 top 指示棧頂元素新症，top 永遠(yuǎn)指向鏈表的頭節(jié)點(diǎn)位置步氏。

1.1.1 堆棧的基本操作

棧作為一種線性表來說，理論上應(yīng)該具備線性表所有的操作特性徒爹，但由于「后進(jìn)先出」的特殊性荚醒，所以針對棧的操作進(jìn)行了一些變化。尤其是插入操作和刪除操作隆嗅，改為了入棧（push）和出棧（pop）界阁。

• 初始化空棧：創(chuàng)建一個(gè)空棧，定義棧的大小 size胖喳，以及棧頂元素指針 top铺董。
• 判斷棧是否為空：當(dāng)堆棧為空時(shí)，返回 True禀晓。當(dāng)堆棧不為空時(shí)，返回 False坝锰。一般只用于棧中刪除操作和獲取當(dāng)前棧頂元素操作中粹懒。
• 判斷棧是否已滿：當(dāng)堆棧已滿時(shí)，返回 True顷级，當(dāng)堆棧未滿時(shí)凫乖，返回 False。一般只用于順序棧中插入元素和獲取當(dāng)前棧頂元素操作中。
• 插入元素（進(jìn)棧帽芽、入棧）：相當(dāng)于在線性表最后元素后面插入一個(gè)新的數(shù)據(jù)元素删掀。并改變棧頂指針 top 的指向位置。
• 刪除元素（出棧导街、退棧）：相當(dāng)于在線性表最后元素后面刪除最后一個(gè)數(shù)據(jù)元素披泪。并改變棧頂指針 top 的指向位置。
• 獲取棧頂元素：相當(dāng)于獲取線性表中最后一個(gè)數(shù)據(jù)元素搬瑰。與插入元素款票、刪除元素不同的是，該操作并不改變棧頂指針 top 的指向位置泽论。

1.1.2 堆棧的順序存儲實(shí)現(xiàn)

堆棧最簡單的實(shí)現(xiàn)方式就是借助于一個(gè)數(shù)組來描述堆棧的順序存儲結(jié)構(gòu)艾少。在 Python 中我們可以借助列表 list 來實(shí)現(xiàn)。這種采用順序存儲結(jié)構(gòu)的堆棧也被稱為 「順序椧磴玻」缚够。

image.png

約定 self.top 指向棧頂元素所在位置。

• 初始化空棧：使用列表創(chuàng)建一個(gè)空棧鹦赎，定義棧的大小 self.size谍椅，并令棧頂元素指針 self.top 指向 -1，即 self.top = -1钙姊。
• 判斷棧是否為空：當(dāng) self.top == -1 時(shí)毯辅，說明堆棧為空，返回 True煞额，否則返回 False思恐。
• 判斷棧是否已滿：當(dāng) self.top == self.size - 1，說明堆棧已滿膊毁，返回 True胀莹，否則返回返回 False。
• 獲取棧頂元素：先判斷隊(duì)列是否為空婚温，為空直接拋出異常描焰。不為空則返回 self.top 指向的棧頂元素，即 self.stack[self.top]栅螟。
• 插入元素（進(jìn)棧荆秦、入棧）：先判斷隊(duì)列是否已滿，已滿直接拋出異常力图。如果隊(duì)列未滿步绸，則在 self.stack 末尾插入新的數(shù)據(jù)元素，并令 self.top 向右移動 1 位吃媒。
• 刪除元素（出棧瓤介、退棧）：先判斷隊(duì)列是否為空吕喘，為空直接拋出異常。如果隊(duì)列不為空刑桑，則令 self.top 向左移動 1 位氯质，并返回 self.stack[self.top]。

class Stack:
    # 初始化空棧
    def __init__(self, size=100):
        self.stack = []
        self.size = size
        self.top = -1    
        
    # 判斷棧是否為空
    def is_empty(self):
        return self.top == -1
    
    # 判斷棧是否已滿
    def is_full(self):
        return self.top + 1 == self.size
    
    # 入棧操作
    def push(self, value):
        if self.is_full():
            raise Exception('Stack is full')
        else:
            self.stack.append(value)
            self.top += 1
    
    # 出棧操作
    def pop(self):
        if self.is_empty():
            raise Exception('Stack is empty')
        else:
            self.top -= 1
            self.stack.pop()
    
    # 獲取棧頂元素
    def peek(self):
        if self.is_empty():
            raise Exception('Stack is empty')
        else:
            return self.stack[self.top]

1.1.3 堆棧的鏈?zhǔn)酱鎯?shí)現(xiàn)

堆棧的順序存儲結(jié)構(gòu)保留著順序存儲分配空間的固有缺陷祠斧，即在棧滿或者其他需要重新調(diào)整存儲空間時(shí)需要移動大量元素闻察。為此，堆椓褐祝可以采用鏈?zhǔn)酱鎯Ψ绞絹韺?shí)現(xiàn)蜓陌。在 Python 中我們通過構(gòu)造鏈表節(jié)點(diǎn) Node 的方式來實(shí)現(xiàn)。這種采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的堆棧也被稱為 「鏈?zhǔn)綏吩蔑！埂?/p>

image.png

約定 self.top 指向棧頂元素所在位置钮热。

• 初始化空棧：使用列表創(chuàng)建一個(gè)空棧，并令棧頂元素指針 self.top 指向 None烛芬，即 self.top = None隧期。
• 判斷棧是否為空：當(dāng) self.top == None 時(shí)，說明堆棧為空赘娄，返回 True仆潮，否則返回 False。
• 獲取棧頂元素：先判斷隊(duì)列是否為空遣臼，為空直接拋出異常性置。不為空則返回 self.top 指向的棧頂節(jié)點(diǎn)，即 self.top.value揍堰。
• 插入元素（進(jìn)棧鹏浅、入棧）：創(chuàng)建值為 value 的鏈表節(jié)點(diǎn)，插入到鏈表頭節(jié)點(diǎn)之前屏歹，并令棧頂指針 self.top 指向新的頭節(jié)點(diǎn)隐砸。
• 刪除元素（出棧、退棧）：先判斷隊(duì)列是否為空蝙眶，為空直接拋出異常季希。如果隊(duì)列不為空，則令 self.top 鏈表移動 1 位幽纷，并返回 self.top.value式塌。

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        
class Stack:
    # 初始化空棧
    def __init__(self):
        self.top = None
    
    # 判斷棧是否為空
    def is_empty(self):
        return self.top == None
    
    # 入棧操作
    def push(self, value):
        cur = Node(value)
        cur.next = self.top
        self.top = cur
    
    # 出棧操作
    def pop(self):
        if self.is_empty():
            raise Exception('Stack is empty')
        else:
            cur = self.top
            self.top = self.top.next
            del cur
    
    # 獲取棧頂元素
    def peek(self):
        if self.is_empty():
            raise Exception('Stack is empty')
        else:
            return self.top.value

1.2 堆棧的應(yīng)用

堆棧是算法和程序中最常用的輔助結(jié)構(gòu)，其的應(yīng)用十分廣泛友浸。堆椃宄ⅲ基本應(yīng)用于兩個(gè)方面：

• 使用堆棧可以很方便的保存和取用信息尾菇，因此長被用作算法和程序中的輔助存儲結(jié)構(gòu)境析，臨時(shí)保存信息，供后面操作中使用派诬。
  例如：操作系統(tǒng)中的函數(shù)調(diào)用棧劳淆，瀏覽器中的前進(jìn)、后退功能默赂。
• 堆棧的后進(jìn)先出規(guī)則沛鸵，可以保證特定的存取順序。
  例如：翻轉(zhuǎn)一組元素的順序缆八、鐵路列車車輛調(diào)度曲掰。

二、深度優(yōu)先搜索

2.1 簡介

深度優(yōu)先搜索算法（Depth First Search）：英文縮寫為 DFS奈辰。是一種用于遍歷或搜索樹或圖的算法栏妖。該算法沿著樹的深度遍歷樹的節(jié)點(diǎn)，會盡可能深的搜索樹的分支奖恰。當(dāng)節(jié)點(diǎn) v 的所在邊都己被探尋過吊趾，搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn) v 的那條邊的起始節(jié)點(diǎn)。這一過程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止瑟啃。如果還存在未被發(fā)現(xiàn)的節(jié)點(diǎn)论泛，則選擇其中一個(gè)作為源節(jié)點(diǎn)并重復(fù)以上過程，整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被訪問為止蛹屿。
深度優(yōu)先搜索使用的是回溯思想屁奏，這種思想很適合使用「遞歸」來實(shí)現(xiàn)。而遞歸對問題的處理順序错负，遵循了「后進(jìn)先出」的規(guī)律坟瓢。所以遞歸問題的處理，需要借助「堆検」來實(shí)現(xiàn)载绿。
在深度優(yōu)先遍歷的過程中，我們需要將當(dāng)前遍歷節(jié)點(diǎn) v 的相鄰節(jié)點(diǎn)暫時(shí)存儲起來油航，以便于在回退的時(shí)候可以繼續(xù)訪問它們崭庸。遍歷到的節(jié)點(diǎn)順序符合「后進(jìn)先出」的特點(diǎn)，所以深度優(yōu)先搜索可以通過「遞歸」或者「堆椧昵簦」來實(shí)現(xiàn)怕享。

2.2 過程演示

以一個(gè)無向圖為例
用鄰接字典的方式存儲無向圖結(jié)構(gòu)，對應(yīng)結(jié)構(gòu)代碼如下：

# 定義無向圖結(jié)構(gòu)
graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D", "E"],
    "D": ["B", "C", "E", "F"],
    "E": ["C", "D"],
    "F": ["D"]
}

該無向圖的結(jié)構(gòu)如圖左所示镰踏，圖右為深度優(yōu)先搜索的遍歷路徑函筋。

image.png

其對應(yīng)的動態(tài)演示圖如下所示。

image.png

2.3 基于遞歸實(shí)現(xiàn)的深度優(yōu)先搜索

實(shí)現(xiàn)步驟：

• graph 為存儲無向圖的字典變量奠伪，visited 為標(biāo)記訪問節(jié)點(diǎn)的 set 集合變量跌帐。start 為當(dāng)前遍歷邊的開始節(jié)點(diǎn)首懈。def dfs_recursive(graph, start, visited): 為遞歸實(shí)現(xiàn)的深度優(yōu)先搜索方法。
• 將 start 標(biāo)記為已訪問谨敛，即將 start 節(jié)點(diǎn)放入 visited 中（visited.add(start)）究履。
• 訪問節(jié)點(diǎn) start，并對節(jié)點(diǎn)進(jìn)行相關(guān)操作（看具體題目要求）脸狸。
• 遍歷與節(jié)點(diǎn) start 相連并構(gòu)成邊的節(jié)點(diǎn) end最仑。
  • 如果 end 沒有被訪問過，則從 end 節(jié)點(diǎn)調(diào)用遞歸實(shí)現(xiàn)的深度優(yōu)先搜索方法炊甲，即 dfs_recursive(graph, end, visited)泥彤。

def dfs_recursive(graph, start, visited):
    # 標(biāo)記節(jié)點(diǎn)
    visited.add(start)
    # 訪問節(jié)點(diǎn)
    print(start)

    for end in graph[start]:
        if end not in visited:
            # 深度優(yōu)先遍歷節(jié)點(diǎn)
            dfs_recursive(graph, end, visited)

2.4 基于堆棧實(shí)現(xiàn)的深度優(yōu)先搜索

實(shí)現(xiàn)步驟：

• 1、start 為開始節(jié)點(diǎn)卿啡。定義 visited 為標(biāo)記訪問節(jié)點(diǎn)的 set 集合變量吟吝。定義 stack 用于存放臨時(shí)節(jié)點(diǎn)的棧結(jié)構(gòu)。
• 2牵囤、首先將起始節(jié)點(diǎn)放入棧中爸黄，并標(biāo)記訪問。即 visited = set(start)揭鳞，stack = [start]炕贵。
• 3、從 stack 中取出第一個(gè)節(jié)點(diǎn) node_u野崇。
• 4称开、訪問節(jié)點(diǎn) node_u，并對節(jié)點(diǎn)進(jìn)行相關(guān)操作（看具體題目要求）乓梨。
• 5鳖轰、遍歷與節(jié)點(diǎn) node_u 相連并構(gòu)成邊的節(jié)點(diǎn) node_v。
  • 如果 node_v 沒有被訪問過扶镀，則將 node_v 節(jié)點(diǎn)放入棧中蕴侣，并標(biāo)記訪問，即 stack.append(node_v)臭觉，visited.add(node_v)昆雀。
• 6、重復(fù)步驟 3 ~ 5蝠筑，直到 stack 為空狞膘。

def dfs_stack(graph, start):
    visited = set(start)
    stack = [start]

    while stack:
        node_u = stack.pop()
        # 訪問節(jié)點(diǎn)
        print(node_u)
        for node_v in graph[node_u]:
            if node_v not in visited:
                stack.append(node_v)
                visited.add(node_v)

三、總結(jié)

本章節(jié)首先介紹了堆棧的基礎(chǔ)知識什乙、存儲方式和應(yīng)用場景挽封，然后對深度優(yōu)先搜索作了詳細(xì)介紹，包括它的基礎(chǔ)知識和基于不同方式的實(shí)現(xiàn)過程臣镣。