数据结构之栈篇总结

栈是只能在表尾进行插入和删除的线性表，允许插入和删除的一端我们称之为栈顶，另一端我们称之为栈底，当栈内没有元素时我们称之为空栈，它具有后进先出的特性。

栈的顺序结构

       顺序栈通过给定尺寸大小的数组实现，并且把数组下标为0的位置设置为栈底，通过top的位置表示栈顶。当向栈增加元素时，top位置加1；当向栈删除元素时，top位置减1；当top等于-1时，表示此时为空栈，如下图所示。

 栈的链接结构

        通常链栈用单链表来实现，由于栈只能在栈顶进行插入和删除操作，所以用单链表的头部做栈的栈顶是最方便的，而不用头结点也方便，如下图所示。

       入栈和出栈都通过top指针来操作。入栈时，以s为新元素，所要做的操作为：s->next=top，top=s即可，如下图左所示；出栈时，所要做的操作为：用p暂存结点，top=top->next即可，如下图右所示。

       初始化顺序栈时，我们需要给定一个固定的长度，因此顺序栈会存在存储元素个数的限制和空间浪费的问题。链栈则不存在这类问题，但是每个元素都要另外一个指针域，增加了结构性开销。

       作为一般规律，当栈内元素变化较大时，使用链栈比较适宜，反之，使用顺序栈。但是顺序栈和链栈的选择也要根据具体情况来确定，不能一概而论。 

       the end~