栈的链式存储结构及实现

讲完了栈的顺序存储结构，我们现在来看看栈的链式存储结构，简称为链栈。

想想看，栈只是栈顶来做插入和删除操作，栈顶放在链表的头部还是尾部呢？
链表头尾操作没啥区别，但有个头指针

• 由于单链表有头指针，而栈顶指针也是必须的，那干吗不让它俩合二为一呢，

  所以比较好的办法是把栈顶放在单链表的头部（如图4-6-1所示）。

• 另外，都已经有了栈顶在头部了，单链表中比较常用的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。

图4-6-1

• 对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那此时的计算机操作系统已经面临死机崩溃的情况，而不是这个链栈是否溢出的问题。
• 但对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL的时候。

链栈的结构代码如下：

typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
} StackNode, *LinkStackPtr;
typedef struct LinkStack
{
    LinkStackPtr top;
    int count;
} LinkStack;

链栈的操作绝大部分都和单链表类似，只是在插入和删除上，特殊一些。