二、链栈
结构定义：
typedef struct {
SLink top; // 栈顶指针
int length; // 栈中元素个数
} Stack;
此时只需要对顺序栈的基本操作接口作两处改动，便可作为链栈的基本操作接口。
其一是，初始化时不需要"maxsize"的参数，因为它不需要事先分配空间；其二是，在进行入栈操作时不需要顾忌栈的空间是否已经被填满。
链栈即为栈的链式存储结构。
链栈的定义更简单，结点结构和单链表中的结点结构相同，无须重复定义。由于栈只在栈顶作插入和删除操作，因此链栈中不需要头结点，但要注意链栈中指针的方向是从栈顶指向栈底的，这正好和单链表是相反的。
void InitStack ( Stack &S )
{
// 构造一个空栈 S
S.top = NULL; // 设栈顶指针的初值为"空"
S.length = 0; // 空栈中元素个数为0
} // InitStack
|
|||
|
能否将链栈中的指针方向反过来，从栈底到栈顶？
void Push ( Stack &S, ElemType e )
{
// 在栈顶之上插入元素 e 为新的栈顶元素
p = new LNode; // 建新的结点
if(!p) exit(1); // 存储分配失败
p -> data = e;
p -> next = S.top; // 链接到原来的栈顶
S.top = p; // 移动栈顶指针
++S.length; // 栈的长度增1
} // Push
在链栈的类型定义中设立"栈中元素个数"的成员是为了便于求得栈的长度。
bool Pop ( Stack &S, SElemType &e )
{
// 若栈不空，则删除S的栈顶元素，用 e 返回其值，
// 并返回 TRUE；否则返回 FALSE
if ( !S.top )
return FALSE;
else
{
e = S.top -> data; // 返回栈顶元素
q = S.top;
S.top = S.top -> next; // 修改栈顶指针
--S.length; // 栈的长度减1
delete q; // 释放被删除的结点空间
return TRUE;
}
} // Pop
和顺序栈相同，除了遍历之外，其它基本操作的时间复杂度也都是常量级的。