线性表：链栈算法实现

骑猪看日落 2022-05-31 13:10 192阅读 0赞

# 链栈介绍 #

**链栈也是我们所说的采用链式存储结构的栈**。往往通过单链表的方式来实现，使用链式栈的优点在于它能够克服用数组实现的顺序栈空间利用率不高的特点，但是需要为每个栈元素分配额外的指针空间用来存放指针域。**栈 是一种受限制的线性表，它具有后进先出（Last-In-First-Out）的特性**。所以呢本次**编写链栈呢 采用以前写的企业级单链表形式编写**。**不知道企业级单链表？请看[数据结构与算法：企业级链表实现（超详细）][Link 1]，感觉这种思想超赞，你值得拥有**。

# 链栈相关算法接口 #

**同样对外提供LinkStack类型也就是void\* ，对用户隐藏底层代码实现，链表结点只维护链表结构和用户数据分类**。用户数据只需在业务数据结构体最上面提供4个字节的空间即可。

#pragma once
    #ifndef __LINKSTACK_H__
    #define __LINKSTACK_H__
    #define MAXSIZE 1024
    typedef enum { FALSE, TRUE } Boolean;
    
    typedef struct StackNode
    {
    	struct StackNode* next;
    }StackNode;
    
    typedef void* LinkStack;
    
    //初始化
    LinkStack Init_LinkStack();
    //压栈
    void Push_LinkStack(LinkStack stack, void* data);
    //弹栈
    void* Pop_LinkStack(LinkStack stack);
    //获取栈顶
    void* Top_LinkStack(LinkStack stack);
    //是否为空栈
    //1 是空，0 非空
    int IsEmpty_LinkStack(LinkStack stack);
    //栈元素个数
    int Size_LinkStack(LinkStack stack);
    //销毁 栈
    void Destroy_LinkStack(LinkStack stack);
    
    #endif // !__LINKSTACK_H__

# 链栈相关算法实现 #

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include "LinkStack.h"
    
    //链栈
    typedef struct LStack
    {
    	StackNode header;//链栈头结点header.next 指向栈顶元素
    	int size;
    }LStack;
    
    //初始化
    LinkStack Init_LinkStack()
    {
    	LStack* stack = (LStack*)malloc(sizeof(LStack));
    	stack->header.next = NULL;
    	stack->size = 0;
    	return stack;
    }
    //压栈
    void Push_LinkStack(LinkStack stack, void* data)
    {
    	if (stack == NULL || data == NULL)
    	{
    		return;
    	}
    	LStack* myStack = stack;
    	((StackNode*)data)->next = myStack->header.next;
    	myStack->header.next = data;
    	myStack->size++;
    }
    //弹栈
    void* Pop_LinkStack(LinkStack stack)
    {
    	LStack* myStack = stack;
    	if (stack == NULL || myStack->size == 0)
    	{
    		return NULL;
    	}
    	StackNode* node = myStack->header.next;
    	myStack->header.next = node->next;
    	myStack->size--;
    	return node;
    }
    //获取栈顶
    void* Top_LinkStack(LinkStack stack)
    {
    	LStack* myStack = stack;
    	if (stack == NULL || myStack->size == 0)
    	{
    		return NULL;
    	}
    	StackNode* node = myStack->header.next;
    	return node;
    }
    //是否为空栈
    //1 是空，0 非空
    int IsEmpty_LinkStack(LinkStack stack)
    {
    	LStack* myStack = stack;
    	if (stack == NULL)
    	{
    		return 1;
    	}
    	if (myStack->size == 0)
    	{
    		return 1;
    	}
    	return 0;
    }
    //栈元素个数
    int Size_LinkStack(LinkStack stack)
    {
    	LStack* myStack = stack;
    	if (stack == NULL)
    	{
    		return 0;
    	}
    	return myStack->size;
    }
    //销毁 栈
    void Destroy_LinkStack(LinkStack stack)
    {
    	LStack* myStack = stack;
    	if (stack == NULL)
    	{
    		return;
    	}
    	free(myStack);
    	myStack = NULL;
    }

# 代码运行检测 #

## Main.c测试代码 ##

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include "LinkStack.h"
    //测试 数据
    typedef struct Person
    {
    	StackNode node;
    	char name[64];
    	int age;
    }Person;
    
    int main(int argc, char *argv[])
    {
    	Person p1 = { NULL,"Lily",11 };
    	Person p2 = { NULL,"Laymond",21 };
    	Person p3 = { NULL,"John",31 };
    	Person p4 = { NULL,"Leo",41 };
    	Person p5 = { NULL,"Zeo",51 };
    	LinkStack stack = Init_LinkStack();
    	Push_LinkStack(stack, &p1);
    	Push_LinkStack(stack, &p2);
    	Push_LinkStack(stack, &p3);
    	Push_LinkStack(stack, &p4);
    	Push_LinkStack(stack, &p5);
    	printf("栈顶元素:name=%s,age=%d\n", ((Person*)Top_LinkStack(stack))->name, ((Person*)Top_LinkStack(stack))->age);
    	printf("栈的元素个数:%d\n", Size_LinkStack(stack));
    	Person* p = NULL;
    	while (!IsEmpty_LinkStack(stack))
    	{
    		p = Pop_LinkStack(stack);
    		printf("name=%s,age=%d\n", p->name, p->age);
    	}
    	printf("栈的元素个数:%d\n", Size_LinkStack(stack));
    	Destroy_LinkStack(stack);
    	return 0;
    }

## 运行结果 ##

![20180225230835869][]

[Link 1]: http://blog.csdn.net/qq_29542611/article/details/79342970
[20180225230835869]: /images/20220531/c2c67c4f0f324412b94444df788319b5.png