数据结构中栈的复习要点

栈的重点是掌握栈和在两种存储结构（顺序存储结构和链式存储结构）上实现的基本运算及其应用。

栈的逻辑结构、存储结构
栈的逻辑结构和我们先前学过的线性表相同，如果它是非空的，则有且只有一个开始结点，有且只能有一个终端结点，其它的结点前后所相邻的也只能是一个结点(直接前趋和直接后继),但是栈的运算规则与线性表相比有更多的限制，栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表。通常称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进行的，我们又称栈为LIFO表(Last In First Out)。栈的基本运算有六种：构造空栈、判栈空、判栈满、进栈、退栈、取栈顶元素。由于栈也是线性表，因此线性表的存储结构对栈也适用，通常栈有顺序栈和链栈两种存储结构，这两种存储结构的不同，则使得实现栈的基本运算的算法也有所不同。
顺序栈和链栈
在顺序栈中有"上溢"和"下溢"的概念。顺序栈好比一个有盖的盒子，我们在里头放了一叠书，但我们要用书的时候只能从第一本开始拿（是不是有点麻烦），那么当我们把书本放到这个栈中超过盒子的顶部时就放不下了（否则盒子的盖子就盖不上了），这时就是"上溢","上溢"也就是栈顶指针指出栈的外面，显然是出错了。反之，当栈中已没有书时，我们再去拿，看看没书，把盒子拎起来看看盒底，还是没有，这就是"下溢"。"下溢"本身可以表示栈为空栈,因此可以用它来作为控制转移的条件。
链栈则没有上溢的限制，它就象是一条一头固定的链子，可以在活动的一头自由地增加链环(结点)而不会溢出，链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要在头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。
以上两种存储结构的栈的基本操作算法是不同的，我们主要要学会进栈和退栈的基本算法以解决简单的应用问题。
例：链栈中为何不设置头结点?
　　 解答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。