数据结构与算法（5）— 链栈
2、链栈
2.1、只允许在表头进行插入和删除运算的单链表称为链栈。链栈有头节点和没有头节点两种。
2.2、栈以链表的形式出现，链表 （不带头结点）首指针为s，即栈顶为s，链表尾结点为栈底。
初始化时，s=NULL(不带头结点)；s=(LStack *)malloc(sizeof(LStack)),s->next=NULL（带头结点）。
栈顶指针的引用为s（不带头结点）或s->next（带头结点），栈顶元素的引用为s->data（不带头结点）或s->next->data（带头结点）。
栈空条件为s==NULL(不带头结点)或s->next=NULL(带头结点)。
进栈操作和出栈操作与单链表在开始结点的插入和删除操作一致。
栈的链式存储结构的C语言描述
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct stnode{
ElemType data;
struct stnode *next;
}LStack;
2.3、链栈基本函数算法描述
注：以上程序在VC6.0+WIN2K下测试通过。
2.3.1、初始化
void initstack(LStack **s)
{
*s=NULL;
}
2.3.2、入栈
int push(LStack **s,ElemType x)
{
LStack *p=(LStack *) malloc (sizeof(LStack));
p->data=x;
p->next=*s;
*s=p;
return 1;
}
2.3.3、出栈
int pop(LStack **s,ElemType *x)
{
LStack *p;
if(s==NULL)
{
printf("underflow/n");
return 0;
}
else
{
p=*s;
*s=(*s)->next;
*x=p->data;
free(p);
return 1;
}
}
2.3.4、读取栈顶元素
int gettop(LStack *s,ElemType *x)
{
if(s==NULL)
{
printf("underflow/n");
return 0;
}
else
{
*x=s->data;
return 1;
}
}
2.3.5、判栈空
int isempty(LStack *s)
{
if(s==NULL)
return 1;
else
return 0;
}
2.3.6、显示链栈中的所有元素
void ShowLinkStack(LStack * s)
{
while(s!=NULL)
{
printf("栈中的元素依次为:%d/n",s->data);
s=s->next;
}
}
2.3.7、测试程序
int main()
{
LStack *s;
ElemType x;
initstack(&s);
if(isempty(s))
printf("此栈为空/n");
push(&s,1);
push(&s,2);
push(&s,3);
ShowLinkStack(s);
gettop(s,&x);
printf("栈顶元素为:%d/n",x);
pop(&s,&x);
printf("弹出的元素为:%d/n",x);
pop(&s,&x);
printf("弹出的元素为:%d/n",x);
ShowLinkStack(s);
gettop(s,&x);
printf("栈顶元素为:%d/n",x);
return 0;
}
2.3.8、由于栈是一种特殊的线性表，因此和线性表的顺序存储结构与链式存储结构的区别有所不同。栈的插入和删除是在线性表的一端进行的，无论是用顺序存储结构，还是用链式存储结构都一样。当要求存储的栈长度变化不大时，易与事先确定其大小时为了节约存储空间，宜采取顺序存储结构；反之，当栈长度变化大，难以估计其存储规模时采用动态链表作为存储结构。链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对结点之后的结点进行操作，反而使算法复杂。