7.4 C/C++ 实现链表栈
【摘要】 相对于顺序栈,链表栈的内存使用更加灵活,因为链表栈的内存空间是通过动态分配获得的,它不需要在创建时确定其大小,而是根据需要逐个分配节点。当需要压入一个新的元素时,只需要分配一个新的节点,并将其插入到链表的头部;当需要弹出栈顶元素时,只需要删除链表头部的节点,并释放其所占用的内存空间即可。由于链表栈的空间利用率更高,因此在实际应用中,链表栈通常比顺序栈更受欢迎。在实现上,链表栈通过使用mall...
相对于顺序栈,链表栈的内存使用更加灵活,因为链表栈的内存空间是通过动态分配获得的,它不需要在创建时确定其大小,而是根据需要逐个分配节点。当需要压入一个新的元素时,只需要分配一个新的节点,并将其插入到链表的头部;当需要弹出栈顶元素时,只需要删除链表头部的节点,并释放其所占用的内存空间即可。由于链表栈的空间利用率更高,因此在实际应用中,链表栈通常比顺序栈更受欢迎。
在实现上,链表栈通过使用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;
}
本文作者: 王瑞
本文链接: https://www.lyshark.com/post/a8502db9.html
版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)