linkstack.h 文件
#ifndef _LINK_STACK_H_
#define _LINK_STACK_H_
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//用线性表的链式存储模拟栈的链式存储,在头部插入删除元素不会涉及大量元素移动
typedef void Stack;
//把业务节点弄到底层,只需传入业务数据指针,在底层函数中
//把业务数据整合到链表一格中,void* item中,不用用户自己搞链表的业务节点了
typedef struct _tag_LinkStackNode{
LinkListConnectedNode node; //关系节点
void* item; //存业务数据
}LinkStackNode;
#ifndef bool
#define bool int
#define true 1
#define false 0
#endif
Stack* LinkStack_Create();
bool LinkStack_Destory(Stack* stack);
bool LinkStack_Clear(Stack* stack);
bool LinkStack_Push(Stack* stack, void* item);
void* LinkStack_Pop(Stack* stack);
void* LinkStack_Top(Stack* stack);
int LinkStack_GetSize(Stack* stack);
#endif
linkstack.c 文件
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "linklist.h"
#include "linkstack.h"
//注意栈的业务节点嵌套在链表一格的节点中的
//通过底层函数把用户的业务数据通过指针整合到栈的业务节点中
//实际栈只是链表一格业务节点的一个域而已
//创建一个栈的链式存储相当于创建一个线性表的链式存储
Stack* LinkStack_Create()
{
return LinkList_Create();
}
//销毁栈相当于销毁链表
bool LinkStack_Destory(Stack* stack)
{
bool ret;
//先清空栈
ret = LinkStack_Clear(stack);
if (ret == false)
{
return false;
}
//销毁链表
ret = LinkList_Destory(stack);
if (ret == false)
{
return false;
}
return true;
}
//清空栈的时候涉及到栈元素生命周期的管理
//注意所有栈的元素都是malloc出来的
//要把所有元素弹出,并且释放内存
bool LinkStack_Clear(Stack* stack)
{
if (stack == NULL)
{
return false;
}
while(LinkStack_GetSize(stack) > 0)
{
LinkStack_Pop(stack); //在这个函数中释放内存了
}
return true;
}
//向栈添加元素相当于向链表头部插入元素
//栈的业务节点void* item转化为链表的业务节点ListNode* listnode
bool LinkStack_Push(Stack* stack, void* item)
{
LinkStackNode* linkstackdata = NULL;
bool ret;
linkstackdata = (LinkStackNode*)malloc(sizeof(LinkStackNode));
if (linkstackdata == NULL)
{
return false;
}
memset(linkstackdata,0,sizeof(LinkStackNode));
//先创建出链表一格,链表一格里添加栈的业务节点
//栈的业务节点赋值
linkstackdata->item = item;
//stackdata 的首地址等于 stackdata->node 的地址 连接链表关系的节点
//链表头部插入链表格,0号位置
ret = LinkList_InsertOneNode(stack ,linkstackdata, 0);
//插入失败,释放内存
if (ret == false)
{
if (linkstackdata != NULL)
{
free(linkstackdata);
linkstackdata = NULL;
return false;
}
}
return true;
}
//从栈顶弹出元素相当于从链表头部删除元素
void* LinkStack_Pop(Stack* stack)
{
void* ret = NULL; //栈的业务节点
LinkStackNode* linkstackdata = NULL; //链表的业务节点包含了栈的业务节点
if (LinkStack_GetSize(stack) <= 0)
{
return NULL;
}
linkstackdata = (LinkStackNode* )LinkList_DeleteOneNode(stack,0);
if (linkstackdata == NULL)
{
return NULL;
}
ret = (void*)linkstackdata->item;
//因为push中 LinkList_InsertOneNode之前分配了内存
//所以在Pop中 LinkList_DeleteOneNode之后释放内存
free(linkstackdata);
linkstackdata = NULL;
return ret;
}
//获取栈顶元素相当于获得链表0号位置元素中的iten域的数据
void* LinkStack_Top(Stack* stack)
{
void* ret = NULL;
LinkStackNode* linkstackdata = NULL;
if (LinkStack_GetSize(stack) <= 0)
{
return NULL;
}
linkstackdata = (LinkStackNode* )LinkList_GetOneNode(stack,0);
if (linkstackdata == NULL)
{
return NULL;
}
ret = (void*)linkstackdata->item;
return ret;
}
//求栈的大小相当于求线性表的length
int LinkStack_GetSize(Stack* stack)
{
int ret = 0;
ret = LinkList_GetLength(stack);
return ret;
}
/*********************************测试代码*******************/
/*
void main()
{
int i = 0;
int aa[10] = {0};
Stack* stack = NULL;
stack = LinkStack_Create();
if (stack == NULL)
{
printf("创建链式栈失败");
}
for (i = 0; i < 5; i++)
{
aa[i] = aa[i] + i +1;
LinkStack_Push(stack,&aa[i]);
}
printf("栈的大小是:%d \n",LinkStack_GetSize(stack));
printf("栈顶元素是:%d \n",*((int*)LinkStack_Top(stack)));
//一次弹出元素
while(LinkStack_GetSize(stack) > 0)
{
printf("栈一次弹出元素:%d \n",*((int*)LinkStack_Pop(stack)));
}
//
LinkStack_Destory(stack);
system("pause");
}
*/
可能会调用其它头文件或源文件,如果调用,请翻看我的其它博客,对其头文件或源文件的实现方式。
good luck !