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

2024-03-11 23:12
文章标签 算法 语言 实现 体验 数据结构 概念 初阶 结构 线性 神奇 带来 惊喜 后来者居上 后进先出

本文主要是介绍【数据结构和算法初阶(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。

相关文章

Nginx 配置跨域的实现及常见问题解决

Nginx 配置跨域的实现及常见问题解决

《Nginx配置跨域的实现及常见问题解决》本文主要介绍了Nginx配置跨域的实现及常见问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来... 目录1. 跨域1.1 同源策略1.2 跨域资源共享（CORS）2. Nginx 配置跨域的场景2.1
阅读更多...
Python中提取文件名扩展名的多种方法实现

Python中提取文件名扩展名的多种方法实现

《Python中提取文件名扩展名的多种方法实现》在Python编程中,经常会遇到需要从文件名中提取扩展名的场景,Python提供了多种方法来实现这一功能,不同方法适用于不同的场景和需求,包括os.pa... 目录技术背景实现步骤方法一：使用os.path.splitext方法二：使用pathlib模块方法三
阅读更多...
CSS实现元素撑满剩余空间的五种方法

CSS实现元素撑满剩余空间的五种方法

《CSS实现元素撑满剩余空间的五种方法》在日常开发中，我们经常需要让某个元素占据容器的剩余空间，本文将介绍5种不同的方法来实现这个需求，并分析各种方法的优缺点，感兴趣的朋友一起看看吧... css实现元素撑满剩余空间的5种方法 在日常开发中，我们经常需要让某个元素占据容器的剩余空间。这是一个常见的布局需求
阅读更多...
HTML5 getUserMedia API网页录音实现指南示例小结

HTML5 getUserMedia API网页录音实现指南示例小结

《HTML5getUserMediaAPI网页录音实现指南示例小结》本教程将指导你如何利用这一API，结合WebAudioAPI，实现网页录音功能,从获取音频流到处理和保存录音，整个过程将逐步... 目录1. html5 getUserMedia API简介1.1 API概念与历史1.2 功能与优势1.3
阅读更多...
Java实现删除文件中的指定内容

Java实现删除文件中的指定内容

《Java实现删除文件中的指定内容》在日常开发中,经常需要对文本文件进行批量处理,其中,删除文件中指定内容是最常见的需求之一,下面我们就来看看如何使用java实现删除文件中的指定内容吧... 目录1. 项目背景详细介绍2. 项目需求详细介绍2.1 功能需求2.2 非功能需求3. 相关技术详细介绍3.1 Ja
阅读更多...
使用Python和OpenCV库实现实时颜色识别系统

使用Python和OpenCV库实现实时颜色识别系统

《使用Python和OpenCV库实现实时颜色识别系统》：本文主要介绍使用Python和OpenCV库实现的实时颜色识别系统,这个系统能够通过摄像头捕捉视频流,并在视频中指定区域内识别主要颜色（红... 目录一、引言二、系统概述三、代码解析1. 导入库2. 颜色识别函数3. 主程序循环四、HSV色彩空间详解
阅读更多...
PostgreSQL中MVCC 机制的实现

PostgreSQL中MVCC 机制的实现

《PostgreSQL中MVCC机制的实现》本文主要介绍了PostgreSQL中MVCC机制的实现,通过多版本数据存储、快照隔离和事务ID管理实现高并发读写,具有一定的参考价值,感兴趣的可以了解一下... 目录一 MVCC 基本原理python1.1 MVCC 核心概念1.2 与传统锁机制对比二 Postg
阅读更多...
SpringBoot整合Flowable实现工作流的详细流程

SpringBoot整合Flowable实现工作流的详细流程

《SpringBoot整合Flowable实现工作流的详细流程》Flowable是一个使用Java编写的轻量级业务流程引擎,Flowable流程引擎可用于部署BPMN2.0流程定义,创建这些流程定义的... 目录1、流程引擎介绍2、创建项目3、画流程图4、开发接口4.1 Java 类梳理4.2 查看流程图4
阅读更多...
C++中零拷贝的多种实现方式

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri
阅读更多...
C++高效内存池实现减少动态分配开销的解决方案

C++高效内存池实现减少动态分配开销的解决方案

《C++高效内存池实现减少动态分配开销的解决方案》C++动态内存分配存在系统调用开销、碎片化和锁竞争等性能问题,内存池通过预分配、分块管理和缓存复用解决这些问题,下面就来了解一下... 目录一、C++内存分配的性能挑战二、内存池技术的核心原理三、主流内存池实现：TCMalloc与Jemalloc1. TCM
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2