大家好，今天和大家一起分享一下数据结构中的栈基本内容~
栈是一种非常基础且重要的线性数据结构，它遵循后进先出（LIFO, Last In First Out）的原则。今天详细介绍栈的基本概念、操作方法、实现方式以及在实际应用中的示例。
1. 栈的基本概念
栈是一种只能在一端进行插入或删除的线性表，在主程序中常用来保存函数调用信息。这种特性使得栈非常适合处理需要回溯的问题，如括号匹配、表达式求值等。栈的这一端通常被称为“栈顶”，相对的一端称为“栈底”。所有新元素都靠近栈顶添加，而移除元素时也是从栈顶开始。
1.1 栈的主要操作
- push：向栈中添加一个新的元素。
- pop：移除栈顶元素，并返回该元素的值。
- peek 或 top：查看栈顶元素而不移除它。
- isEmpty：检查栈是否为空。
- size：获取栈中元素的数量。
2. 栈的应用场景
栈因其独特的访问模式而在多种场景下被广泛使用：
- 函数调用与递归：在程序运行时，系统会维护一个调用栈来跟踪当前正在执行的函数及其状态。
- 括号匹配：用于检查代码或文本中的括号是否正确闭合。
- 表达式求值：可以用来计算逆波兰表示法（RPN）中的算术表达式。
- 浏览器历史记录：用户浏览网页时，浏览器使用栈来存储访问过的页面地址，以便快速返回之前的页面。
- 编译器设计：编译器使用栈来进行语法分析，比如识别嵌套结构。
3. 栈的实现
栈可以通过多种方式实现，包括数组和链表两种常见的方法。
3.1 使用数组实现栈
数组实现的栈简单直观，但需要预先定义最大容量。当达到最大容量时，除非进行动态调整，否则无法继续添加新元素。
class ArrayStack:def __init__(self, capacity=10):self.capacity = capacityself.stack = [None] * capacityself.top_index = -1def push(self, item):if self.top_index + 1 == self.capacity:raise Exception("Stack is full")self.top_index += 1self.stack[self.top_index] = itemdef pop(self):if self.isEmpty():raise Exception("Stack is empty")item = self.stack[self.top_index]self.stack[self.top_index] = Noneself.top_index -= 1return itemdef peek(self):if not self.isEmpty():return self.stack[self.top_index]return Nonedef isEmpty(self):return self.top_index == -1def size(self):return self.top_index + 13.2 使用链表实现栈
链表实现的栈更加灵活，因为不需要预先设定大小。每个节点包含数据部分和指向下一个节点的指针。
class Node:def __init__(self, data):self.data = dataself.next = Noneclass LinkedListStack:def __init__(self):self.top = Noneself._size = 0def push(self, item):new_node = Node(item)new_node.next = self.topself.top = new_nodeself._size += 1def pop(self):if self.isEmpty():raise Exception("Stack is empty")item = self.top.dataself.top = self.top.nextself._size -= 1return itemdef peek(self):if not self.isEmpty():return self.top.datareturn Nonedef isEmpty(self):return self._size == 0def size(self):return self._size4. 栈的实际应用案例
接下来通过几个具体的应用案例来进一步说明
4.1 括号匹配问题
给定一个字符串，判断其中的圆括号、方括号和花括号是否成对出现且正确嵌套。
def is_balanced(expression):stack = []for char in expression:if char in "([{":stack.append(char)elif char in ")]}":if not stack:return Falsetop = stack.pop()if (char == ")" and top != "(") or \(char == "]" and top != "[") or \(char == "}" and top != "{"):return Falsereturn len(stack) == 0此函数遍历输入字符串，遇到左括号时将其压入栈中；遇到右括号时则检查栈顶元素是否为对应的左括号。如果最终栈为空，则说明括号匹配正确。
4.2 计算逆波兰表达式
逆波兰表达式（RPN）是一种数学表达式的表示形式，其中运算符位于操作数之后。例如，3 4 + 表示 3 + 4。
def evaluate_rpn(expression):stack = []tokens = expression.split()for token in tokens:if token.isdigit():stack.append(int(token))else:right_operand = stack.pop()left_operand = stack.pop()result = 0if token == "+":result = left_operand + right_operandelif token == "-":result = left_operand - right_operandelif token == "*":result = left_operand * right_operandelif token == "/":result = left_operand / right_operandstack.append(result)return stack[0]这段代码首先将输入字符串分割成单个字符，然后遍历这些字符。如果是数字，则直接压入栈；如果是运算符，则弹出栈顶两个元素作为操作数，根据运算符进行计算，并将结果再压入栈。最后，栈中剩下的唯一元素即为表达式的计算结果。
4.3 简单的文字编辑器撤销功能
模拟一个简单的文字编辑器，支持添加字符和撤销最后一次操作的功能。
class TextEditor:def __init__(self):self.text = ""self.history = []def add_text(self, text):self.history.append(self.text)self.text += textdef undo(self):if self.history:self.text = self.history.pop()# 示例
editor = TextEditor()
editor.add_text("Hello, ")
editor.add_text("world!")
print(editor.text) # 输出: Hello, world!
editor.undo()
print(editor.text) # 输出: Hello,在这个例子中，每次添加文本时都将当前文本状态保存到历史记录栈中。当需要撤销操作时，只需从历史记录栈中恢复上一次的状态即可。
如果希望进一步分析，可以尝试实现一些更复杂的栈应用场景，如深度优先搜索算法、内存管理等。此外，也可以考虑研究其他类型的数据结构，如队列、树、图等。