《数据结构》C语言版——栈链

顺序栈是分配一段连续的内存空间，需要两个指针，即指针top与指针base，指针top指向栈顶，指针base指向栈底，而链栈每个结点的地址是不连续的，所以只需要一个栈顶指针即可，相比于单链表，栈链的操作只能在栈顶进行。

入栈前，旧的栈顶结点是新入栈结点的后继结点，栈顶指针重新指向新入栈的结点；
出栈前，新的栈顶结点是即将出栈结点的后继结点，栈顶指针指向出栈结点的后继(即指向新的栈顶结点，把出栈结点释放)；

空口无凭，纸上的概念都显得苍白无力，让我们把代码开起来，慢慢细品！！！

#include <stdio.h>
#include <malloc.h>
#include <assert.h>//断言——如果条件返回错误，则终止程序执行
typedef int ElemType;//定义元素类型为int型，即为存放整型数据的栈链
/*给出结点结构*/
typedef struct StackNode
{
	ElemType data;//数据域
	struct StackNode *next;//指针域(指向下一个结点的地址)
}ListNode,*pNode;//定义结点类型,定义结点的指针类型

/*给出链栈结构*/
typedef struct ListStack
{
	pNode top;//指针top指向栈顶元素
	size_t size;//结点的个数
}ListStack;

/*初始化链栈*/
void InitStack(ListStack *s)
{
    s->top=(StackNode*)malloc(sizeof(StackNode)); //栈顶指针指向新申请的结点  
	assert(s->top!=NULL);//判断申请空间是否为空
	s->top = NULL;//栈顶指针初始化
	s->size=0;//栈中元素初始化为0个
}

/*链栈是否为空*/
bool IsEmptyStack(ListStack *s)//给出链栈的位置
{
	if(s->size == 0)
		return true;
	else
		return false;
}

/*入链栈*/
void PushStack(ListStack *s, ElemType x)//给出链栈的位置和即将入栈的元素
{
	StackNode *p=(StackNode*)malloc(sizeof(StackNode));//指针p指向申请的新结点
	assert(p!=NULL);
	p->data = x;//入栈的元素保存新结点的数据域
    p->next = s->top;//新结点的指针域保存栈顶指针的地址
    s->top = p;//栈顶指针重新指向新结点
	s->size++;//栈中元素增加
  }

/*出链栈*/
void PopStack(ListStack *s, ElemType *v)
{
		StackNode *p=s->top;//指针p指向栈顶
		*v=s->top->data;//指针v带回栈顶元素
		s->top=s->top->next;//栈顶指针指向栈顶结点的后继结点
		free(p);//释放栈顶结点
	    s->size--;//栈中元素减少
}

/*展示链栈*/
void ShowStack(ListStack *s)
{
		StackNode *p=s->top;//指针p指向栈顶
		printf("链栈中的数据元素:");
		while(p!=NULL)//栈不为空,执行
		{
			printf("%d->",p->data);
			p = p->next;//p指向下一个结点
		}
			printf("\n");
}

/*取栈顶指针*/
void GetTopStack(ListStack *s,ElemType *v)
{
	if(s->top==NULL)
		return;
	else
		*v=s->top->data;//指针v带回栈顶元素
}

/*栈长*/
int LengthStack(ListStack *s)
{
	return s->size;
}

/*清空栈链*/
void ClearStack(ListStack *s)
{
	StackNode *p=s->top;//指针p指向栈顶结点
	while(p!=NULL)
	{
		s->top=p->next;//栈顶指针指向栈顶结点的后继结点
		free(p);//释放栈顶结点
		p=s->top;//指针p重新指向栈顶结点
	}
	s->top = NULL;//否则栈顶指针置空
	s->size = 0;//栈中长度置0
}

/*销毁栈链*/
void DestroyStack(ListStack *s)
{
	ClearStack(s);
	free(s->top);//销毁最初创建的结点
	s->top=NULL;//预防野指针
}

void main()
{
		ListStack  st;
		ElemType e;
		InitStack(&st);
		if(IsEmptyStack(&st))
			printf("栈为空,初始化成功\n\n");
		else
			printf("栈非空!\n\n");
 		printf("入栈\n");
		for(int i=0;i<5;i++)
		{
			PushStack(&st,i);
		}
	    ShowStack(&st);
		printf("\n");
		int k=LengthStack(&st);
		printf("栈的长度为:%d \n\n",k);
		GetTopStack(&st,&e);
		printf("栈顶元素为:%d \n",e);
		printf("\n");
  		printf("出栈\n");
		PopStack(&st,&e);
		printf("出栈的元素为:%d \n",e);
		ShowStack(&st);
		printf("\n");
		PopStack(&st,&e);
		printf("出栈的元素为:%d \n",e);
		ShowStack(&st);
		printf("\n");
		PopStack(&st,&e);
		printf("出栈的元素为:%d \n",e);
		ShowStack(&st);
		printf("\n");
		PopStack(&st,&e);
		printf("出栈的元素为:%d \n",e);
		ShowStack(&st);
		printf("\n");
		PopStack(&st,&e);
		printf("出栈的元素为:%d \n",e);
		ShowStack(&st);
		printf("\n");
		PopStack(&st,&e);
		printf("出栈的元素为:%d \n",e);
		ShowStack(&st);
		ClearStack(&st);
		DestroyStack(&st);
}

运行结果：