#include<malloc.h>
typedef int ElemType
typedef struct linknode
{
ElemType data //数据域
struct linknode *next //指针域
}LiStack //链栈类型的定义
//初始化栈
void InitStack(LiStack *&s)
{
s=(LiStack *)malloc(sizeof(LiStack))
s->next=NULL
}
//销毁栈
void ClearStack(LiStack *&s)
{
LiStack *p=s->next
while(p!=NULL)
{
free(s)
s=p
p=p->next
}
free(s)//
}
//求战的长度
void StackLength(LiStack *s)
{
int i=0
LiStack *p
p=s->next
while(p!=NULL)
{
i++
p=p->next
}
printf("目前此栈的长度为: %d\n",i)
}
//判断栈是否为空栈
void StackEmpty(LiStack *s)
{
if(s->next==NULL)
printf("目前此栈是空栈n")
else
printf("目前此栈不是空栈\n")
}
//进栈
void Push(LiStack *&s,ElemType e)
{
LiStack *p
p=(LiStack *)malloc(sizeof(LiStack))
p->data=e
p->next=s->next //插入*p结点作为第一个数据结点
s->next=p
}
//出栈
void Pop(LiStack *&s,ElemType &e)
{
LiStack *p
if(s->next==NULL)
{
printf("目前此栈是空栈,此次出栈失败了!\n")
}
else
{
p=s->next //p指向第一个数据结点
e=p->data
s->next=p->next
free(p)
printf("此次出栈成功,出栈元素是:%d\n",e)
}
}
//取栈顶元素
void GetTop(LiStack *s,ElemType &e)
{
LiStack *p
p=s->next
if(p==NULL)
printf("目前此栈是空栈,此次取栈顶元素失败了\n")
else
{
e=p->data
printf("此次取栈顶的元素是:%d\n",e)
}
}
//显示栈中元素
void DispStack(LiStack *s)
{
LiStack *p
p=s->next
if(p==NULL)
printf("此栈目前是空栈\n")
else
{
printf("下面输出链栈里的各个元素:\n")
while(p!=NULL)
{
printf("%d ",p->data)
p=p->next
}
printf("\n")
}
}
void main()
{
LiStack *s
int e
InitStack(s)
printf("请输入一个进栈元素:\n")
scanf("%d",&e)
while(e!=0)
{
Push(s,e)
DispStack(s)
StackLength(s)
printf("请输入一个进栈元素:\n")
scanf("%d",&e)
}
StackEmpty(s)
GetTop(s,e)
int i
printf("如果你想出栈元素,请按1\n")
scanf("%d",&i)
while(i==1)
{
Pop(s,e)
DispStack(s)
StackLength(s)
printf("如果你想继续出栈元素,请按1\n")
scanf("%d",&i)
}
printf("链栈的基本运算,到此操作完毕了哦!\n")
}
若是栈中元素的数目变化范围较大或不清楚栈元素的数目,就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。由于栈的插入、删除操作只能在一端进行,而对于单链表来说,在首端插入、删除结点要比在尾端进行相对容易一些,所以将单链表的首端作为栈的顶端,即将单链表的头指针作为栈顶指针。链栈如图1所示。
图1链栈的存储示意
顺序栈和链栈区别如下:1。存储结构不同,顺序栈是静态分配的,而链栈则是动态分配的,链栈可以将很多零碎的空间利用起来,容量可变,节省空间,顺序栈则固定内存空间,容量不变。
2。使用方面,顺序栈查询速度快,链栈添加删除数据更快。