堆栈（Stack）：一种抽象线性表数据结构，允许在表的一端按照先入后出（FIFO）的方式进行插入和删除操作。
    计算机中的函数调用过程也是符合“栈”的“后进先出”的规律。父函数调用子函数是，子函数入栈，等子函数执行完毕时出栈接着执行父函数。

    括号匹配是“栈”的经典应用。

    1. 按照正反括号进行配对，正括号入栈，反括号出栈并且匹配。
    2. 能匹配上就顺利出栈，不能匹配说明是无效括号串。

    3. 最后所有括号都顺利匹配出栈（栈空）就说明是合法括号串。

      1. class Solution:
      2.  def isValid(self, s: str) -> bool:
      3.      if len(s) % 2 == 1:
      4.          return False
      5.      parentheses = {'(':')', '[':']', '{':'}'}
      7.      stack = []
      8.      for ch in s:
      9.          if ch in parentheses.keys():
      10.              stack.append(ch)
      11.          else:
      12.              if ch in parentheses.values() and len(stack) > 0 and ch == parentheses.get(stack[-1]):
      13.                  stack.pop()
      14.              else:
      15.                  return False
      17.      return len(stack) == 0

    实现图的深拷贝。DFS和BFS都可以对图进行遍历，使用DFS的方式实现深拷贝。

    1. """
    2. # Definition for a Node.
    3. class Node:
    4.     def __init__(self, val = 0, neighbors = None):
    5.         self.val = val
    6.         self.neighbors = neighbors if neighbors is not None else []
    7. """
    9. class Solution:
    10.     def dfs(self, node, clone):
    11.         if node in clone:
    12.             return clone[node]
    14.         new_node = Node(node.val, [])
    15.         clone[node] = new_node
    16.         for neighbor in node.neighbors:
    17.             new_node.neighbors.append(self.dfs(neighbor, clone))
    19.         return new_node
    21.     def cloneGraph(self, node: 'Node') -> 'Node':
    22.         if node is None:
    23.             return None
    24.         clone = {}
    25.         return self.dfs(node, clone)