《数据结构与算法 C语言版》—— 3.7小结

本节书摘来自华章出版社《数据结构与算法 C语言版》一 书中的第3章，第3.7节，作者：徐凤生，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

3.7小结

本章介绍了两种特殊的线性表：栈和队列，主要内容如下。
（1）栈
栈是限定仅在表尾（栈顶）进行插入（进栈）或删除（出栈）的线性表，又称后进先出的线性表。栈有两种存储表示：顺序表示（顺序栈）和链式表示（链栈）。
栈的主要操作是进栈和出栈。
对于顺序栈的进栈和出栈要注意判断栈满或栈空，栈满和栈空的条件与栈顶指针的指向有关。本书中栈顶指针指向栈顶元素，栈满的条件是Stop>=Sstacksize-1，栈空的条件是Stop=-1。有的教材中栈顶指针指向栈顶的下一个元素时，栈满和栈空的条件会发生变化，需要特别注意。当然，这两种情况下的进栈和出栈操作也会有所不同。
链栈的进栈操作不需要判断栈是否已满，但出栈操作仍需要判断是否为空栈。
（2）队列
队列是一种先进先出的线性表，它只允许在表的一端（队尾）插入元素（入队），而在另一端（队头）删除元素（出队）。队列也有两种存储表示：顺序表示（循环队列）和链式存储表示（链队列）。
队列的主要操作是入队和出队。
对于顺序表示的循环队列的入队和出队操作要注意判断队满或队空。为了区分队满和队空，需牺牲一个存储单元。队满的条件是(Qrear+1)%MAXSIZE=Qfront，队空的条件是Qfront=Qrear。凡是涉及队头或队尾指针的修改都要对其MAXSIZE求模。
链队的入队操作不需要判断队列是否已满，但出队操作仍需要判断是否为空队列。
（3）递归
递归是程序设计中最为重要的方法之一，递归程序结构清晰，形式简洁。常见的递归有“定义是递归的”、“数据结构是递归的”、“问题的解法是递归的”三种情况。递归的内部实现是通过一个工作栈保存调用过程中的参数、局部变量和返回地址的。根据是否使用栈，可将递归消除分为简单递归消除和基于栈的递归消除两类。
学完本章后，要求掌握栈和队列的特点，熟练掌握顺序栈和链栈的进栈和出栈算法，循环队列和链队列的入队和出队算法，特别注意栈满和栈空、队满和队空的条件。要求能够灵活运用栈和队列解决实际应用问题，掌握数制转换、表达式（前缀、中缀、后缀三种表达方式）求值算法，深刻理解递归算法执行过程中栈的状态变化过程，便于更好地使用递归算法。