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;
}