自学内容网 自学内容网

重头开始嵌入式第三十九天(数据结构 栈)

目录

栈的定义

栈的分类

栈的类型

顺序栈

1.栈的创建

2.栈的销毁

3.入栈

4.出栈

5.判断栈满

6.判断栈空

7.获得栈顶元素

8.判断栈长

链栈

1.栈的创建

2.栈的销毁

3.入栈

4.出栈

5.判断栈满

6.判断栈空

7.获得栈顶元素

8.判断栈长


栈的定义

栈是一种数据结构,它具有以下特点:

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)!