重头开始嵌入式第三十九天（数据结构 栈）
栈
目录
栈的定义
栈是一种数据结构，它具有以下特点：
1. 只能在一端进行插入和删除操作，这一端被称为栈顶。
2. 遵循“后进先出”（Last In First Out，LIFO）的原则。也就是说，最后进入栈的元素最先被弹出。
3. 可以用数组或链表来实现。
例如，把书一本一本叠放在桌子上，只能从最上面取书或放书，这就类似栈的操作。后放上去的书先被拿走，符合“后进先出”原则。
栈的分类
栈主要有以下两种分类：
一、从存储结构角度分类
1. 顺序栈：
- 利用一组连续的存储单元依次存放自栈底到栈顶的数据元素。
- 类似于在一个固定大小的数组中进行栈的操作，通过指针来指示栈顶位置。
- 优点是存储结构简单，容易实现，访问元素速度快。缺点是需要事先确定栈的大小，可能会出现栈溢出或空间浪费的情况。
2. 链栈：
- 采用链表的形式存储栈元素，每个节点包含数据域和指向下一个节点的指针域。
- 栈顶在链表的头部，进行入栈和出栈操作时只需要修改栈顶指针。
- 优点是可以根据需要动态地分配内存空间，不会出现栈溢出的情况。缺点是需要额外的存储空间来存储指针，访问元素的速度相对较慢。
二、从应用场景角度分类
1. 表达式求值栈：
- 在计算机中对算术表达式进行求值时，常常使用两个栈，一个用于存放操作数，另一个用于存放运算符。
- 通过特定的算法，根据运算符的优先级进行计算，实现表达式的求值。
2. 函数调用栈：
- 当程序执行函数调用时，会将当前函数的状态（如返回地址、局部变量等）压入栈中。
- 当函数执行完毕后，从栈中弹出该函数的状态，恢复到调用前的状态，继续执行调用函数的后续代码。
栈的类型
顺序栈
1.栈的创建
SeqStack* CreateSeqStack(int len)
{
SeqStack* ss = malloc(sizeof(SeqStack));
if(NULL == ss)
{
perror("create seq stack malloc");
return NULL;
}
ss->head= malloc(sizeof(DATATYPE)*len);
if(NULL == ss->head)
{
perror("create seq stack malloc2");
return NULL;
}
ss->tlen= len;
ss->top = 0;
return ss;
}2.栈的销毁
int DestroySeqStack(SeqStack* ss)
{
if(IsEmptySeqStack(ss))
{
free(ss);
return 0;
}
while(ss->top)
PopSeqStack(ss);
free(ss);
return 0;
}3.入栈
int PushSeqStack(SeqStack* ss, DATATYPE*data)
{
if(IsFullSeqStack(ss))
{
return 1;
}
memcpy(&ss->head[ss->top++],data,sizeof(DATATYPE));
return 0;
}4.出栈
int PopSeqStack(SeqStack*ss)
{
if(IsEmptySeqStack(ss))
{
return 1;
}
ss->top--;
return 0;
}5.判断栈满
nt IsFullSeqStack(SeqStack*ss)
{
return ss->tlen == ss->top;
}6.判断栈空
nt IsEmptySeqStack(SeqStack*ss)
{
return ss->top == 0;
}7.获得栈顶元素
DATATYPE* GetTopSeqStack(SeqStack* ss)
{
return &ss->head[ss->top-1];
}
8.判断栈长
int GetSizeSeqStack(SeqStack*ss)
{
return ss->top;
}
链栈
1.栈的创建
LinkStack* CreateLinkStack()
{
LinkStack* ls = (LinkStack*) malloc(sizeof(LinkStack));
if(NULL == ls)
{
perror("CreateSLinkList malloc");
return NULL;
}
ls->top = NULL;
ls->clen = 0 ;
return ls;
}2.栈的销毁
nt DestroyLinkStack(LinkStack*ls)
{
int len = GetSizeLinkStack(ls);
int i = 0 ;
for(i=0;i<len;i++)
{
PopLinkStack(ls);
}
free(ls);
return 0;
}3.入栈
int PushLinkStack(LinkStack*ls ,DATATYPE*data)
{
LinkStackNode*newnode = (LinkStackNode*)malloc(sizeof(LinkStackNode));
if(NULL == newnode)
{
perror("push malloc");
return 1;
}
memcpy(&newnode->data,data,sizeof(DATATYPE));
newnode->next = NULL;
newnode->next= ls->top;
ls->top = newnode;
ls->clen++;
return 0;
}4.出栈
int PopLinkStack(LinkStack*ls)
{
if(IsEmptyLinkStack(ls))
{
return 1;
}
LinkStackNode* tmp = ls->top;
ls->top=ls->top->next;
free(tmp);
ls->clen--;
return 0;
}5.判断栈满
nt IsFullLinkStack(SeqStack*ss)
{
return ss->top == ss->clne;
}6.判断栈空
int IsEmptyLinkStack(LinkStack*ls)
{
return ls->clen==0;
}7.获得栈顶元素
DATATYPE* GetTopLinkStack(LinkStack*ls)
{
if(IsEmptyLinkStack(ls))
{
return NULL;
}
else
{
return &ls->top->data ;
}
}8.判断栈长
int GetSizeLinkStack(LinkStack* ls)
{
return ls->clen;
}原文地址：https://blog.csdn.net/qq_64792908/article/details/142202957
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！