数据结构第4章.doc

"数据结构第4章栈和队列" 数据结构是计算机科学中的一门基础课程，对于计算机科学专业的学生来说是必修的课程。该章节主要讨论了栈和队列这两种基本数据结构，栈是一种基于 Last-In-First-Out（LIFO）原则的数据结构，队列是一种基于 First-In-First-Out（FIFO）原则的数据结构，优先级队列是队列的一种变形，根据数据对象的优先级对其进行排序。 栈是一种顺序存取的表，限定只能在表的一端（栈顶）插入与删除，其特点是先进后出。栈的抽象数据类型定义了栈的基本操作，如进栈、退栈、取栈顶元素、判栈空、置空栈等。栈的顺序存储表示和链接存储表示是两种常见的实现方式，需要注意的是，链式栈的栈顶应在链头，插入与删除都在链头进行。 队列是一种顺序存取的表，限定只能在表的一端（队尾）插入在另一端（队头）删除，队列的抽象数据类型定义了队列的基本操作，如进队列、出队列、取队头元素、判队列空、置空队列等。队列的顺序存储表示（循环队列）和链接存储表示是两种常见的实现方式，需要注意的是，链式队列的队头应在链头，队尾应在链尾。 优先级队列是队列的一种变形，根据数据对象的优先级对其进行排序。优先级队列的最佳存储表示是堆（heap）,本章节中介绍的表示看懂即可。 在算法设计中，需要掌握栈和队列的基本操作的实现，如栈的 5 种操作（进栈、退栈、取栈顶元素、判栈空、置空栈）的在顺序存储表示下的实现，以及在链接存储表示下的实现。双栈共用一个数组的进栈、退栈、置空栈、判栈空算法及栈满、栈空条件也需要掌握。此外，还需要了解使用栈的后缀表达式计算算法、使用两个栈模拟一个队列时的进队列和出队列算法等。 在习题解析中，需要掌握如何改写顺序栈的进栈成员函数 Push(x)，要求当栈满时执行一个 stackFull() 操作进行栈满处理。另外，还需要掌握铁路进行列车调度时的栈式结构的站台设计，如右图所示，以及可能的出栈序列的计算方法等。