数据结构与算法之美

数据结构与算法之美 | 栈

栈结构：后进者先出，先进者后出
栈是一种“操作受限”的线性表
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，这时我们就应该首选“栈”这种数据结构

栈的实现

使用数组实现：顺序栈

class ArrayStack:
    """使用数组实现一个顺序栈"""

    def __init__(self):
        '''
        初始化顺序栈

        参数：
            无

        返回值：
            无
        '''
        
        self.items = []

    def push(self, item):
        '''
        入栈操作

        参数：
            item (任意类型): 待入栈的值

        返回值：
            无
        '''
        self.items.append(item)

    def pop(self):
        '''
        出栈操作

        参数：
            无

        返回值：
            待出栈的值
        '''
        if not self.is_empty():
            return self.items.pop()

    def is_empty(self):
        '''
        检查栈是否为空

        参数：
            无

        返回值：
            bool: 如果栈为空则返回True，否则返回False
        '''
        return len(self.items) == 0

使用链表实现：链式栈

class Node:
    '''维护链表节点'''
    def __init__(self, value):
        '''
        初始化链表节点

        参数：
            value (任意类型): 节点的值

        返回值：
            无
        '''
        # 节点的值
        self.value = value
        # 指向下一个节点的指针
        self.next = None

class Stack:
    '''进行出栈或入栈操作'''
    def __init__(self):
        '''
        初始化栈

        参数：
            无

        返回值：
            无
        '''
        # 栈顶节点
        self.top = None

    def push(self, value):
        '''
        入栈操作

        参数：
            value (任意类型): 要入栈的值

        返回值：
            无
        '''
        if self.top is None:
            self.top = Node(value)
        else:
            # 创建新节点
            new_node = Node(value)
            # 将新节点指向当前的栈顶节点
            new_node.next = self.top
            # 更新栈顶节点为新节点
            self.top = new_node

    def pop(self):
        '''
        出栈操作

        参数：
            无

        返回值：
            出栈的节点的值
        '''
        if self.top is None:
            return None
        else:
            # 弹出栈顶节点
            popped_node = self.top
            # 更新栈顶节点为下一个节点
            self.top = self.top.next
            # 将弹出的节点从链表中断开
            popped_node.next = None
            # 返回弹出节点的值
            return popped_node.value

栈的应用

函数调用栈

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧¹入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

def main():
    '''
    主函数，用于执行程序的主要逻辑

    参数：
        无

    返回值：
        int: 表示程序执行结果的返回值
    '''
    a = 1
    ret = 0
    res = 0

    # 调用add函数，将返回值赋给ret变量
    ret = add(3, 5)

    # 计算a和ret的和，将结果赋给res变量
    res = a + ret

    # 打印res的值
    print(res)

    return 0


def add(x, y):
    '''
    将两个数字相加

    参数：
        x (int): 第一个数字
        y (int): 第二个数字

    返回值：
        int: 两个数字的和
    '''
    sum = 0

    # 计算x和y的和，将结果赋给sum变量
    sum = x + y

    return sum


if __name__ == '__main__':
    # 调用main函数
    main()

能否使用其他数据结构实现函数调用功能？

虽然其他数据结构也可以用来保存临时变量，但是它们的实现可能不如栈那么高效。
例如，使用链表来保存上下文信息，需要在插入和删除元素时遍历链表，时间复杂度为O(n)，而使用栈的时间复杂度为O(1)。因此，栈是最常用的函数调用栈的实现方式。

表达式求值

编译器通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。

我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；
当遇到运算符，就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；
如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

检查括号是否匹配

假设表达式中只包含三种括号：

圆括号 ()
方括号[]
花括号{}

它们可以任意嵌套。比如，{[] ()[{}]}或[{()}([])]等都为合法格式，而{[}()]或[({)]为不合法的格式。

那么如何检查括号是否合法？

我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。
当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如 ( 跟 ) 匹配，[跟]匹配，{跟}匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。
当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明有未匹配的左括号，为非法格式。

实现浏览器的前进和后退功能

使用两个栈，X 和 Y。
我们把首次浏览的页面依次压入栈 X，当点击后退按钮时，再依次从栈 X 中出栈，并将出栈的数据依次放入栈 Y。当我们点击前进按钮时，我们依次从栈 Y 中取出数据，放入栈 X 中。
当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了。