链栈-----栈的链式存储结构及其实现

   栈通过数组来实现的方式其实就是采用的是线性表的顺序存储结构，而通过链式存储结构实现的栈操作，简称为”链栈“。既然是通过链式存储，那么肯定是像单链表那样，是通过一个个结点来构成的。既然是结点，必不可少的，需要一个存放数据的变量，一个存放后继指针的变量。这是对结点的定义，还有就是栈本身的定义，由于栈是在顶部进行元素的插入或删除操作，所以，需要一个栈顶指针，因为是链栈，还需要一个计数变量，用来存放元素个数的。那么，链栈的结构定义如下：

typedef struct StackNode{

    ElemType data;
    struct StackNode *next;
}StackNode, *LinkStackPtr;

typedef struct LinkStack{

    LinkStackPtr top;
    int count;
}LinkStack;

   接下来就是元素的插入操作。链栈元素的插入跟单链表元素的插入非常类似。既然是链式存储，那么很明显的就是需要动态的分配存储空间。由于只能在栈顶进行元素的插入操作，所以，在data中存放数据后，后继指针next中存放的就是top指针中的值，因为top指向的是栈顶。然后，再将栈顶指针指向新的存储空间。具体实现代码如下：

Status Push ( LinkStack *S, SElemType e )
{
    LinkStackPtr s = ( LinkStackPtr ) malloc ( sizeof ( StackNode ) );
    s->data = e;
    s->next = S->top;
    S->top = s;
    S->count++;
    
    return OK;

}

   元素的删除操作与插入操作非常类似。删除一个元素只要将栈顶指针指向它的之前一个元素就行了，然后释放删除元素的空间。代码如下：

Status Pop ( LinkStack *S, SElemType *e )
{
    LinkStackPtr p;
    if ( StackEmpty ( *s ) )
        return ERROR;
        
    p = S->top;
    *e = S->data;
    S->top = S->top->next;
    free ( p );
    S->count--;
    
    return OK;

}

最后一段总结，摘自书本：

如果栈的使用过程中元素变化不可预料，有时很小，有时非常大。那么最好是用链栈，反之，如果它的变化是在可控范围内，建议使用顺序栈会更好些。