《数据结构和算法》之栈的链式存储结构

        在上篇博文中我已经将栈的顺序存储结构简单地介绍了一下，也举了一个进制转换的例子，供大家学习参考。这里将继续进行栈的有关介绍，本篇博文重点对栈的链式存储结构进行分析。

一，栈的链式存储结构

        栈的链式存储结构简称栈链。栈因为只是栈顶来做插入和删除操作，所以比较好的方法就是将栈顶放在单链表的头部，栈顶指针和单链表的头指针合二为一。

                                                                                         

                                                                                                               图1  栈的链式结构示意图

          在图1中可以看到，这是一个栈链，栈顶就相当于单链表的表头，栈底就相当于单链表的表尾。

二，栈链的定义结构

            

typedef struct StackNode { ElemType data; //存放栈的数据 struct StackNode *next; }StackNode, *LinkStackPtr; typedef struct LinkStack { LinkStackPrt top; //指针 int count; //栈元素计算器 }

三，栈的具体操作

    1，进栈操作

          对于栈链的Push操作，假设元素的值为e的新结点是s, top为栈顶指针，我们得到如下代码：

          

Satus Push(LinkStack *s,ElemType e) { LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode)); p->data = e; p->next = s->top; s->top = p; s->count++; return OK; }

     2，出栈操作

        链栈的出栈Pop操作，也是假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可。

Satus Push(LinkStack *s,ElemType e) { LinkStackPtr p; if(StackEmpty(*s)) return ERROR; *e = s->top->data; p = s->top; s->top = s->top->next; free(p); s->count--; return OK; }