Python数据结构预算法之栈（Stack）的实现与应用 数据结构预算法.pdf

Python中的栈（Stack）是一种基于“后进先出”（LIFO）原则的数据结构，它在数据处理中扮演着重要角色。栈的操作主要包括入栈（push）、出栈（pop）、查看栈顶元素（peek）以及检查栈是否为空（is_empty）。在Python中，可以方便地利用内置的列表（list）数据类型来实现栈的功能。 我们可以创建一个名为`Stack`的类，将列表`items`作为存储元素的基础容器。通过`__init__`方法初始化一个空的列表。栈的其他基本操作如push、pop、peek和size可以通过列表的方法直接实现： ```python class Stack: def __init__(self): self.items = [] def is_empty(self): return self.items == [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def peek(self): return self.items[len(self.items)-1] def size(self): return len(self.items) ``` 栈的应用广泛，例如在括号匹配问题中，我们可以使用栈来检查一个字符串中的括号是否匹配。`parChecker`函数通过创建一个栈`s`，遍历输入的括号字符串，遇到开括号就入栈，遇到闭括号时检查栈顶的开括号是否匹配，不匹配或栈为空则返回False，遍历结束后栈为空且所有括号匹配则返回True。 ```python def parChecker(symbolString): s = Stack.Stack() balanced = True index = 0 # ... ``` 进制转换也是一个常见的栈应用。例如，将10进制数字转换为其他进制，可以使用栈来存储每次除法得到的余数，然后逆序组合成目标进制的字符串。`baseConvert`函数实现了这个功能，它接受一个10进制数字和目标进制，返回转换后的字符串。 ```python def baseConvert(decNumber, base): digit = "0123456789ABCDEF" tranStack = Stack() # ... ``` 此外，表达式转换（如中缀转后缀表达式）也可以用栈来解决。在扫描中缀表达式时，操作符被压入操作符栈（opstack），遇到操作数则添加到结果列表，遇到左括号入栈，右括号出栈直到遇到匹配的左括号。这样可以确保运算符的优先级和顺序得到正确处理。 栈作为一种基础的数据结构，其简单易用的特性使其在算法和程序设计中有着广泛的应用，包括但不限于括号匹配、进制转换、表达式解析等。理解并熟练掌握栈的原理和实现，对于提升编程能力具有重要意义。