数据结构 栈(一篇基本掌握)

这篇具有很好参考价值的文章主要介绍了数据结构 栈(一篇基本掌握)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


绪论

        时间就是生命,时间就是速度,时间就是气力。——郭沫若;本章继续学习数据结构,本章主要讲了什么是栈以及栈的基本功能和实现方法。

数据结构 栈(一篇基本掌握),数据结构,数据结构

 文章来源地址https://www.toymoban.com/news/detail-652339.html

 话不多说安全带系好,发车啦(建议电脑观看)


附:红色,部分为重点部分;蓝颜色为需要记忆的部分(不是死记硬背哈,多敲);黑色加粗或者其余颜色为次重点;黑色为描述需要


目录

1.栈的实现

1.1栈的结构​编辑

1.2栈的初始化

1.3栈的摧毁

1.4将数据插入栈中(入栈)

1.5将数据从栈中删除(出栈)

1.6查看栈顶元素

1.7查看栈中有几个元素

1.8判断栈是否是空的

2.实现栈的全部代码


知识点:

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶
可以把栈想成是一个水杯,水都是从一端进并从同一端出的(水也是后进的先出),放水进去时是压栈,把水倒出来是出栈。

数据结构 栈(一篇基本掌握),数据结构,数据结构

细节:

 

栈的所要实现的框架有:栈可以由顺序表或者链表来作为底层实现,下面主要讲以顺序表来实现的过程(因为相比于链表,顺序表在尾端插入删除数据的消耗较低)

  1. 栈的结构
    1. 一个数组变量
    2. 记录元素个数的变量
    3. 一个记录容量的变量
  2. 栈所要实现的功能
    1. 初始化栈
    2. 摧毁栈
    3. 入栈
    4. 出栈
    5. 查看栈顶元素
    6. 查看栈中的元素个数
    7. 判断栈是否为空栈

1.栈的实现

1.1栈的结构数据结构 栈(一篇基本掌握),数据结构,数据结构

 

栈的结构:由数组变量、已经两个变量组成

typedef int datetype;//类型重命名,把int 重命名为 datetype 这样方便于改变结构中的存的类型
typedef struct stack//类型重命名
{
	datetype* date;//数组
	int size;//记录元素个数
	int capacity;//容量
}stack;//重命名为stack(避免每次都要写struct的繁琐)

1.2栈的初始化

主要是为了申请空间、以及初始化size、capacity。

void StackInit(stack* ps)
{
    //初始化两个变量
    ps->capacity = 3;//容量初始为3
    ps->size = 0;//元素的个数0

    ps->date = malloc(sizeof(datetype) * ps->capacity);//用malloc给数组开辟datetype类型的容量个大小的空间
    //此处就是开辟了 4(int) * 3(capacity) = 12 byte 大小的空间
    if (ps->date == NULL)//判断是否申请成功
    {
        perror("malloc");
        return;
    }
}

其中注意点是:把size定义成0这样方便于我们在顺序表中插入数据(插入数据的位置下标就是size),并且这样我们在拿出顶部数据时就需要-1后才能取到顶部数据了(有些程序员会定义成-1这样size就表示栈顶元素的下标,+1为栈中的元素个数)

1.3栈的摧毁

因为此处用的是顺序表来实现所以其摧毁方法就和顺序表一样

void StackDestroy(stack* ps)
{
    assert(ps);//判空
    ps->capacity = ps->size= 0;//置为0
    free(ps->date);//释放所借的空间
    ps->date = NULL;//将用完的指针置为NULL
}

1.4将数据插入栈中(入栈)

在date数组中插入数据,其中已经知道了size下标处就是数组中要插入数据的位置即date[ps->size]

void StackPush(stack* ps, datetype x)
{
    assert(ps);//判空
    if (ps->size== ps->capacity)//注意要检查空间是否足够
    {
        datetype* tmp = (datetype*)realloc(ps->date, sizeof(datetype) * ps->capacity * 2);//扩容扩大比原容量大两倍的空间大小
        if (tmp == NULL)//检查是否扩容成功
        {
            perror("realloc");
            return;
        }
        ps->date = tmp;//把tmp扩容好的空间,给到date
        ps->capacity *= 2;//注意别忘把capacity增加
    }
    ps->date[ps->size] = x;//在date的size下标位置处插入数据x
    ps->size++;//元素个数增加
}

1.5将数据从栈中删除(出栈)

对于出栈我们的方法和顺序表一样仅仅只是改变size元素个数

void StackPop(stack* ps)
{
    assert(ps);//为假就会报错
    assert(!StackEmpty(ps));//判断一下栈是不是空的
    ps->size--;//元素个数减一个
}

1.6查看栈顶元素

栈顶元素的下标是元素个数size-1故:

datetype StackTop(stack* ps)
{
    assert(ps);
    return ps->date[ps->size - 1];//返回栈顶元素
}

1.7查看栈中有几个元素

int StackSize(stack* ps)
{
    assert(ps);
    return ps->size;//返回size即可
}

1.8判断栈是否是空的

bool StackEmpty(stack* ps)
{
    assert(ps);
    return ps->size == 0;//等于0返回真,反之则为假
}

2.实现栈的全部代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

	typedef int datetype;

	typedef struct stack
	{
		datetype* date;
		int size;
		int capacity;
	}stack;



bool StackEmpty(stack* ps)
{
    assert(ps);
    return ps->size == 0;//等于0返回真,反之则为假
}



void StackInit(stack* ps)
{
    //初始化两个变量
    ps->capacity = 3;//容量初始为3
    ps->size = 0;//注意size指向的是下一个堆顶的位置

    ps->date = malloc(sizeof(datetype) * ps->capacity);//用malloc给数组开辟datetype类型的容量个大小的空间
    //此处就是开辟了 4(int) * 3(capacity) = 12 byte 大小的空间
    if (ps->date == NULL)//判断是否申请成功
    {
        perror("malloc");
        return;
    }
}

void StackDestroy(stack* ps)
{
    assert(ps);//判空
    ps->capacity = ps->size = 0;//置为0
    free(ps->date);//释放所借的空间
    ps->date = NULL;//将用完的指针置为NULL
}


void StackPush(stack* ps, datetype x)
{
    assert(ps);//判空
    if (ps->size == ps->capacity)//检查空间是否足够
    {
        datetype* tmp = (datetype*)realloc(ps->date, sizeof(datetype) * ps->capacity * 2);//扩容扩大比原容量大两倍的空间大小
        if (tmp == NULL)//检查是否扩容成功
        {
            perror("realloc");
            return;
        }
        ps->date = tmp;//把tmp扩容好的空间,给到date
        ps->capacity *= 2;//注意别忘把capacity增加
    }
    ps->date[ps->size] = x;//在date的top下标位置处插入数据x
    ps->size++;//元素个数增加
}

void StackPop(stack* ps)
{
    assert(ps);//为假就会报错
    assert(!StackEmpty(ps));//判断一下栈是不是空的
    ps->size--;//元素个数减一个
}

datetype StackTop(stack* ps)
{
    assert(ps);
    return ps->date[ps->size - 1];
}

int StackSize(stack* ps)
{
    assert(ps);
    return ps->size;
}

 

如果有任何问题欢迎讨论哈!

如果觉得这篇文章对你有所帮助的话点点赞吧!

持续更新大量数据结构细致内容,早关注不迷路。

 

 

 

到了这里,关于数据结构 栈(一篇基本掌握)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构--》掌握数据结构中的排序算法

            当我们面对海量数据时,如何高效地将其排序是数据结构领域中一个重要的问题。排序算法作为其中的关键部分,扮演着至关重要的角色。         无论你是初学者还是进阶者,本文将为你提供简单易懂、实用可行的知识点,帮助你更好地掌握排序算法在数据

    2024年02月08日
    浏览(43)
  • 数据结构--》掌握数据结构中的查找算法

            当你需要从大量数据中查找某个元素时,查找算法就变得非常重要。         无论你是初学者还是进阶者,本文将为你提供简单易懂、实用可行的知识点,帮助你更好地掌握查找在数据结构和算法中的重要性,进而提升算法解题的能力。接下来让我们开启数据

    2024年02月08日
    浏览(57)
  • 一篇学完:王道考研408数据结构(全)

    PDF版本附在  lengyueling.cn 对应 文章结尾,欢迎下载访问交流 数据结构在学什么 如何用程序代码把现实世界的问题信息化 如何用计算机高效地处理这些信息从而创造价值 数据结构的基本概念 什么是数据: 数据是信息的载体,是描述客观事物属性的数、字符及所有能输入到

    2023年04月08日
    浏览(46)
  • 【数据结构】一篇带你彻底了解栈

    栈:一种线性数据结构,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶 (Top), 另一端称为栈底 [Bottom]。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。即最后进入的元素最先被访问。 压栈:栈的插入操作叫做进栈/压栈

    2024年02月05日
    浏览(88)
  • 【从零开始学习数据结构 | 第一篇】树

    目录 前言:  树: 树结点之间的关系描述:  树的常见属性: 森林: ​编辑树的性质: 总结: 当谈论数据结构时,树(Tree)是一种极为重要且常用的数据结构之一。树的概念源自现实生活中的树木,它具有分层结构,由 节点(Node) 和 边(Edge) 组成,形成了一种类似于

    2024年04月16日
    浏览(51)
  • 数据结构:一篇拿捏十大排序(超详细版)

    排序: 所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性: 假定在待排序的记录序列中,存在多个具有相同的的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前, 而

    2024年02月08日
    浏览(52)
  • 【数据结构】一篇带你彻底吃透 顺序表

    顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改等功能。 顺序表一般可以分为: 静态顺序表:使用定长数组存储元素。 动态顺序表:使用动态开辟的数组存储。 而现实的顺序表大多数采用动态

    2023年04月19日
    浏览(81)
  • [数据结构 -- 手撕排序第一篇] 插入排序

    目录 1、常见的排序算法 2、插入排序的思路 2.1 基本思想 2.2 直接插入排序 2.2.1 单趟排序的思路 2.2.2 单趟排序代码实现 3、插入排序代码 4、插入排序+打印测试 5、插入排序的时间复杂度 5.1 最坏情况 5.2 最好情况 6、直接插入排序的特性总结   直接插入排序是一种简单的插入

    2024年02月12日
    浏览(56)
  • 有哪些数据结构与算法是程序员必须要掌握的?——“数据结构与算法”

    作为IT程序员,学习算法的原因主要有以下几点: 提升问题解决能力:算法可以帮助程序员分析、优化和解决复杂问题。了解算法原理和实现方式将有助于程序员更快地找到合适的解决方案。这对于解决实际工作中的问题是非常有帮助的。 提高代码效率:通过学习不同的算法

    2024年02月13日
    浏览(36)
  • 数据结构--》从线性表说起,掌握常用基础算法

    目录 初识线性表 线性表的基本操作 顺序表的定义 顺序表的基本操作 单链表的定义 单链表的基本操作  双链表的介绍 循环链表的介绍 静态链表的介绍 线性表是具有 相同 数据类型的 n (n0) 个数据元素的 有限序列 ,其中n为 表长 ,当n=0时线性表是一个 空表 。若用L命名线性

    2024年02月09日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包