文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

C语言 栈与数组的实现详解

2024-04-02 19:55

关注

栈的实现

首先我们思考一个问题,什么是栈?

栈是数据结构的一种,栈在我们日常编码中遇到的非常多,很多人对栈的接触可能仅仅局限在 递归使用的是栈 和 StackOverflowException,栈是一种后进先出的数据结构(可以想象生化金字塔的牢房和生化角斗场的狗洞)。

栈的定义

栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素

栈的应用广泛,比如你的程序执行查看调用堆栈、计算机四则加减运算、算法的非递归形式、括号匹配问题等等。所以栈也是必须掌握的一门数据结构。最简单大家都经历过,你拿一本书上下叠在一起,就是一个后进先出的过程,你可以把它看成一个栈。下面我们介绍数组实现的栈两种形式。

数组实现

静态栈

一般不推荐使用这种方法,因为当空间不够用时,增容会有点麻烦,不实用。

typedef struct Stack
{ 
    STDataType _a[];  //STDataType 为int宏定义,当然你也可以将它定义为其他类型,宏定义是为了换栈类型的时候方便一点
    int _top; // 栈顶
    int _capacity; // 容量
}Stack;

动态栈

相比静态栈,动态栈空间不够时可以直接时用realloc动态扩容,但是动态扩会有一定程度的消耗,我们会直接扩容一倍,当使用不完时会造成一定程度的空间浪费。

typedef struct Stack
{ 
    STDataType* _a;//指向一块开辟出来的连续空间的指针
    int _top; // 栈顶
    int _capacity; // 容量
}Stack;

栈要实现的操作

// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);

栈的初始化

void StackInit(Stack* ps)
{
    ps->_a = NULL; //初始化时将指针指向空,此时没有开辟空间
    //这里可以将top赋值为0,也可以赋值为-1。
    ps->_top = -1;  //赋值为0时表示top为栈顶元素的下一个位置的下标,赋值为-1时top为栈顶元素的下标
    ps->_capacity = 0; //栈的容量
}

入栈

void StackPush(Stack* ps, STDataType data)
{
    assert(ps);
    //考虑要不要增容
    //当top为0时判断条件为
    //if(ps->top==ps->_capacity)
    if (ps->_top+1 == ps->_capacity)//当栈满时进入
    {
        //判断当前栈的容量是否为0,为0的话开辟4个空间,不为0时扩容一倍
        int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
        STDataType* tmp = realloc(ps->_a, sizeof(STDataType) * newcapacity);
        if (tmp == NULL)
        {
            exit(-1);
        }
        ps->_a = tmp;
        ps->_capacity = newcapacity;
    }
    //扩容完成,或者不用扩容,开始插入
    ps->_top++;
    ps->_a[ps->_top] = data;
    //当top为0时插入操作
    //ps->_a[ps->_top] = data;
    //ps->_top++;
}

出栈

void StackPop(Stack* ps)
{
    assert(ps);
    //判断是否为空
    assert(!StackEmpty(ps));//暴力判断
    //if (top==-1)//温柔判断
    //{
    //  printf("栈已经空了!\n");
    //  exit(-1); //甩出异常
    //}
    ps->_top--;
}

取栈顶元素

STDataType StackTop(Stack* ps)
{
    assert(ps);
    //判断是否为空,为空甩出异常。
    assert(!StackEmpty(ps));
    //if (!StackEmpty(ps)) {
    //  printf("栈为空!\n");
    //  exit(-1);
    //}
    return ps->_a[ps->_top]; //返回栈顶元素
}

判断栈中有几个有效数据

//取出栈里有效元素个数。
int StackSize(Stack* ps)
{
    assert(ps);
    return ps->_top+1; 
}

判断栈是否为空

bool StackEmpty(Stack* ps)
{
    assert(ps);
    return ps->_top == -1;  //ps->_top为-1返回true,否则返回false.
​
}

销毁栈

销毁栈是必不可少的的一步,如果没有销毁的话会造成内存泄露

void StackDestroy(Stack* ps)
{
    assert(ps);
    free(ps->_a);
    ps->_a = NULL;
    ps->_top = -1;
    ps->_capacity = 0;
}

链栈

最后介绍一下链栈,这里就不实现了有兴趣的话可以自己实现一下。

链栈和链表一样的,也是通指针将各个数据块链接起来的

设计链栈是最好设计为双向链表,否则当你设计为用尾作栈顶是出栈效率低。

用头做栈顶时,头插头删,可以设计为单链表。

到此这篇关于C语言 栈与数组的实现详解的文章就介绍到这了,更多相关C语言 栈与数组内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯