7.4 C/C++ 实现链表栈

相对于顺序栈,链表栈的内存使用更加灵活,因为链表栈的内存空间是通过动态分配获得的,它不需要在创建时确定其大小,而是根据需要逐个分配节点。当需要压入一个新的元素时,只需要分配一个新的节点,并将其插入到链表的头部;当需要弹出栈顶元素时,只需要删除链表头部的节点,并释放其所占用的内存空间即可。由于链表栈的空间利用率更高,因此在实际应用中,链表栈通常比顺序栈更受欢迎。

在实现上,链表栈通过使用malloc函数动态开辟节点内存空间来实现入栈操作,在释放时使用free函数释放节点内存空间来实现出栈操作,这使得链表栈相对于顺序栈更加节约存储空间,也更加容易实现。

读者需自行创建头文件linkstack.h并拷贝如下链表栈代码实现;

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct StackNode
{
struct StackNode *next;
};
struct LStack
{
struct StackNode header;
int size;
};

typedef void* LinkStack;

// 初始化
LinkStack InitLinkStack()
{
struct LStack *stack = malloc(sizeof(struct LStack));
if (NULL == stack)
{
return NULL;
}

stack->header.next = NULL;
stack->size = 0;
return stack;
}

// 入栈
void PushLinkStack(LinkStack stack, void *data)
{
if (NULL == stack || NULL == data)
{
return;
}

// 先将头指针进行强转
struct LStack *ls = (struct LStack *)stack;

// 把节点进行强转
struct StackNode *node = (struct StackNode *)data;

node->next = ls->header.next;
ls->header.next = node;
++(ls->size);
}

// 出栈
void PopLinkStack(LinkStack stack)
{
if (NULL == stack)
{
return;
}

struct LStack *ls = (struct LStack *)stack;
if (ls->size == 0)
{
return;
}

// 缓存第一个节点
struct StackNode *pFirst = ls->header.next;
ls->header.next = pFirst->next;
ls->size--;
}

// 获得栈顶元素
void* TopLinkStack(LinkStack stack)
{
if (NULL == stack)
{
return NULL;
}

struct LStack *ls = (struct LStack *)stack;
if (ls->size == 0)
{
return NULL;
}

return ls->header.next;
}

// 获得大小
int SizeLinkStack(LinkStack stack)
{
if (NULL == stack)
{
return -1;
}
struct LStack *ls = (struct LStack *)stack;
return ls->size;
}

// 销毁栈
void DestroyLinkStack(LinkStack stack)
{
if (NULL != stack)
{
free(stack);
}
stack = NULL;
return;
}

在主函数中使用也很容易,首先同样定义一个Student结构体,然后通过InitLinkStack函数初始化一个链表栈,接着调用PushLinkStack函数向该栈中插入数据,最后通过循环的方式输出该栈中的元素,当输出结束后调用DestroyLinkStack函数对栈进行销毁释放内存。

#include "linkstack.h"

struct Student
{
int uid;
char name[64];
};

int main(int argc, char *argv[])
{
// 初始化栈,默认分配空间为1024
LinkStack stack = InitLinkStack();

// 穿件一些测试数据
struct Student stu1 = { 1001, "admin" };
struct Student stu2 = { 1002, "guest" };
struct Student stu3 = { 1003, "lyshark" };

// 将输入加入到栈中
PushLinkStack(stack, &stu1);
PushLinkStack(stack, &stu2);
PushLinkStack(stack, &stu3);

// 循环输出栈顶元素
while (SizeLinkStack(stack) > 0)
{
// 获得栈顶元素
struct Student *ptr = (struct Student *)TopLinkStack(stack);
printf("Uid: %d --> Name: %s \n", ptr->uid, ptr->name);
printf("当前栈大小: %d \n", SizeLinkStack(stack));
PopLinkStack(stack);
}

// 销毁栈
DestroyLinkStack(stack);
stack = NULL;

system("pause");
return 0;
}