栈的链式存储结构——C语言

链式存储结构最大的好处就是没有空间的限制，通过指针指向将结点像一个链子一样把结点链接，那么栈的同样可以用于链式存储结构。

栈因为只是栈顶来做插入和删除操作，所以比较好的方法就是将栈顶放在单链表的头部（与顺序栈相反），栈顶指针和单链表的头指针合二为一。

另外栈顶在头部了，那么单链表的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。

同样对于链栈来说，基本不存在栈满的情况，除非内存已经没有可用的空间了。

下面是链栈的指向图：

同样链栈中最重要的算法是压栈和弹栈。

代码实现：

//栈顶放在链表的头部，栈顶指针和头指针合二。
//另外栈顶在头部，单链表的头结点也就失去了意义。
//对于链栈来说，基本不存在栈满的情况，除非内存已经没有可用的空间了。
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef int ElemType;
typedef struct Node
{
	ElemType data;
	struct Node *next;
}StackNode, *LinkStackpoi;

typedef struct LinkStack
{
	LinkStackpoi top;
	int count; //元素个数
}LinkStack;

//链栈的初始化
bool InitLinkStack(LinkStack *s)
{
	if (!s)
	{
		return false;
	}
	s->top = NULL;
	s->count = 0;
	return true;
}

//压栈
void push(LinkStack *s, ElemType e)
{
	if (!s)
	{
		exit(0);
	}
	StackNode *p = (StackNode*)malloc(sizeof(StackNode));
	p->next = s->top;
	s->top = p;
	p->data = e;
	s->count++;
	//头插法
}

//出栈
void pop(LinkStack *s, ElemType &e)
{
	if (!(s && s->count))
	{
		exit(0);
	}
	StackNode *p = s->top;
	e = p->data;
	s->top = p->next;
	free(p);
	s->count--;
}

//清空栈
void clear(LinkStack *s)
{
	if (!(s && s->count))
	{
		printf("栈原本已清空\n");
		exit(0);
	}
	while (s->count)
	{
		StackNode *p = s->top;
		s->top = p->next;
		free(p);
		s->count--;
	}
}

//显示站内元素
void display(LinkStack *s)
{
	if (!(s && s->count))
	{
		exit(0);
	}
	StackNode* p = s->top;
	while (p)
	{
		printf("%d,", p->data);
		p = p->next;
	}
}

int main()
{
	int c, countsize;
	ElemType elem;
	LinkStack stack;
	InitLinkStack(&stack);
	printf("输入链栈的元素个数为:\n");
	scanf("%d", &countsize);
	for (int i = 0; i < countsize; i++)
	{
		printf("输入元素:\n");
		scanf("%d", &c);
		push(&stack, c);
	}
	printf("栈内的元素为：\n");
	display(&stack);
	pop(&stack, elem);
	printf("出栈的元素为:%d\n", elem);
	printf("栈内的元素为：\n");
	display(&stack);
	clear(&stack);
	system("pause");
	return 0;
}
           

运行结果：