69 第4 章 栈和队列 一、复习要点 本章主要讨论3种线性结构：栈、队列与优先级队列。这3种结构都是顺序存取的表，而且都是限制存取点的表。栈限定只能在表的一端（栈顶）插入与删除，其特点是先进后出。队列和优先级队列限定只能在表的一端（队尾）插入在另一端（队头）删除，不过优先级队列在插入和删除时需要根据数据对象的优先级做适当的调整，令优先级最高的对象调整到队头，其特点是优先级高的先出。而队列不调整，其特点是先进先出。这几种结构在开发各种软件时非常有用。 本章复习的要点： 1 、基本知识点 要求理解栈的定义和特点，栈的抽象数据类型和在递归和表达式计算中的使用，在栈式铁路调车线上当进栈序列为 1, 2, 3, , n 时，可能的出栈序列计数，栈的顺序存储表示和链接存储表示，特别要注意，链式栈的栈顶应在链头，插入与删除都在链头进行。另外，需要理解队列的定义和特点，队列的抽象数据类型和在分层处理中的使用，队列的顺序存储表示（循环队列）和链接存储表示，需要注意的是，链式队列的队头应在链头，队尾应在链尾。还需要理解优先级队列的定义和特点。优先级队列的最佳存储表示是堆（heap），本章介绍的表示看懂即可。 2 、算法设计 栈的 5 种操作（进栈、退栈、取栈顶元素、判栈空、置空栈）的在顺序存储表示下的实现，以及在链接存储表示下的实现。 使用栈的后缀表达式计算算法 双栈共用一个数组的进栈、退栈、置空栈、判栈空算法及栈满、栈空条件 使用两个栈模拟一个队列时的进队列和出队列算法 循环队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现 使用 tag 区分队列空和队列满的循环队列的进队列和出队列操作的实现 链式队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现 使用队尾指针 rear 和队列长度 length 的链式队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现 队列在分层处理中的使用事例（杨辉三角形按层次打印） 双端队列的顺序存储表示及其进队列、出队列算法及队空、队满条件 二、难点和重点 1、栈：栈的特性、栈的基本运算 栈的数组实现、栈的链表实现 栈满及栈空条件、抽象数据类型中的先决条件与后置条件 2、栈的应用：用后缀表示计算表达式，中缀表示改后缀表示 3、队列：队列的特性、队列的基本运算 队列的数组实现：循环队列中队头与队尾指针...
