【数据结构和算法初阶(C语言)】栈的概念和实现(后进先出---后来者居上的神奇线性结构带来的惊喜体验)

本文主要是介绍【数据结构和算法初阶(C语言)】栈的概念和实现(后进先出---后来者居上的神奇线性结构带来的惊喜体验),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1.栈

1.1栈的概念及结构

2.栈的实现 

3.栈结构对数据的处理方式 

3.1对栈进行初始化

 

3.2 从栈顶添加元素

3.3 打印栈元素

3.4移除栈顶元素

3.5获取栈顶元素 

3.6获取栈中的有效个数

3.7 判断链表是否为空

3.9 销毁栈空间

4.结语及整个源码


1.栈

1.1栈的概念及结构

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。

进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。

栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。

出栈:栈的删除操作叫做出栈。出数据也在栈顶。  

栈中的数据后面进的先出,也就是说不能够任意访问,添加和删除数据只能在栈顶进行操作。

入栈过程图解:

 

出栈过程图解:

2.栈的实现 

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小.不用去修改指针

使用数组实现图解:

使用链表实现图解:

 

实现栈最好的方式就是使用数组的方式来实现:

静态数组定义栈的方式:

typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType _a[N];int _top; // 栈顶
}Stack;

但是由于空间指定的问题,实际使用较小,所以最适合栈的实现方式就是:动态数组定义栈 

动态数组定义栈的方式:

 

typedef int STDataType;//直接定义动态版本的栈  栈顶表示就是要插入
typedef struct  Stack
{STDataType* arr;//定义指向栈空间的指针int top;//栈顶int capcity;//定义容量}Stack;

3.栈结构对数据的处理方式 

3.1对栈进行初始化

首先用户创建一个栈变量过后,我们就要将这个栈首先初始化,方便后续用栈来管理数据。

在初始化动作中,指向栈空间的指针应该置空,后续开辟空间的时候再给定值。容量最初也是0,无可争议。但是对于栈顶的定义要注意初始值的区别。

top栈顶后续会用于访问栈顶元素也就是作为我们数组的下标,如果初始为1,此时栈里面是没有元素的,那么后续进入数据就要注意,栈的大小是top的大小。如果开始为0,栈的大小是top+1.当然这里大家自己实现的时候自由选择定义就好:

void SInit(Stack* pc)
{pc->arr = NULL;pc->capcity = 0;pc->top = 0;
}

 

3.2 从栈顶添加元素

首先:先断言一下我们传入的结构体指针,看是否存在这样一个栈结构,再开始后续操作。

第二:添加元素前我们就要考虑我们这个栈的空间还够不够,不够就要进行扩容。这里由于开始的时候,指向栈空间的指针为空,所以realloc函数会直接开辟空间,所以就没有malloc单独申请空间了。

第三:将对应的容量增加,top增加,将我们每个值赋值。

void StackPush(Stack* pc, STDataType data)
{assert(pc);if (pc->top ==pc->capcity){STDataType* a = (STDataType*)realloc(pc->arr, (pc->capcity+2)*sizeof(STDataType) );if (a == NULL){perror("realloc");}pc->arr = a;pc->capcity+=2;}pc->arr[pc->top] = data;pc->top++;}

3.3 打印栈元素

使用遍历的方法打印栈空间中的每一个元素。

void  StackPrint(Stack* pc){assert(pc);int i = 0;for (i = 0; i < pc->top; i++){printf("%d ", pc->arr[i]);}
}

我们来测试一下刚才的入栈: 

3.4移除栈顶元素

也就是顺序表中的尾部删除

首先还是要断言一下传入的指针是否为空

第二,我们移除尾部元素,并不是把尾部元素置空,只是将top--,那么就访问不到那个元素,后续增加元素就会覆盖,容量也没有必要减去了。其次,每次top--,那么就要判断一下top减为或者已经小于0了就不执行了。

 

void StackPop(Stack* pc)
{assert(pc);assert(pc->top > 0);//top减为0了就别在减去了pc->top--;
}

 

3.5获取栈顶元素 

获取栈顶元素,就是通过top作为下标来访问我们的尾部元素,注意如果top初始值为0,那么直接使用我们的top作为下标即可,但是由于我们每次添加元素后都要++,所以要-1,如果是以1为top的初始值,那么此时的top需要-2.

STDataType StackTop(Stack* pc)
{assert(pc);return pc->arr[pc->top-1];
}

 

3.6获取栈中的有效个数

也就是我们top 

int StackSize(Stack* pc)
{assert(pc);return pc->top;
}

.

3.7 判断链表是否为空

我们可以判断此时的容量是否为空,因为就是top为0,但是栈依旧存在,只是无法访问每个元素。

bool StackEmpty(Stack* pc)
{assert(pc);return pc->capcity == 0;
}

3.9 销毁栈空间

我们的空间是在堆区上申请来的,用完记得销毁还给操作系统,不让后续造成内存泄漏。

void StackDestory(Stack* pc)
{assert(pc);free(pc->arr);pc->arr == NULL;pc->top = pc->capcity = 0;
}

4.结语及整个源码

以上就是本期的所有内容,知识含量蛮多,大家可以配合解释和原码运行理解。创作不易,大家如果觉得还可以的话,欢迎大家三连,有问题的地方欢迎大家指正,一起交流学习,一起成长,我是Nicn,正在c++方向前行的奋斗者,数据结构内容持续更新中,感谢大家的关注与喜欢。

附上源码:

test.c

#include"stack.h"
int main()
{//创建栈Stack stack = { 0 };//初始化栈SInit(&stack);StackPush(&stack, 1);StackPush(&stack, 2);StackPush(&stack, 3);StackPush(&stack, 4);StackPrint(&stack);printf("\n");StackPop(&stack);StackPrint(&stack);printf("\n");/*printf("%d ", StackTop(&stack));*/printf("%d ", StackSize(&stack));return 0;
}

stack.c

#include"stack.h"void SInit(Stack* pc)
{pc->arr = NULL;pc->capcity = 0;pc->top = 0;
}void StackPush(Stack* pc, STDataType data)
{assert(pc);if (pc->top ==pc->capcity){STDataType* a = (STDataType*)realloc(pc->arr, (pc->capcity+2)*sizeof(STDataType) );if (a == NULL){perror("realloc");}pc->arr = a;pc->capcity+=2;}pc->arr[pc->top] = data;pc->top++;}void  StackPrint(Stack* pc){assert(pc);int i = 0;for (i = 0; i < pc->top; i++){printf("%d ", pc->arr[i]);}
}void StackPop(Stack* pc)
{assert(pc);assert(pc->top > 0);//top减为0了就别在减去了pc->top--;
}STDataType StackTop(Stack* pc)
{assert(pc);return pc->arr[pc->top-1];
}
bool StackEmpty(Stack* pc)
{assert(pc);return pc->capcity == 0;
}int StackSize(Stack* pc)
{assert(pc);return pc->top;
}void StackDestory(Stack* pc)
{assert(pc);free(pc->arr);pc->arr == NULL;pc->top = pc->capcity = 0;
}

stack.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;//直接定义动态版本的栈  栈顶表示就是要插入
typedef struct  Stack
{STDataType* arr;//定义指向栈空间的指针int top;//栈顶int capcity;//定义容量}Stack;void SInit(Stack* pc);
//入栈
void StackPush(Stack* pc, STDataType data);
//出栈
void StackPop(Stack* pc);
//获取栈顶元素
STDataType StackTop(Stack* pc);
//检查栈是否为空
bool StackEmpty(Stack* pc);
//栈的大小
int StackSize(Stack* pc);
//打印
void  StackPrint(Stack* pc);
//销毁栈
void StackDestory(Stack* pc);

 

这篇关于【数据结构和算法初阶(C语言)】栈的概念和实现(后进先出---后来者居上的神奇线性结构带来的惊喜体验)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/799383

相关文章

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

Python+PyQt5实现多屏幕协同播放功能

《Python+PyQt5实现多屏幕协同播放功能》在现代会议展示、数字广告、展览展示等场景中,多屏幕协同播放已成为刚需,下面我们就来看看如何利用Python和PyQt5开发一套功能强大的跨屏播控系统吧... 目录一、项目概述:突破传统播放限制二、核心技术解析2.1 多屏管理机制2.2 播放引擎设计2.3 专

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

idea中创建新类时自动添加注释的实现

《idea中创建新类时自动添加注释的实现》在每次使用idea创建一个新类时,过了一段时间发现看不懂这个类是用来干嘛的,为了解决这个问题,我们可以设置在创建一个新类时自动添加注释,帮助我们理解这个类的用... 目录前言:详细操作:步骤一:点击上方的 文件(File),点击&nbmyHIgsp;设置(Setti

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

MySQL大表数据的分区与分库分表的实现

《MySQL大表数据的分区与分库分表的实现》数据库的分区和分库分表是两种常用的技术方案,本文主要介绍了MySQL大表数据的分区与分库分表的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有... 目录1. mysql大表数据的分区1.1 什么是分区?1.2 分区的类型1.3 分区的优点1.4 分