参考链接：https://github.com/itcharge/LeetCode-Py

一、堆栈基础知识

堆栈（Stack）：简称栈。是一种线性表数据结构，它只允许在表的一端进行插入和删除。其中，允许插入和删除的一端称为 「栈顶（top）」，另一端称为 「栈底（bottom）」，表中没有任何数据元素称为 「空栈」。
基本操作（插入和删除）：

• 插入操作又称为「入栈」或者「进栈」。

• 删除操作又称为「出栈」或者「退栈」。

  
  
  image.png

1.1 堆栈的顺序存储与链式存储

和线性表类似，栈有两种存储表示方法：「顺序栈」 和 「链式栈」。
「顺序栈」：即堆栈的顺序存储结构。利用一组地址连续的存储单元依次存放自栈底到栈顶的元素，同时使用指针 top 指示栈顶元素在顺序栈中的位置。
「链式栈」：即堆栈的链式存储结构。利用单链表的方式来实现堆栈。栈中元素按照插入顺序依次插入到链表的第一个节点之前，并使用栈顶指针 top 指示栈顶元素，top 永远指向链表的头节点位置。

1.1.1 堆栈的基本操作

栈作为一种线性表来说，理论上应该具备线性表所有的操作特性，但由于「后进先出」的特殊性，所以针对栈的操作进行了一些变化。尤其是插入操作和删除操作，改为了入栈（push）和出栈（pop）。

• 初始化空栈：创建一个空栈，定义栈的大小 size，以及栈顶元素指针 top。
• 判断栈是否为空：当堆栈为空时，返回 True。当堆栈不为空时，返回 False。一般只用于栈中删除操作和获取当前栈顶元素操作中。
• 判断栈是否已满：当堆栈已满时，返回 True，当堆栈未满时，返回 False。一般只用于顺序栈中插入元素和获取当前栈顶元素操作中。
• 插入元素（进栈、入栈）：相当于在线性表最后元素后面插入一个新的数据元素。并改变栈顶指针 top 的指向位置。
• 删除元素（出栈、退栈）：相当于在线性表最后元素后面删除最后一个数据元素。并改变栈顶指针 top 的指向位置。
• 获取栈顶元素：相当于获取线性表中最后一个数据元素。与插入元素、删除元素不同的是，该操作并不改变栈顶指针 top 的指向位置。

1.1.2 堆栈的顺序存储实现

堆栈最简单的实现方式就是借助于一个数组来描述堆栈的顺序存储结构。在 Python 中我们可以借助列表 list 来实现。这种采用顺序存储结构的堆栈也被称为 「顺序栈」。

image.png

约定 self.top 指向栈顶元素所在位置。

• 初始化空栈：使用列表创建一个空栈，定义栈的大小 self.size，并令栈顶元素指针 self.top 指向 -1，即 self.top = -1。
• 判断栈是否为空：当 self.top == -1 时，说明堆栈为空，返回 True，否则返回 False。
• 判断栈是否已满：当 self.top == self.size - 1，说明堆栈已满，返回 True，否则返回返回 False。
• 获取栈顶元素：先判断队列是否为空，为空直接抛出异常。不为空则返回 self.top 指向的栈顶元素，即 self.stack[self.top]。
• 插入元素（进栈、入栈）：先判断队列是否已满，已满直接抛出异常。如果队列未满，则在 self.stack 末尾插入新的数据元素，并令 self.top 向右移动 1 位。
• 删除元素（出栈、退栈）：先判断队列是否为空，为空直接抛出异常。如果队列不为空，则令 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 堆栈的链式存储实现

堆栈的顺序存储结构保留着顺序存储分配空间的固有缺陷，即在栈满或者其他需要重新调整存储空间时需要移动大量元素。为此，堆栈可以采用链式存储方式来实现。在 Python 中我们通过构造链表节点 Node 的方式来实现。这种采用链式存储结构的堆栈也被称为 「链式栈」。

image.png

约定 self.top 指向栈顶元素所在位置。

• 初始化空栈：使用列表创建一个空栈，并令栈顶元素指针 self.top 指向 None，即 self.top = None。
• 判断栈是否为空：当 self.top == None 时，说明堆栈为空，返回 True，否则返回 False。
• 获取栈顶元素：先判断队列是否为空，为空直接抛出异常。不为空则返回 self.top 指向的栈顶节点，即 self.top.value。
• 插入元素（进栈、入栈）：创建值为 value 的链表节点，插入到链表头节点之前，并令栈顶指针 self.top 指向新的头节点。
• 删除元素（出栈、退栈）：先判断队列是否为空，为空直接抛出异常。如果队列不为空，则令 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 堆栈的应用

堆栈是算法和程序中最常用的辅助结构，其的应用十分广泛。堆栈基本应用于两个方面：

• 使用堆栈可以很方便的保存和取用信息，因此长被用作算法和程序中的辅助存储结构，临时保存信息，供后面操作中使用。
  例如：操作系统中的函数调用栈，浏览器中的前进、后退功能。
• 堆栈的后进先出规则，可以保证特定的存取顺序。
  例如：翻转一组元素的顺序、铁路列车车辆调度。

二、深度优先搜索

2.1 简介

深度优先搜索算法（Depth First Search）：英文缩写为 DFS。是一种用于遍历或搜索树或图的算法。该算法沿着树的深度遍历树的节点，会尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过，搜索将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
深度优先搜索使用的是回溯思想，这种思想很适合使用「递归」来实现。而递归对问题的处理顺序，遵循了「后进先出」的规律。所以递归问题的处理，需要借助「堆栈」来实现。
在深度优先遍历的过程中，我们需要将当前遍历节点 v 的相邻节点暂时存储起来，以便于在回退的时候可以继续访问它们。遍历到的节点顺序符合「后进先出」的特点，所以深度优先搜索可以通过「递归」或者「堆栈」来实现。

2.2 过程演示

以一个无向图为例
用邻接字典的方式存储无向图结构，对应结构代码如下：

# 定义无向图结构
graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D", "E"],
    "D": ["B", "C", "E", "F"],
    "E": ["C", "D"],
    "F": ["D"]
}

该无向图的结构如图左所示，图右为深度优先搜索的遍历路径。

image.png

其对应的动态演示图如下所示。

image.png

2.3 基于递归实现的深度优先搜索

实现步骤：

• graph 为存储无向图的字典变量，visited 为标记访问节点的 set 集合变量。start 为当前遍历边的开始节点。def dfs_recursive(graph, start, visited): 为递归实现的深度优先搜索方法。
• 将 start 标记为已访问，即将 start 节点放入 visited 中（visited.add(start)）。
• 访问节点 start，并对节点进行相关操作（看具体题目要求）。
• 遍历与节点 start 相连并构成边的节点 end。
  • 如果 end 没有被访问过，则从 end 节点调用递归实现的深度优先搜索方法，即 dfs_recursive(graph, end, visited)。

def dfs_recursive(graph, start, visited):
    # 标记节点
    visited.add(start)
    # 访问节点
    print(start)

    for end in graph[start]:
        if end not in visited:
            # 深度优先遍历节点
            dfs_recursive(graph, end, visited)

2.4 基于堆栈实现的深度优先搜索

实现步骤：

• 1、start 为开始节点。定义 visited 为标记访问节点的 set 集合变量。定义 stack 用于存放临时节点的栈结构。
• 2、首先将起始节点放入栈中，并标记访问。即 visited = set(start)，stack = [start]。
• 3、从 stack 中取出第一个节点 node_u。
• 4、访问节点 node_u，并对节点进行相关操作（看具体题目要求）。
• 5、遍历与节点 node_u 相连并构成边的节点 node_v。
  • 如果 node_v 没有被访问过，则将 node_v 节点放入栈中，并标记访问，即 stack.append(node_v)，visited.add(node_v)。
• 6、重复步骤 3 ~ 5，直到 stack 为空。

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

    while stack:
        node_u = stack.pop()
        # 访问节点
        print(node_u)
        for node_v in graph[node_u]:
            if node_v not in visited:
                stack.append(node_v)
                visited.add(node_v)

三、总结

本章节首先介绍了堆栈的基础知识、存储方式和应用场景，然后对深度优先搜索作了详细介绍，包括它的基础知识和基于不同方式的实现过程。