栈的链式存储结构及其基本运算的实现

时间:2021-05-13 00:15:44
#include<iostream>
using namespace std;
#define MAX 50
typedef char 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,*q=s->next;
while(q!=NULL)
{
free(p);
p=q;
q=p->next;
}
free(p);
}

int StackLength(LiStack * &s) //数据结点的个数
{
int n=0;
LiStack *p;
p=s->next;
while(p!=NULL)
{
n++;
p=p->next;
}
return (n);
}

int StackEmpty(LiStack * &s)
{
return(s->next==NULL);
}

void Push(LiStack * &s,ElemType e) //将数据结点插入头结点之后
{
LiStack *p;
p=(LiStack *)malloc (sizeof(LiStack)); //创建新结点
p->data=e;
p->next=s->next;
s->next=p;
}

int Pop(LiStack * &s,ElemType &e)
{
LiStack *p;
if(s->next==NULL)
return 0;
p=s->next;
e=p->data;
s->next=p->next;
free(p);
return 1;
}

int GetTop(LiStack * s,ElemType &e)
{
if(s->next==NULL)
return 0;
e=s->next->data;
return 1;
}

void DispStack(LiStack *s)
{
LiStack *p=s->next;
while(p!=NULL)
{
printf("%c",p->data);
p=p->next;
}
printf("\n");
}

void main()
{
LiStack *s;
s=(LiStack *)malloc (sizeof(LiStack));
cout<<"初始化栈:"<<endl;
InitStack(s);
cout<<"判断是否为空栈:";
if(StackEmpty(s))
cout<<"空"<<endl;
else
cout<<"非空"<<endl;
Push(s,'a');
Push(s,'b');
Push(s,'c');
Push(s,'d');
Push(s,'e');
cout<<"栈的长度为:"<<StackLength(s)<<endl;
cout<<"栈的元素为:";
DispStack(s);
cout<<"清空栈"<<endl;
ClearStack(s);
}