括号匹配-Python中最强数据结构——栈的魅力与应用

中最强数据结构——栈的魅力与应用

栈是一种非常基础的、强大的数据结构。它的应用范围广泛，尤其在编程中，栈的用途几乎无处不在。今天，我们将一起深入了解栈的基本概念、实现方法和一些常见的应用场景，让你快速掌握栈的使用。

什么是栈？

栈（Stack）是一种先进后出（LIFO）的线性数据结构。也就是说，栈中最后被放入的数据将最先被取出。你可以把栈想象成一个“盘子堆”括号匹配，新的盘子总是被放在最上面，而取盘子时总是从最上面取。

栈的核心操作包括：

栈的形象比喻

想象你在餐馆里，服务员正在收拾盘子。服务员从上面开始堆叠盘子，新的盘子总是被放到最上面。每当需要取盘子时，服务员从最上面取，直到最底层的盘子。如果要移走最底层的盘子，就得先把上面的盘子都拿掉，这就模拟了栈的“先进后出”特性。

如何在中实现栈？

本身没有内建的栈数据结构，但我们可以通过列表（list）来实现栈的功能括号匹配，因为列表支持()和pop()方法，这两个方法正好对应栈的push和pop操作。

使用列表实现栈

# 使用列表模拟栈
stack = []

# push操作
stack.append(1)  # 栈顶是1
stack.append(2)  # 栈顶是2
stack.append(3)  # 栈顶是3

print(f"栈的状态：{stack}")

# pop操作
top = stack.pop()  # 从栈顶移除并返回3
print(f"移除栈顶元素：{top}")
print(f"移除后的栈：{stack}")

# peek操作
top = stack[-1]  # 查看栈顶元素但不移除
print(f"栈顶元素：{top}")

输出：

栈的状态：[1, 2, 3]
移除栈顶元素：3
移除后的栈：[1, 2]
栈顶元素：2

栈的应用实例

栈在编程中有很多常见的应用。下面列出一些经典的应用场景。

1. 括号匹配问题

一个常见的面试题目是括号匹配。我们可以使用栈来判断一个表达式中的括号是否成对出现。

例如，表达式(a + b) * (c + d)中的括号是成对的，而(a + b * (c + d)则是不匹配的。

括号匹配的实现：

def isValid(s: str) -> bool:
    stack = []
    # 括号对应关系
    parentheses_map = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in parentheses_map.values():
            # 如果是左括号，入栈
            stack.append(char)
        elif char in parentheses_map.keys():
            # 如果是右括号，检查栈顶的左括号是否匹配
            top_element = stack.pop() if stack else'#'
            if parentheses_map[char] != top_element:
                returnFalse
    returnnot stack  # 栈为空，说明所有括号都匹配

使用例子：

expression = "(a + b) * (c + d)"
print(isValid(expression))  # 输出：True

expression = "(a + b * (c + d)"
print(isValid(expression))  # 输出：False

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

栈非常适合用于实现浏览器的历史记录功能。当用户点击“后退”时，我们可以将当前页面压入栈中，点击“前进”时，则弹出栈顶页面。

实现一个简单的浏览器历史功能：

class BrowserHistory:
    def __init__(self):
        self.history = []

    def visit(self, url: str):
        self.history.append(url)

    def back(self):
        if len(self.history) > 1:
            self.history.pop()
            return self.history[-1]
        return"No history"

    def forward(self, url: str):
        self.history.append(url)
        return url

# 使用例子
browser = BrowserHistory()
browser.visit("google.com")
browser.visit("yahoo.com")
print(browser.back())  # 输出："google.com"
browser.visit("bing.com")
print(browser.forward("bing.com"))  # 输出："bing.com"