3.1.4 链栈

1.栈的链式存储结构

采用链式存储方式的栈称为链栈或链式栈。由于栈的插入与删除操作仅限在表头的位置进行，因此链表的表头指针就作为栈顶指针。通常，链栈采用带头结点的单链表实现。如图3.5所示。

在图3.5中，top为栈顶指针，始终指向栈顶元素前面的头结点。链栈的基本操作与链表的类似，在使用完链栈时，应释放其空间。

链栈结点的类型描述如下：

链栈的进栈操作与链表的插入操作类似，出栈操作与链表的删除操作类似。关于链栈的操作说明如下：

（1）链栈通过链表实现，链表的第一个结点位于栈顶，最后一个结点位于栈底。

（2）设栈顶指针为top，初始化时，对于不带头结点的链栈，top=NULL；对于带头结点的链栈，top->next=NULL。

（3）不带头结点的栈空条件为top==NULL，带头结点的栈空条件为top->next==NULL。

2.链栈的基本运算

链栈的基本运算具体实现如下（以下算法的实现保存在文件“LinkStack.h”中）。

（1）链栈的初始化。

（2）判断链栈是否为空。

（3）进栈操作。进栈操作就是要将新元素结点插入到链表的第一个结点之前，分为两个步骤：①p->next=top->next；②top->next=p。进栈操作如图3.6所示。

（4）出栈操作。出栈操作就是将单链表中的第一个结点删除，并将结点的元素赋值给e，并释放结点空间。在元素出栈前，要判断栈是否为空。出栈操作如图3.7所示。

（5）取栈顶元素。

（6）求表长操作。

在链表中为了求表中元素个数，必须从栈顶指针出发，依次访问每个结点，并利用计数器计数，直到栈底为止。求表长的时间复杂度为O（n）。

（7）销毁链栈。