第3章 栈和队列
3.1 考纲要求及分析
考纲要求
(1)栈和队列的基本概念。
(2)栈和队列的顺序存储结构。
(3)栈和队列的链式存储结构。
(4)栈和队列的应用。
考纲分析
本章是必考内容,出题形式主要以选择题为主。本章要求:
(1)理解栈和队列的定义及其操作特性,掌握栈和队列对插入和删除的操作定义。
(2)对于栈和队列的存储结构,掌握顺序栈、链栈、共享栈、顺序队列、循环队列、链队列的存储方法,以及栈空、栈满、队空、队满的判定条件。
(3)掌握栈和队列的插入、删除、判空等基本操作的算法描述和时间性能。
(4)理解栈和队列的应用,例如,子程序调用、表达式求值、括号匹配等。
对于栈,常考的一类题是考查栈的后进先出特性,例如给定一个入栈序列,判断某个出栈序列的合法性(或不合法性),共享栈也是一个常考点。对于队列,循环队列是一个常考点,注意队空、队满的判定条件、队列长度的计算。
本章有一个难点是关于栈的证明题,主要采用反证法应用栈的操作特性来完成;有一个结合点是将栈、队列、链表和数组相结合,主要考查是否掌握栈和队列的操作特性,以及链表和数组的存储特点;有一个复杂的应用是递归,主要考查是否理解栈在递归调用过程中的作用,以及应用栈实现递归函数到非递归函数的转换。
由于栈和队列的算法比较简单,通常不会单独以算法设计题的形式出题;在树和图的算法设计中,栈和队列通常作为辅助数据结构,因此,需要熟练掌握栈和队列的基本操作语句。
……