Python 栈

1. 什么是栈？

栈（Stack）是一种常用的数据结构，它是一种只能在一端（称为栈顶）进行插入和删除操作的线性表。栈是一种后进先出（Last In First Out，LIFO）的数据结构，类似于我们生活中常见的一摞盘子，后放进去的盘子先被拿出来。

栈只允许在栈顶进行插入和删除操作。当我们向栈中插入一个新元素时，它将被放置在栈顶，而栈顶的元素会依次向下移动。同样地，当我们从栈中删除一个元素时，它会从栈顶被弹出，栈顶的元素会上移。

2. 栈的操作

栈提供了以下几种基本操作：

push(item): 将元素item压入栈顶
pop(): 弹出栈顶元素并返回
peek(): 返回栈顶元素，但不弹出
is_empty(): 判断栈是否为空
size(): 返回栈中元素的个数

3. 栈的实现

在 Python 中，我们可以使用列表（List）来实现栈。列表是一种非常常用的数据结构，它可以容纳不同类型的元素，并且支持动态大小调整。

让我们通过一个示例代码来实现一个简单的栈类：

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

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

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

    def pop(self):
        if self.is_empty():
            return None
        return self.items.pop()

    def peek(self):
        if self.is_empty():
            return None
        return self.items[-1]

    def size(self):
        return len(self.items)

以上代码定义了一个 Stack 类，它使用一个列表 self.items 作为内部存储结构。通过列表的 append() 方法实现元素的入栈操作，pop() 方法实现元素的出栈操作。peek() 方法返回栈顶元素，size() 方法返回栈的元素个数。

我们可以使用该栈类进行栈的基本操作，如下所示：

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.size())  # 输出：3
print(stack.peek())  # 输出：3
print(stack.pop())   # 输出：3
print(stack.is_empty())  # 输出：False

4. 栈的应用

栈在计算机科学和软件开发中有着广泛的应用，下面介绍几个常见的应用场景。

4.1. 逆波兰表达式计算器

逆波兰表达式（Reverse Polish Notation, RPN）是一种用于数学表达式的书写方式，它将运算符放在操作数的后面，可以通过栈来进行计算。

例如，对于表达式 3 + 4 * 2，在逆波兰表达式中表示为 3 4 2 * +。其中，运算符 + 和 * 放在数字 3，4 和 2 的后面。

下面是一个使用栈来计算逆波兰表达式的示例代码：

def evaluate_rpn(expression):
    stack = Stack()
    operators = ["+", "-", "*", "/"]

    for token in expression.split():
        if token not in operators:
            stack.push(int(token))
        else:
            num2 = stack.pop()
            num1 = stack.pop()
            if token == "+":
                result = num1 + num2
            elif token == "-":
                result = num1 - num2
            elif token == "*":
                result = num1 * num2
            elif token == "/":
                result = num1 / num2
            stack.push(result)

    return stack.pop()

expression = "3 4 2 * +"
print(evaluate_rpn(expression))  # 输出：11

4.2. 括号匹配

栈也可以用于解决括号匹配的问题。给定一个由括号组成的字符串，我们需要判断括号是否匹配。

例如，对于字符串 ()[]{}，括号是匹配的；而对于字符串 ({[()]})，同样是匹配的。

下面是一个使用栈来判断括号匹配的示例代码：

def is_valid_parentheses(s):
    stack = Stack()
    mapping = {')': '(', ']': '[', '}': '{'}

    for char in s:
        if char in mapping:
            top_element = stack.pop() if not stack.is_empty() else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.push(char)

    return stack.is_empty()

s = "()[]{()}"
print(is_valid_parentheses(s))  # 输出：True

4.3. 浏览器前进和后退

在浏览器中，我们可以通过点击前进和后退按钮来切换页面。浏览器使用栈来实现这一功能。每当访问一个新页面时，该页面的 URL 被压入栈顶；当点击后退按钮时，栈顶的页面 URL 被弹出，访问上一个页面。

下面是一个简化版的浏览器历史记录管理的示例代码：

class BrowserHistory:
    def __init__(self):
        self.back_stack = Stack()
        self.forward_stack = Stack()

    def visit(self, url):
        self.back_stack.push(url)

    def back(self):
        if self.back_stack.is_empty():
            return None
        current_url = self.back_stack.pop()
        self.forward_stack.push(current_url)
        return current_url

    def forward(self):
        if self.forward_stack.is_empty():
            return None
        current_url = self.forward_stack.pop()
        self.back_stack.push(current_url)
        return current_url

history = BrowserHistory()
history.visit("https://www.example.com/page1")
history.visit("https://www.example.com/page2")
history.visit("https://www.example.com/page3")
print(history.back())  # 输出：https://www.example.com/page2
print(history.forward())  # 输出：https://www.example.com/page3