栈：先进后出的数据结构

一、栈的基本定义

栈(Stack)是一种线性数据结构，它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据(最后入栈的数据最先弹出)。栈可以简单地看做是一种限制性的单向链表，它限制了只能在链表的一端进行插入和删除操作，这一端称之为栈顶(top)，另一端称之为栈底(bottom)。

二、栈的操作

对栈的操作主要有两个：压入和弹出。在栈中压入元素的操作称为push，而弹出元素的操作称为pop。

class Stack:
    def __init__(self):
        self.stack = []

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

    def pop(self):
        # 弹出元素
        if not self.is_empty():
            return self.stack.pop()

    def peek(self):
        # 返回栈顶元素
        if not self.is_empty():
            return self.stack[-1]

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

    def is_empty(self):
        # 判断栈是否为空
        return len(self.stack) == 0

三、栈的应用

1. 表达式求值

栈可以用来求表达式的值，由于表达式的优先级问题，我们需要把中缀表达式转化为后缀表达式。比如a+b*c-d，可以转化为abc*+d-

def evaluate_postfix_expression(expression: str) -> int:
    stack = Stack()
    for i in expression:
        if i.isdigit():
            stack.push(i)
        else:
            num2, num1 = int(stack.pop()), int(stack.pop())
            if i == '+':
                stack.push(num1 + num2)
            elif i == '-':
                stack.push(num1 - num2)
            elif i == '*':
                stack.push(num1 * num2)
            elif i == '/':
                stack.push(num1 / num2)
    return stack.pop()

2. 括号匹配

栈也可以用来匹配括号，比如，判断括号序列是否合法，(()())合法，(()非法。

def is_valid_brackets(s: str) -> bool:
    stack = Stack()
    for i in s:
        if i == '(':
            stack.push(i)
        elif i == ')':
            if stack.is_empty():
                return False
            else:
                stack.pop()
    return stack.is_empty()

3. 函数调用的系统栈

函数的调用关系也可以看做是一种栈的结构，每当一个函数被调用时，系统就会在栈顶记录下来当前的函数调用信息，同时栈指针上移一位，而在一个函数执行完以后，栈顶的函数返回并弹出，此时系统将把执行权向下移交给当前的栈顶函数。

四、栈的优缺点

1. 优点

1. 栈能够保证基本操作的时间复杂度为O(1)。

2. 栈是一种先进后出的数据结构，特别适用于需要倒序输出或倒序执行操作的场景。

3. 栈可以解决一些复杂的问题，比如函数调用等。

2. 缺点

1. 栈的空间固定，一旦栈满就不能再去push数据，容易产生栈溢出的问题。

2. 栈的操作受限，只有栈顶元素可以进行操作，其他位置的元素不能进行操作。

3. 栈不支持随机访问，只能从栈顶往下遍历。

五、总结

本文详细介绍了栈的定义、操作、应用及其优缺点，栈是一种非常重要和实用的数据结构，广泛应用于计算机科学领域。