数据结构第四章：栈与表达式求值

"本资源主要讨论了数据结构中的表达式求值问题，特别是与栈相关的概念，包括中缀表达式、后缀表达式及其运算规则。同时提到了栈、队列以及优先级队列等基本数据结构，并给出了栈的抽象数据类型及其实现示例。" 在计算机科学中，数据结构是组织、管理和存储数据的重要工具，它们影响着算法的效率和程序的设计。在本资料中，我们重点关注的是表达式的求值过程，这通常涉及到栈这一数据结构。 **中缀表达式**是我们在日常数学运算中常见的表达式形式，例如 `a + b * ( c - d ) - e / f`。这种表达式中，操作符位于其操作数之间。求值时，我们需要遵循特定的运算规则，如**运算符优先级**和**结合性**。优先级高的运算符先进行计算，例如乘法和除法的优先级高于加法和减法；对于优先级相同的运算符，我们从左到右进行计算。括号用于改变默认的运算顺序，先计算括号内的表达式。 **后缀表达式**，也称为逆波兰表示法，是一种没有括号且操作符位于操作数之后的表达式形式，如 `a b c d - * + e f / -`。这种表示法简化了表达式求值的过程，因为无需考虑运算符的优先级，只需要按照操作数出现的顺序进行计算即可。后缀表达式求值通常使用栈来实现。 **栈**是只允许在一端（栈顶）进行插入和删除操作的线性数据结构，遵循**后进先出（LIFO）**的原则。在表达式求值中，栈常用于处理后缀表达式：遇到操作数时压入栈，遇到运算符时取出栈顶的两个操作数进行运算，并将结果压回栈。栈的抽象数据类型通常包含构造函数、进栈（Push）、出栈（Pop）、获取栈顶元素（GetTop）、置空栈（MakeEmpty）和判断栈是否为空或已满的方法。 在给出的代码示例中，栈的实现是一个动态数组，通过栈顶指针`top`追踪当前栈顶的位置。当栈为空时，`top`等于-1；当栈满时，`top`等于最大容量减1。栈的常用操作如进栈、出栈、取栈顶元素等都有对应的成员函数。 **队列**是另一种线性数据结构，允许在两端（前端和后端）进行操作，遵循**先进先出（FIFO）**原则。虽然本资料主要关注栈，但队列在某些数据处理场景中也非常重要。 **优先级队列**是队列的一种变体，其中元素根据优先级进行排序。优先级高的元素会优先被处理。这种数据结构在许多算法中都有应用，如Dijkstra最短路径算法。 本资源通过讲解表达式求值和相关数据结构，帮助读者理解如何利用栈这一数据结构解决实际问题，并展示了栈的抽象数据类型和基本操作的实现。了解这些概念和技巧对学习和设计高效的算法至关重要。