(一)链栈图文解析

链栈是指采用链式结构实现的栈，和单链表的存储结构相同，用数据域和指针域分别代表存储的数据与指针，与单链表不同的是栈不需要头结点，且只对栈顶元素依次进行入栈和出栈操作。

(二) 顺序栈代码解析

(1) 链栈的基本操作

1.1 链栈的存储结构

typedef struct StackNode
{
	int data;	//数据域
	struct StackNode *next;	//指针域
}StackNode,*LinkStack;

1.2 链栈的初始化

void InitStack(LinkStack &S)
{
	S=NULL;//因为链栈不需要头结点，所以也不必为其分配空间
}

1.3 链栈的入栈

void Push(LinkStack &S,int e)
{
	LinkStack p;	//创建一个新结点
	p=(StackNode *)malloc(sizeof(StackNode));//为结点分配空间
	p->data=e;	//给新结点p的数据域置为e
	p->next=S;	//将新结点插入到栈顶，新结点p指向栈顶S结点
	S=p;		//使栈顶S结点=p结点，即使S依旧指向栈顶p
}

1.4 链栈的出栈

void Pop(LinkStack &S,int &e)
{
	LinkStack p;//创建一个新结点
	p=(StackNode *)malloc(sizeof(StackNode));//为新结点分配空间
	if(S==NULL)	//判断链栈是否为空
		printf("栈空!\n");
	else
	{
		e=S->data;//将栈顶数据赋给e
		p=S;	//用p保存栈顶结点S，用于释放栈顶结点
		S=S->next;	//修改栈顶指针，使S指向栈顶以下的结点
		free(p);	//释放头结点的空间p=S
	}
}

1.5 取栈顶元素

void GetTop(LinkStack S)
{
	if(S!=NULL)
		printf("栈顶元素:%d\n",S->data);
	else
		printf("栈空!\n");
}

(2) 链栈源代码及测试

2.1 源代码：

#include<stdio.h>
#include<malloc.h>
typedef struct StackNode
{
	int data;
	struct StackNode *next;
}StackNode,*LinkStack;

void InitStack(LinkStack &S)
{
	S=NULL;
}

void Push(LinkStack &S,int e)
{
	LinkStack p;
	p=(StackNode *)malloc(sizeof(StackNode));
	p->data=e;
	p->next=S;
	S=p;
}

void Pop(LinkStack &S,int &e)
{
	LinkStack p;
	p=(StackNode *)malloc(sizeof(StackNode));
	if(S==NULL)
		printf("栈空!\n");
	else
	{
		e=S->data;
		p=S;
		S=S->next;
		free(p);
	}
}

void GetTop(LinkStack S)
{
	if(S!=NULL)
		printf("栈顶元素:%d\n",S->data);
	else
		printf("栈空!\n");
}	
int main()
{
	StackNode *S;
	int e;
	InitStack(S);
	Push(S,10);
	Push(S,20);
	Push(S,30);
	printf("依次入栈10,20,30\n");
	GetTop(S);
	printf("出栈一次\n");
	Pop(S,e);
	GetTop(S);
	return 0;
}

2.2 测试结果：

测试环境 : Windows 10
编译软件 : Visual C++ 6.0