Stack 栈模型的链式存储实现

栈模型使用顺序存储的方式就相当于在数组上进行操作，而本文介绍的则是通过链式存储来实现栈的模型，那么我们就要思考一个问题了。栈只是栈顶来做插入和删除操作，栈顶放在链表的头部还是尾部呢？

由于单链表有头指针，而栈顶指针也是必须的，那干嘛不让他俩合二为一呢，所以比较好的办法就是把栈顶放在单链表的头部（如下图）。另外都已经有了栈顶在头部了，单链表中比较常用的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。（摘自 传智播客 教师课件）

【代码实现】

以下代码需要用到线性表链式存储的头文件。

#ifndef _LINKSTACK_H
#define _LINKSTACK_H
#

typedef void LinkStack;


//创建栈
LinkStack* LinkStack_Create();

//销毁栈
void LinkStack_Destroy(LinkStack* stack);

//清空栈
void LinkStack_Clear(LinkStack* stack);

//压栈
int LinkStack_Push(LinkStack* stack, void *item);

//出栈
void* LinkStack_Pop(LinkStack* stack);

//获取栈顶元素
void* LinkStack_Top(LinkStack* stack);

//获取栈的大小
int LinkStack_Size(LinkStack* stack);

#endif //_LINKSTACK_H

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "LinkStack.h"
#include "LinkList.h"

//栈节点的数据结构
typedef struct tag_linkstacknode
{
	//链表节点
	LinkListNode node;
	//保存数据节点的地址
	void * data;
}LinkStackNode;

//创建栈
LinkStack* LinkStack_Create()
{
	return LinkList_Create();
}

//销毁栈
void LinkStack_Destroy(LinkStack* stack)
{
	// 先free所有堆上的内存
	LinkStack_Clear(stack);

	// 销毁线性表
	LinkList_Destroy(stack);
}


//清空栈
void LinkStack_Clear(LinkStack* stack)
{
	// 无限循环弹出所有栈上的元素，直至长度为0
	while (LinkStack_Size(stack))
	{
		// 弹出
		LinkStack_Pop(stack);
	}
	// 清空线性表
	LinkList_Clear(stack);
}


//压栈
int LinkStack_Push(LinkStack* stack, void *item)
{
	LinkStackNode* pNew = malloc(sizeof(LinkStackNode));
	if (pNew == NULL)
	{
		return -1;
	}
	//初始化
	pNew->data = item;
	pNew->node.next = NULL;

	//将栈节点插入到链表的头部
	int ret = LinkList_Insert(stack, (LinkListNode*)pNew, 0);
	if (ret != 0)
	{
		free(pNew);
	}
	return ret;
}


//出栈
void* LinkStack_Pop(LinkStack* stack)
{
	void* myData = NULL;
	//删除链表中的第一个数据节点
	LinkListNode* pDel = LinkList_Delete(stack, 0);
	//
	//释放节点内存
	if (pDel != NULL)
	{
		myData = ((LinkStackNode*)pDel)->data;
		free(pDel);
	}

	return myData;
}


//获取栈顶元素
void* LinkStack_Top(LinkStack* stack)
{
	//获取链表第一个节点
	LinkListNode* pNode = LinkList_Get(stack, 0);
	LinkStackNode * pp = (LinkStackNode*)pNode;
	return pp->data;
}


//获取栈的大小
int LinkStack_Size(LinkStack* stack)
{
	return LinkList_Length(stack);
}

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "LinkStack.h"

int main()
{
	int i;
	int array[10] = { 0 };
	LinkStack* stack = NULL;
	//创建栈
	stack = LinkStack_Create();
	//初始化数组
	for (i = 0; i < sizeof(array) / sizeof(int); i++)
	{
		array[i] = i;
		//压栈
		LinkStack_Push(stack, (void*)&array[i]);
	}

	//打印栈的大小
	printf("stack size = %d\n", LinkStack_Size(stack));
	//获取栈顶元素
	printf("stack top element = %d\n", *(int*)LinkStack_Top(stack));

	//所有元素出栈
	while (LinkStack_Size(stack) > 0)
	{
		//出栈, 并打印弹出的元素值
		printf("Pop -- stack top element = %d\n", *(int*)LinkStack_Pop(stack));
	}
	//销毁栈
	LinkStack_Destroy(stack);

	printf("Good good study, day day up!!!\n");
	system("pause");
	return 0;
}