Stack

Jessica Gracewell2023-09-282023-09-28

Stack

一、栈的基本概念与特性

栈（Stack）是一种特殊的线性数据结构，其只允许在一端（通常称为“栈顶”）进行数据的插入或删除操作。栈的特点是“后入先出”（LIFO, Last In First Out），即最后加入的元素最先取出。可以想象为一摞盘子，想要取出最底下的盘子，就需要先移开上面的所有盘子。

栈结构通常用于实现临时保存数据，然后依次再弹出来，常用于深度优先搜索（DFS）。而队列结构一般用于广度优先搜索（BFS），表现为一层一层的搜索。

栈的操作：
push()：元素入栈，添加至栈顶
pop()：栈顶元素出栈
peek()：访问栈顶元素，不改变栈结构
is_empty()：判断栈是否为空
Python实现：
在Python中，没有内置的栈类，但可以用List来模拟栈的操作。

stack = []  # 初始化栈
stack.append(1)  # 元素入栈
peek = stack[-1]  # 访问栈顶元素
pop = stack.pop()  # 元素出栈
is_empty = len(stack) == 0  # 判断是否为空

二、栈的实现方式

栈可基于数组或链表实现，其中，数组实现简单直观，链表实现则更加灵活。

基于链表的实现：
基于链表实现的栈，通常将链表的头节点视为栈顶。入栈操作即为链表头部插入节点，而出栈操作则是删除头节点。

class ListNode:
    """链表节点"""
    def __init__(self, val: int):
        self.val = val  # 节点值
        self.next = None  # 指向下一个节点的指针


class LinkedListStack:
    """基于链表实现的栈"""
    
    def __init__(self):
        """初始化一个空栈"""
        self.__peek = None  # 栈顶元素
        self.__size = 0  # 栈的大小
    
    def size(self) -> int:
        """获取栈的大小"""
        return self.__size  # 返回栈中元素的数量
    
    def is_empty(self) -> bool:
        """判断栈是否为空"""
        return not self.__peek  # 当栈顶元素为None时，栈为空，返回True
    
    def push(self, val: int):
        """元素入栈"""
        node = ListNode(val)  # 创建一个新的链表节点
        node.next = self.__peek  # 新节点的下一个节点为当前的栈顶元素
        self.__peek = node  # 更新栈顶元素为新节点
        self.__size += 1  # 栈的大小加1
    
    def pop(self) -> int:
        """元素出栈"""
        if self.is_empty():
            raise IndexError("栈为空，无法出栈")  # 如果栈为空，抛出异常
        num = self.__peek.val  # 获取栈顶元素的值
        self.__peek = self.__peek.next  # 更新栈顶元素为下一个节点
        self.__size -= 1  # 栈的大小减1
        return num  # 返回出栈元素的值
    
    def peek(self) -> int:
        """查看栈顶元素"""
        if self.is_empty():
            raise IndexError("栈为空，无法访问栈顶元素")  # 如果栈为空，抛出异常
        return self.__peek.val  # 返回栈顶元素的值

基于数组的实现：
基于数组实现的栈，通常将数组的尾部视为栈顶。入栈和出栈操作分别对应在数组尾部添加元素与删除元素。

class ArrayStack:
    """基于数组实现的栈"""
    
    def __init__(self):
        """初始化一个空栈"""
        self.__stack = []  # 使用列表来存储栈元素
    
    def size(self) -> int:
        """获取栈的大小"""
        return len(self.__stack)  # 返回栈中元素的数量
    
    def is_empty(self) -> bool:
        """判断栈是否为空"""
        return len(self.__stack) == 0  # 当栈中无元素时返回True
    
    def push(self, item: int):
        """元素入栈"""
        self.__stack.append(item)  # 使用列表的append方法来添加元素到栈顶
    
    def pop(self) -> int:
        """元素出栈"""
        if self.is_empty():
            raise IndexError("栈为空，无法出栈")  # 如果栈为空，抛出异常
        return self.__stack.pop()  # 使用列表的pop方法来移除栈顶元素
    
    def peek(self) -> int:
        """查看栈顶元素"""
        if self.is_empty():
            raise IndexError("栈为空，无法访问栈顶元素")  # 如果栈为空，抛出异常
        return self.__stack[-1]  # 返回列表的最后一个元素，即栈顶元素

这两种实现方式各有优缺点，基于数组的实现在入栈与出栈操作上通常具有更高的平均效率，但可能会有空间浪费。而基于链表的实现则可以提供更加稳定和灵活的效率表现，但空间占用可能更大。

三、栈的应用实例

栈的应用非常广泛，下面我们将通过几个具体的例子来展示如何使用栈来解决实际问题。

最小栈的实现：
最小栈要求能在常数时间内检索到最小元素。我们可以通过两个栈来实现，一个正常的栈用来存储所有的元素，另一个“最小栈”用来存储当前栈中的最小元素。

class MinStack:
    def __init__(self):
        # 初始化两个栈，一个用于存储数据，另一个用于存储当前最小值
        self.stack = []
        self.min_stack = []

    def push(self, x: int) -> None:
        # 元素x入栈
        self.stack.append(x)
        # 将x与最小栈的栈顶元素比较，将较小值入最小栈
        if not self.min_stack or x < self.min_stack[-1]:
            self.min_stack.append(x)
        else:
            self.min_stack.append(self.min_stack[-1])

    def pop(self) -> None:
        # 出栈操作，两个栈同时出栈
        if self.stack:
            self.stack.pop()
            self.min_stack.pop()

    def top(self) -> int:
        # 获取栈顶元素，如果栈为空，返回None
        return None if not self.stack else self.stack[-1]

    def get_min(self) -> int:
        # 获取当前栈的最小值，如果最小栈为空，返回None
        return None if not self.min_stack else self.min_stack[-1]

逆波兰表达式的求值
逆波兰表达式是一种没有括号的算数表达式，我们可以通过栈来进行求值。

def eval_rpn(tokens: list[str]) -> int:
    # 初始化一个栈
    stack = []
    for token in tokens:
        if token in "+-*/":
            # 遇到运算符时，弹出栈顶的两个元素进行运算，再将结果入栈
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(int(a / b))  # 注意：python中负数除法的取整操作和其他语言可能不同
        else:
            # 遇到数字时，直接入栈
            stack.append(int(token))
    return stack[0]  # 栈顶元素即为逆波兰表达式的值

字符串解码
通过栈可以辅助实现复杂的字符串解码操作。

def decode_string(s: str) -> str:
    stack = []  # 初始化一个栈
    cur_num = 0  # 当前数字
    cur_str = ''  # 当前字符串
    for c in s:
        if c == '[':
            # 遇到'['，将当前数字和字符串入栈，并重置
            stack.append((cur_num, cur_str))
            cur_num = 0
            cur_str = ''
        elif c == ']':
            # 遇到']'，出栈，与当前字符串拼接
            last_num, last_str = stack.pop()
            cur_str = last_str + last_num * cur_str
        elif c.isdigit():
            # 计算数字的值
            cur_num = cur_num * 10 + int(c)
        else:
            # 拼接字符串
            cur_str += c
    return cur_str  # 返回最终解码的字符串

四、深度优先搜索与栈

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

深度优先搜索模板

def dfs(root):
    if not root:
        return
    visited = set()  # 记录已访问的节点
    stack = [root]   # 初始化栈
    while stack:
        node = stack.pop()  # 弹出栈顶元素
        if node in visited:  # 如果节点已访问，跳过
            continue
        visited.add(node)  # 标记为已访问
        for neighbor in node.neighbors:  # 将邻居节点入栈
            if neighbor not in visited:
                stack.append(neighbor)

二叉树的中序遍历

def inorder_traversal(root):
    res = []  # 存放遍历结果
    stack = []  # 初始化栈
    while stack or root:
        while root:
            stack.append(root)  # 当前节点入栈
            root = root.left  # 移动到左子节点
        root = stack.pop()  # 弹出栈顶元素
        res.append(root.val)  # 访问节点
        root = root.right  # 移动到右子节点
    return res

岛屿数量

def num_islands(grid):
    if not grid:
        return 0
    count = 0  # 岛屿数量
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':  # 发现一个岛屿
                stack = [(i, j)]  # 将岛屿的一个点入栈
                while stack:  # 深度优先遍历岛屿的所有点
                    r, c = stack.pop()  # 弹出栈顶元素
                    if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] == '1':
                        grid[r][c] = '0'  # 标记为已访问
                        # 将相邻的陆地入栈
                        stack.extend([(r-1, c), (r+1, c), (r, c-1), (r, c+1)])
                count += 1  # 岛屿数量加1
    return count

五、实现栈及其选择

在某些编程语言中，我们可以直接使用内置的栈类。但在其他一些语言中，我们可能需要自己实现栈。根据具体的应用场景和需求，我们可以选择基于数组或链表来实现栈。

基于数组的栈实现：
使用数组实现栈时，我们将数组的尾部视为栈顶。这种实现方法的优势在于其访问元素的效率较高，并且入栈、出栈操作的平均时间复杂度较低。

class ArrayStack:
    def __init__(self):
        # 初始化数组
        self.stack = []

    def push(self, item: int):
        # 元素入栈
        self.stack.append(item)

    def pop(self) -> int:
        # 元素出栈
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self.stack.pop()

    def peek(self) -> int:
        # 访问栈顶元素
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self.stack[-1]

    def is_empty(self) -> bool:
        # 判断栈是否为空
        return not bool(self.stack)

    def size(self) -> int:
        # 返回栈的大小
        return len(self.stack)

基于链表的栈实现
使用链表实现栈时，我们通常将链表的头部视为栈顶。这种实现方法的优势在于其动态的内存分配，不会有数组扩容带来的时间复杂度问题。

class ListNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None

class LinkedListStack:
    def __init__(self):
        self.head = None

    def push(self, val: int):
        # 元素入栈
        new_node = ListNode(val)
        new_node.next = self.head
        self.head = new_node

    def pop(self) -> int:
        # 元素出栈
        if self.is_empty():
            raise IndexError("pop from empty stack")
        val = self.head.val
        self.head = self.head.next
        return val

    def peek(self) -> int:
        # 访问栈顶元素
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self.head.val

    def is_empty(self) -> bool:
        # 判断栈是否为空
        return self.head is None

实现选择
基于数组和基于链表的栈实现各有优势。基于数组的实现访问元素更快，且在大多数情况下效率较高；而基于链表的实现具有更好的动态内存分配能力。在实际应用中，我们应该根据具体的需求和场景来选择合适的实现方式。
六、栈的应用案例
栈这一数据结构在很多实际场景中都有着广泛的应用，比如浏览器的前进后退、程序调用的上下文管理等。下面我们将通过几个实际的例子来具体讨论栈的应用。

浏览器的前进后退
我们可以用两个栈来实现浏览器的前进和后退功能。当用户打开一个新的网页时，将当前页面压入后退栈，并清空前进栈。当用户点击后退时，将当前页面压入前进栈，并从后退栈中弹出上一个页面。点击前进时则相反。

class Browser:
    def __init__(self):
        self.forward_stack = []
        self.backward_stack = []
        self.current_page = 'homepage'

    def open(self, url):
        print(f"Open new url {url}, clear forward stack")
        self.backward_stack.append(self.current_page)
        self.current_page = url
        self.forward_stack.clear()

    def backward(self):
        if not self.backward_stack:
            print("Cannot go backward")
            return
        self.forward_stack.append(self.current_page)
        self.current_page = self.backward_stack.pop()
        print(f"Go backward to {self.current_page}")

    def forward(self):
        if not self.forward_stack:
            print("Cannot go forward")
            return
        self.backward_stack.append(self.current_page)
        self.current_page = self.forward_stack.pop()
        print(f"Go forward to {self.current_page}")

括号匹配

括号匹配问题是栈的一个经典应用，我们可以用栈来实现括号匹配算法。遇到开括号则入栈，遇到闭括号则出栈并进行匹配。

def is_valid_parentheses(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in mapping.values():  # 开括号，入栈
            stack.append(char)
        elif char in mapping.keys():  # 闭括号，出栈并匹配
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            return False
    return not stack  # 如果栈为空，则全部匹配成功

数学表达式求值

栈也可以用于求解数学表达式的值。我们可以使用两个栈，一个用于存储操作数，另一个用于存储运算符。当遇到一个数时，我们将其压入操作数栈；当遇到一个运算符时，我们从操作数栈中弹出两个数进行计算，然后将结果压回操作数栈。

def calculate_expression(expression: str) -> int:
    num_stack = []
    op_stack = []
    i = 0
    while i < len(expression):
        if expression[i].isdigit():  # 数字，入操作数栈
            j = i
            while j < len(expression) and expression[j].isdigit():
                j += 1
            num_stack.append(int(expression[i:j]))
            i = j
        elif expression[i] in "+-*/":  # 运算符，入运算符栈
            while op_stack and op_stack[-1] in "+-*/":
                num2 = num_stack.pop()
                num1 = num_stack.pop()
                op = op_stack.pop()
                num_stack.append(calculate(num1, num2, op))
            op_stack.append(expression[i])
            i += 1
        elif expression[i] == ' ':
            i += 1
        else:
            raise ValueError(f"Invalid character {expression[i]}")
    while op_stack:  # 计算剩余的运算符和操作数
        num2 = num_stack.pop()
        num1 = num_stack.pop()
        op = op_stack.pop()
        num_stack.append(calculate(num1, num2, op))
    return num_stack[0]

def calculate(num1: int, num2: int, op: str) -> int:
    if op == '+':
        return num1 + num2
    elif op == '-':
        return num1 - num2
    elif op == '*':
        return num1 * num2
    elif op == '/':
        return num1 // num2

七、总结与展望

通过以上的讨论与分析，我们可以看到栈这一数据结构在解决实际问题时的巨大作用。栈的先入后出（LIFO）特性使其在处理具有层次结构的数据时变得尤为有用。

栈的特性与应用
栈的基本特性是后入先出（LIFO），即最后入栈的元素最先出栈。这一特性使得栈在很多应用场景中都能派上用场，例如函数调用、表达式求值、括号匹配等。通过合适的数据结构设计和算法实现，我们可以利用栈来解决这些问题，使得代码更加简洁、易读和高效。
栈的实现
栈可以通过数组或链表来实现。数组实现的优点是访问速度快，适合元素数量固定的场景；而链表实现则更加灵活，适合元素数量不确定的场景。在实际应用中，我们应该根据具体需求选择合适的实现方式。
栈的未来发展
随着计算机科学的发展，栈作为一种基础的数据结构，其在算法设计和问题解决中的作用将会越来越明显。未来，我们可以期待更多的算法和数据结构会以栈为基础而发展，同时，栈也会以更加高效、灵活的形式存在于各种应用和系统中。

学习建议
对于学习栈这一数据结构的人来说，理解其基本原理和操作是基础，但更重要的是要学会如何将理论应用到实际问题中去。通过大量的实践和编程练习，掌握栈在实际开发中的应用，是深入学习和理解栈的关键

# 最后，让我们通过Python代码来演示一个简单的栈应用：反转字符串
class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def is_empty(self):
        return len(self.items) == 0


def reverse_string(s: str) -> str:
    stack = Stack()
    for char in s:  # 将字符串中的每个字符压入栈中
        stack.push(char)

    reversed_str = []
    while not stack.is_empty():  # 当栈不为空时，依次弹出栈顶元素
        reversed_str.append(stack.pop())
        
    return ''.join(reversed_str)  # 将字符列表连接成字符串

# 测试反转字符串函数
s = "Hello, World!"
print(reverse_string(s))  # 输出：!dlroW ,olleH