Python数据结构-栈与深度优先搜索（Stack）

栈的顺序存储实现

class Stack:
    # 初始化空栈
    def __init__(self, size = 100):
        self.stack = []
        self.size = size
        self.top = -1     # 栈顶元素指向 -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.stack.pop()
            self.top -= 1
    # 获取栈顶元素
    def peek(self):
        if self.empty():
            raise Exception('Stack is empty!')
        else:
            return self.stack[self.top]

栈-先进后出

class Test:
    def test(self):
        # create a stack
        stack = []

        # add element
        # time complexity: O(1)
        stack.append(1)
        stack.append(2)
        stack.append(3)
        print(stack)      # [1,2,3]

        # get the top of stack
        # time complexity: O(1)
        stack[-1]

        # remove the top of stack
        # time complexity: O(1)
        temp = stack.pop()
        print(temp)    # 3

        # get stack length
        # time complexity: O(1)
        len(stack)

        # stack is empty?
        # time complexity: O(1)
        len(stack) == 0

        # iterate stack
        # time complexity: O(n)
        while len(stack) > 0:
            temp = stack.pop()
            print(temp)         # 2 1

if __name__ == '__main__':
    test = Test()
    test.test()

3. 堆栈的应用

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

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

练习

20. 有效的括号

输入：s = "()[]{}"
输出：true

# 方法1：使用栈
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        # 首先判断字符串的长度是否为奇数
        if len(s)%2 == 1:
            return False
        # 用栈来完成判断
        for i in s:
            if i == '(' or i == '[' or i == '{':
                stack.append(i)
            else:
                # 先判断栈是否为空
                if len(stack) == 0:
                    return False
                top = stack.pop()
                if i == ')' and top != '(':
                    return False
                elif i == ']' and top != '[':
                    return False
                elif i == '}' and top != '{':
                    return False
        # 最后看栈中元素是否为空
        if len(stack) == 0:
            return True
        else:
            return False

227. 基本计算器 II

整数除法仅保留整数部分。

输入：s = " 3+5 / 2 "
输出：5
输入：s = " 3/2 "
输出：1

class Solution:
    def calculate(self, s: str) -> int:
        # 运算符
        cal = ['+', '-', '*', '/']
        # 辅助栈
        stack = []
        index = 0
        size = len(s)
        # 默认运算,因为除了空字符串，第一个字符串肯定为数字
        op = '+'
        # 字符串遍历
        while index < size:
            # 对于空格的灵活处理
            if s[index] == ' ':
                index += 1
                continue
            # 对于数字字符的处理
            if s[index].isdigit():
                # 将字符串转化为数字
                num = ord(s[index]) - ord('0')
                # 对于连续多位数字字符串的处理
                while index + 1 < size and s[index+1].isdigit():
                    # 需要注意及时更新索引
                    index += 1
                    num = 10*num + ord(s[index]) - ord('0')
                # 得到数字之后和运算符一起压入栈中
                if op == '+':
                    stack.append(num)
                elif op == '-':
                    stack.append(0-num)
                elif op == '*':
                    num_cal = stack.pop()
                    stack.append(num_cal*num)
                # 整数除法仅保留整数部分
                elif op == '/':
                    num_cal = stack.pop()
                    stack.append(int(num_cal/num))
            # 对于运算符的处理
            elif s[index] in cal:
                op = s[index]

            index += 1
        return sum(stack)

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

# 方法1：借用一个辅助栈，同时存储两个值：当前值，当前的最小值
class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
    # 将元素压入栈
    def push(self, val: int) -> None:
        # 首先判断栈是否为空
        if len(self.stack) == 0:
            self.stack.append([val, val])
        else:
            self.stack.append([val, min(val, self.stack[-1][1])])
    # 元素弹出
    def pop(self) -> None:
       self.stack.pop()
    # 获取栈顶元素
    def top(self) -> int:
        return self.stack[-1][0]
    # 获取栈的最小值   
    def getMin(self) -> int:
        return self.stack[-1][1]

739. 每日温度

请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

# 使用一个栈
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        length = len(temperatures)
        result = [0]*length
        count = 0
        for i in range(length):
            # 当栈不为空，且栈顶索引对应的温度小于当前温度
            while stack and temperatures[stack[-1]] < temperatures[i]:
                # 索引出栈
                index = stack.pop()
                result[index] = i - index
            stack.append(i)
        return result

150. 逆波兰表达式求值

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

# 中缀表达式
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        cal = ['+', '-', '*', '/']
        for tok in tokens:
            if tok not in cal:
                stack.append(int(tok))
            else:
                a = stack.pop()
                b = stack.pop()
                if tok == '+':
                    ans = b + a
                elif tok == '-':
                    ans = b - a
                elif tok == '*':
                    ans = b * a
                elif tok == '/':
                    ans = int(b / a)
                stack.append(ans)
        return stack.pop()

394. 字符串解码

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

class Solution:
    def decodeString(self, s: str) -> str:
        stack_num = []
        stack_str = []
        s1 = ['a', 'b', 'c', 'd', 'e', 'f', 'g','h', 'i', 'j', 'k', 'l', 'm', 'n',
        'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
        num = 0
        res = ''
        for s_num in s:
            if s_num.isdigit():
                num = num*10 + int(s_num)
            elif s_num in s1:
                res += s_num
            elif s_num == '[':
                stack_num.append(num)
                stack_str.append(res)
                # 及时初始化
                num = 0
                res = ''
            elif s_num ==']':
                cur_num = stack_num.pop()
                cur_res = stack_str.pop()
                res = cur_res + cur_num * res
        return res

946. 验证栈序列

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

# 对于pushed序列，每次进行push操作之后，有两种选择：继续push、弹出
# 进行实际模拟，查看结果是否相符
class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []
        i = 0
        for p in pushed:
            stack.append(p)
            while stack and stack[-1] == popped[i]:
                stack.pop()
                i += 1
            # stack.append(p)
        # 结束的判断：新建的栈是否都为空
        return not stack

二、栈与深度优先搜索

深度优先搜索算法（Depth First Search）：英文缩写为 DFS。是一种用于遍历或搜索树或图的算法。该算法沿着树的深度遍历树的节点，会尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过，搜索将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

在深度优先遍历的过程中，我们需要将当前遍历节点 v 的相邻节点暂时存储起来，以便于在回退的时候可以继续访问它们。遍历到的节点顺序符合「后进先出」的特点，所以深度优先搜索可以通过「递归」或者「堆栈」来实现。

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

def dfs_recrusive(graph, start, visited):
    ```
    graph: 存储无向图的字典变量
    start: 表示当前遍历边的开始节点
    visited: 标记访问节点的set集合变量
    ```
    visted = set()
    visited.add(start)
    # 遍历图
    for end in graph[start]:
        if end not in visited:
            # 深度优先遍历节点
            dfs_recursive(graph, end, visited)

2.2 基于栈实现的广度优先搜索

def dfs_stack(graph, start):
    # 定义起始节点，并把起始节点进行标记并放在栈中
    visited = set(start)
    stack = [start]
    # 递归结束的条件：栈为空
    while stack:
        node_u = stack.pop()
        for node_v in graph[node_u]:
            if node_v not in visited:
                stack.append(node_v)
                visted.appedn(node_v)

200. 岛屿数量

输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1

class Solution:
    # 先定义深度优先搜索的算法
    def dfs(self, grid, i, j):
        # 计算行数和列数
        n = len(grid)
        m = len(grid[0])
        # 递归的终止条件
        if i < 0 or i >= n or j < 0 or j >= m or grid[i][j] == '0':
            return 0
        # 要及时将grid[i, j] = '1'的位置修改为'0',避免重复查找
        grid[i][j] = '0'
        # 对该点的上下左右进行检查
        self.dfs(grid, i + 1, j)
        self.dfs(grid, i, j + 1)
        self.dfs(grid, i - 1, j)
        self.dfs(grid, i, j - 1)

    def numIslands(self, grid: List[List[str]]) -> int:
        # 计数
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    # count += 1
                    self.dfs(grid, i, j)
                    count += 1
        return count

133. 克隆图

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]
解释：
图中有 4 个节点。
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""
# 深度优先算法
class Solution:
    def dfs(self, node: 'Node', visited):
        # 递归的终止条件
        if node in visited:
            return visited[node]
        clone_node = Node(node.val, [])
        # 新建复制节点 clone_node，赋值为 node.val。
        visited[node] = clone_node
        for neighbor in node.neighbors:
            clone_node.neighbors.append(self.dfs(neighbor, visited))
        return clone_node

    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return node
        # 使用字典变量 visited 存储访问过的节点，键值对为 原节点 : 新节点
        visited = dict()
        return self.dfs(node, visited)

1)实战-括号匹配

输入：(((()
输出：False

def parCheck(symbolString):
    s = Stack()
    balance = True
    index = 0
    while index < len(symbolString) and balance:
        if symbolString[index] == '(':
            s.push(symbolString[index])
        else:
            if s.isEmpty():
                balance = False
            else:
                s.pop()
        index += 1
    if balance and s.isEmpty():
        return True
    else:
        return False
print(parCheck('()(((())))'))

题目复杂化

要求判别 {{{{[[[((()))]]]}}}}

def parCheck(symbolString):
    s = Stack()
    balance = True
    index = 0
    while index < len(symbolString) and balance:
        symbol = symbolString[index]
        if symbol in '({[':
            s.push(symbolString[index])
        else:
            if s.isEmpty():
                balance = False
            else:
                # s.pop()
                top = s.pop()
                if not matches(top, symbol):
                    balance = False
        index += 1
    if balance and s.isEmpty():
        return True
    else:
        return False

def matches(open, close):
    opens = "([{"
    closes = ")]}"
    return opens.index(open) == closes.index(close)

print(parCheck('()(((([{(}]))))'))

2)十进制转二进制

def divideBy2(decNumber):
    stack = Stack()

    while decNumber > 0:
        rem = decNumber % 2   # 求余数
        stack.push(rem)
        decNumber //= 2       # 取整数
    
    binnumber = ''
    while not stack.isEmpty():
        binnumber += str(stack.pop())
    
    return binnumber
print(divideBy2(5))

进阶：十进制转16以下任意进制

def divideBynum(decNumber, num):
    stack = Stack()
    digits = '0123456789ABCDEF'

    while decNumber > 0:
        rem = decNumber % num   # 求余数
        stack.push(rem)
        decNumber //= num       # 取整数
    
    binnumber = ''
    while not stack.isEmpty():
        binnumber += digits[stack.pop()]
    
    return binnumber
print(divideBynum(5, 16))

3)表达式转换

中缀表达式 A + B; A + B * C； (A + B) * C
前缀表达式 + AB ; + A * BC ； * +ABC
后缀表达式 AB + ; A B C * +； AB + C*
在中缀表达式中必须有的括号，在前缀和后缀表达式中消失了

思路
1 将中缀表达式转换为全括号的形式
2 将所有的操作符移动到子表达式所在的左括号（前缀）或者右括号（后缀）处，再删除其它所有的括号

def infixToPostfix(infixexpr):
    # 记录操作符的优先级
    prec = {}
    prec['*'] = 3
    prec['/'] = 3
    prec['+'] = 2
    prec['-'] = 2
    prec['('] = 1

    opStack = Stack()
    postfixList = []
    tokenList = infixexpr.split()    # 将表达式解析为列表
    # print(tokenList)

    for token in tokenList:
        if token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or token in '0123456789':
            postfixList.append(token)
        elif token == '(':
            opStack.push(token)
        elif token == ')':
            topToken = opStack.pop()
            while topToken != '(':
                postfixList.append(topToken)
                topToken = opStack.pop()
        else:
            while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]):
                postfixList.append(opStack.pop())
            opStack.push(token)

    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    
    return " ".join(postfixList)       # 合成后缀表达式字符串

a = '( A + B ) * C'            # 输入字符必须用空格分开，不然无法split
print(infixToPostfix(a))

计算后序表达式

def compute1(s):
    operandStack = Stack()
    splitToken = s.split()

    for token in splitToken:
        if token in '0123456789':
            operandStack.push(int(token))
        else:
            a = operandStack.pop()
            b = operandStack.pop()
            operandStack.push(compute2(token, a, b))
    return operandStack.pop()
            
def compute2(token, a,b):
    if token == '+':
        c = a+b
    elif token == '-':
        c = a-b
    elif token == '*':
        c = a * b
    else:
        c = a/b
    return c

print(compute1('1 2 + 1 *'))     # 只能传入十以内数进行计算