数据结构第4章复习重点.doc

在数据结构的学习中，栈和队列是两种非常基础且重要的线性数据结构。本章主要讨论了栈、队列和优先级队列，它们都属于顺序存取的数据结构，但存取规则有所不同。 栈是一种“后进先出”（LIFO, Last In First Out）的数据结构，仅允许在一端（栈顶）进行插入和删除操作。栈在计算机科学中有广泛的应用，例如在递归调用、表达式求值、内存管理等方面。栈的抽象数据类型通常包括进栈（push）、退栈（pop）、查看栈顶元素（top）、判断栈是否为空（isEmpty）和清空栈（clear）。栈可以使用数组或链表来实现，链式栈的栈顶通常设置在链头，插入和删除操作都在链头进行。 队列是一种“先进先出”（FIFO, First In First Out）的数据结构，允许在表的一端（队尾）插入，在另一端（队头）删除。队列常用于任务调度、缓冲区管理和多进程通信等。队列的实现方式有循环队列（使用数组）和链式队列，循环队列通过双指针管理队头和队尾，链式队列则将队头和队尾分别设在链头和链尾。 优先级队列是一种特殊的队列，按照元素的优先级进行出队，优先级高的元素优先出队。最常用的数据结构是堆（heap），它是一种完全二叉树，可以保证每次出队的元素是当前队列中优先级最高的。堆分为最大堆和最小堆，前者根节点的值大于或等于其子节点，后者反之。 栈的应用中，后缀表达式（也称逆波兰表示法）是一种有效的表达式计算方法，它避免了括号的使用。中缀表达式转换为后缀表达式时，通常借助栈来辅助，根据运算符的优先级决定何时进栈或输出。 队列的难点在于理解和实现循环队列和链式队列的各种操作，如进队列（enqueue）、出队列（dequeue）、查看队头元素（front）、判断队列是否为空（isEmpty）和清空队列（clear）。循环队列需要处理队满和队空的特殊情况，而链式队列则需维护好队头和队尾的指针。 习题解析部分涉及到了栈的应用，例如在铁路列车调度中，栈式结构的站台决定了列车的出站顺序。某些出站序列是不可能的，因为它们违反了栈的“后进先出”原则。此外，还涉及了中缀表达式转后缀表达式的算法，这需要理解运算符的优先级规则。 本章复习的重点在于理解栈、队列和优先级队列的概念、特点、操作及其应用，并能够熟练地实现它们在不同存储结构下的操作。同时，掌握中缀表达式到后缀表达式的转换方法，以及如何利用这些数据结构解决实际问题，是提升编程能力的关键。