3.1.3　栈的链式存储结构及其基本运算的实现

用链式存储结构实现的栈称为链栈。通常链栈用单链表表示，因此其结点结构与单链表的结构相同，在此用LinkStack表示，即有

说明top为栈顶指针：LinkStack top；

图3－4 链栈示意

因为栈中的主要运算是在栈顶插入、删除，显然在链表的头部作栈顶是最方便的，而且没有必要像单链表那样为了运算方便附加一个头结点。通常将链栈表示成图3－4的形式。

对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间了。对于空栈来说，链表原定义头指针为空，链栈的空就是top＝NULL。

栈的大多数操作和单链表相似，只是在插入和删除上特殊一些，链栈基本操作的实现如下。

算法3.3 链栈基本操作

（1）置空栈

（2）判栈空

（3）入栈

（4）出栈

对比一下顺序栈和链栈，在时间复杂度上是相同的，都是O（1）。在空间使用上，顺序栈需要事先估计空间大小，如果用不完就会浪费空间；链栈不必事先估计大小，但是每个元素都要多申请一个辅助空间存储指针。所以两种存储方式各有利弊，如果栈在使用时元素变化很大，有时很多，有时很少，这时适合用链栈；如果栈在使用时元素在可控范围内，适合使用顺序栈。