【数据结构】千字深入浅出讲解栈(附原码 | 超详解)

🚀write in front🚀
📝个人主页:认真写博客的夏目浅石.
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝
📣系列专栏:C语言实现数据结构
💬总结:希望你看完之后,能对你有所帮助,不足请指正!共同学习交流 🖊
✉️如果无聊的话,就来逛逛我的博客栈吧stack-frame.cn
文章目录
- 前言
- 一、栈的概念
- 二、栈的结构
- 三、栈的实现
- 3.1 结构设计
- 3.2 接口总览
- 3.3 初始化
- 3.4 销毁
- 3.5 判断栈是否为空
- 3.6 入栈
- 3.7 出栈
- 3.8 取栈顶元素
- 3.9 计算栈的大小
- 四、 完整代码
- Stack.h
- Stack.c
- test.c
- 总结
前言
这几天看了数据结构的栈这一节,真的收获很大,第一次看没有动手敲代码就是感觉学了和没学一样,今天也是从新又看了一遍,并且边学边敲代码,终于算是非常理解栈这个东西了,今天就把我所学到的知识给大家分享一下。
一、栈的概念
栈 是一个特殊的 线性表
栈只允许在固定的一段进行插入和删除元素的操作。进行数据插入和删除操作的一端称为栈顶,不进行操作的一端称为栈底
栈中的元素遵守 后进先出 (LIFO - Last In First Out) 的原则。也就是先进的后出,后进的先出
栈对于数据的管理主要有两种操作:
- 压栈:栈的插入操作叫做进栈 / 压栈 / 入栈,从栈顶进行压栈。
- 出栈:栈的删除操作叫做 出栈,从栈顶进行出栈。

二、栈的结构
栈一般可以使用 数组或链表 实现。让我们分析一下使用这两种方法实现,栈的结构分别是什么样的。
在分析之前,我们要明确的一点是,栈只对 栈顶 的元素进行操作。
那么对于 顺序栈 和 链式栈 ,那个更加好呢?那必定是 顺序栈,因为使用顺序栈的 尾插尾删非常方便, 且 cpu缓存利用率也更高。而且对于顺序栈实现起来相对简单,所以我们接下来就实现 顺序栈 。
三、栈的实现
3.1 结构设计
我们既然是实现 顺序栈,那么它的结构肯定就和 顺序表 差不多:
typedef struct Stack
{STDatatype* a; // 指向动态开辟的数组int capacity; // 栈的容量int top; // 标识 栈顶的下一个位置的下标 或 栈顶的下标
}ST;
这里的 top 我们需要好好理解一下。当top的初始值不同时,top可以表示 栈顶的下一个位置的下标 或 栈顶下标。
- 当
top = 0,top表示栈顶的下一个位置的下标:

2. 当 top = -1,top 表示栈顶的下标:

top 初始值为 -1,那么需要先 ++top,再压栈。否则会越界。当 最后一次压栈时,为先 ++top 再压栈,top 最后的位置就是栈顶的下标处。
3.2 接口总览
void StackInit(ST* ps); // 初始化
void StackDestroy(ST* ps); // 销毁
void StackPush(ST* ps, STDatatype x); // 压栈
void StackPop(ST* ps); // 出栈
STDatatype StackTop(ST* ps); // 取栈顶元素
bool StackEmpty(ST* ps); // 判空
int StackSize(ST* ps); // 计算栈的大小
3.3 初始化
我们实现的是顺序栈,那么就和顺序表一样,需要创建结构体变量,传结构体的地址,进行初始化。
在初始化的时候就给栈开上四个单位的空间,并且将起始容量设定为4。
注意了我们这里设定的 top = 0,那么表示 top 为栈顶的下一个位置的下标。
void StackInit(ST* ps)
{// 结构体一定不为空,所以需要断言assert(ps);ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);if (ps->a == NULL){perror("malloc fail");exit(-1);}ps->capacity = 4;ps->top = 0;
}
3.4 销毁
对于栈的销毁,那么我们就只需要释放动态开辟的空间,将指针置空。并将 capacity 和 top 两个变量置 0即可。
void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}
3.5 判断栈是否为空
我们起初设定 top = 0,所以判断栈是否为空,那么只需要看 top 是否为0就可以了。如果为0,返回真 ;不为0,返回假。
bool StackEmpty(ST* ps)
{assert(ps);// 如果 ps->top == 0,返回真// 如果 ps->top !=0,返回假return ps->top == 0;
}
3.6 入栈
void StackPush(ST* ps, STDatatype x)
{assert(ps);// 检查容量if (ps->top == ps->capacity){STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity *= 2;}// 插入元素// top 为栈顶的下一个元素// 先插入再 ++ ps->a[ps->top] = x;ps->top++;
}
3.7 出栈
void StackPop(ST* ps)
{assert(ps);// 如果栈空,则不能删除assert(!StackEmpty(ps));ps->top--;
}
3.8 取栈顶元素
STDatatype StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}
3.9 计算栈的大小
int StackSize(ST* ps)
{assert(ps);return ps->top;
}
四、 完整代码
Stack.h
#pragma once#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>typedef int STDatatype;typedef struct Stack
{STDatatype* a;int capacity;int top; // 初始为0,表示栈顶位置下一个位置下标// 初始为-1,表示栈顶位置的下标
}ST;void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDatatype x);
void StackPop(ST* ps);
STDatatype StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);
Stack.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "Stack.h"// top 为栈顶 初识值为 -1void StackInit(ST* ps)
{// 结构体一定不为空assert(ps);ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);if (ps->a == NULL){perror("malloc fail");exit(-1);}ps->capacity = 4;ps->top = -1;
}void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}void StackPush(ST* ps, STDatatype x)
{assert(ps);// 检查容量// 此时 top 一开始为 -1,不能表示栈中元素的数目// top + 1 才是正确的if (ps->top + 1 == ps->capacity){STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity *= 2;}// 插入元素// top 为栈顶元素// 先 ++ 再插入ps->a[++ps->top] = x;
}void StackPop(ST* ps)
{assert(ps);// 如果栈空,则不能删除assert(!StackEmpty(ps));ps->top--;
}STDatatype StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top];
}bool StackEmpty(ST* ps)
{assert(ps);return ps->top == -1;
}int StackSize(ST* ps)
{assert(ps);return ps->top + 1;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "Stack.h"void TestST1()
{ST st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);StackPush(&st, 5);StackPop(&st);StackPop(&st);printf("%d\n", StackTop(&st));
}int main()
{TestST1();
}
总结
今天学习了栈的知识,初次写数据结构的知识,给我的感觉就是,学三遍不如手敲代码一遍来的实在,所以数据结构的学习我将多画图,多敲代码来学习,希望大家吸取经验和我一起学习数据结构,为后面打比赛刷题打下坚实基础。
我是夏目浅石,希望和你一起学习进步,刷题无数!!!希望各位大佬能一键三连支持一下博主,hhhh~我们下期见喽

如果无聊的话,就来逛逛我的博客栈吧stack-frame.cn
✨原创不易,还希望各位大佬支持一下\textcolor{blue}{原创不易,还希望各位大佬支持一下}原创不易,还希望各位大佬支持一下
👍 点赞,你的认可是我创作的动力!\textcolor{9c81c1}{点赞,你的认可是我创作的动力!}点赞,你的认可是我创作的动力!
⭐️ 收藏,你的青睐是我努力的方向!\textcolor{ed7976}{收藏,你的青睐是我努力的方向!}收藏,你的青睐是我努力的方向!
✏️ 评论,你的意见是我进步的财富!\textcolor{98c091}{评论,你的意见是我进步的财富!}评论,你的意见是我进步的财富!
相关文章:
【数据结构】千字深入浅出讲解栈(附原码 | 超详解)
🚀write in front🚀 📝个人主页:认真写博客的夏目浅石. 🎁欢迎各位→点赞👍 收藏⭐️ 留言📝 📣系列专栏:C语言实现数据结构 💬总结:希望你看完…...
自动驾驶V2X
1 SoC MDM9250 2 设备网络节点 mhi_swip0 rmnet_mhi0 3 网络协议栈log打印控制 include/linux/netdevice.h ethtool -s eth0 msglvl [level] ethtool -s eth0 msglvl 0x6001 4 URLs MHI initial design review https://lore.kernel.org/lkml/001601d52148$bd852840$388f78c0$c…...
零基础自学网络安全/渗透测试有哪些常见误区?
一、网络安全学习的误区 1.不要试图以编程为基础去学习网络安全 不要以编程为基础再开始学习网络安全,一般来说,学习编程不但学习周期长,且过渡到网络安全用到编程的用到的编程的关键点不多。一般人如果想要把编程学好再开始学习网络安全往…...
ConvMixer:Patches Are All You Need
Patches Are All You Need 发表时间:[Submitted on 24 Jan 2022]; 发表期刊/会议:Computer Vision and Pattern Recognition; 论文地址:https://arxiv.org/abs/2201.09792; 代码地址:https:…...
day10—编程题
文章目录1.第一题1.1题目1.2思路1.3解题2.第二题2.1题目2.2涉及的相关知识2.3思路2.4解题1.第一题 1.1题目 描述: 给定一个二维数组board,代表棋盘,其中元素为1的代表是当前玩家的棋子,0表示没有棋子,-1代表是对方玩…...
如何测量锂电池的电量
锂电池在放电时我们有时需要知道电池的实时电量,如电池电量低了我们就需要及时给锂电池充电,避免电池过度放电。我手里的这个就是个单节锂电池电量显示模块,只需要将这个模块接到锂电池的正负极即可显示电量。这个模块的电量分为四档…...
菜鸟刷题Day6
⭐作者:别动我的饭 ⭐专栏:菜鸟刷题 ⭐标语:悟已往之不谏,知来者之可追 一.链表内指定区间反转:链表内指定区间反转_牛客题霸_牛客网 (nowcoder.com) 描述 将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转…...
DecimalFormat格式化显示数字
DecimalFormat 是 NumberFormat 的一个具体子类,用于格式化十进制数字,可以实现以最快的速度将数字格式化为你需要的样子。 DecimalFormat 类主要靠 # 和 0 两种占位符号来指定数字长度。0 表示如果位数不足则以 0 填充, # 表示只要有可能就…...
cpu中缓存简介
一级缓存是什么: 一级缓存都内置在CPU内部并与CPU同速运行,可以有效的提高CPU的运行效率。一级缓存越大,CPU的运行效率越高,但受到CPU内部结构的限制,一级缓存的容量都很小。 CPU缓存(Cache Memory…...
【数据结构】二叉树的遍历以及基本操作
目录 1.树形结构 1.概念 2.二叉树 2.1概念 2.2 两种特殊的二叉树 2.3二叉树的存储 2.4二叉树的基本操作 1.手动快速创建一棵简单的二叉树 2.二叉树的遍历 (递归) 3.二叉树的层序遍历 4.获取树中节点的个数 5.获取叶子节点的个数 6.获取第K层节点的个数 7.获取二叉…...
若依框架 --- ruoyi 表格的设置
表格 字典值转换 (1) 方式1:使用字典枚举的方式 var isDownload [[${dict.getType(YES_OR_NO)}]];{field : isDownload,title : 是否允许下载,formatter: function(value, row, index) {return $.table.selectDictLabel(isDownload, value);} }, (2) 方式2&…...
“两会”网络安全相关建议提案回顾
作为新一年的政治、经济、社会等发展的“风向标”,今年“两会”在3月13日顺利闭幕。在今年“两会”期间,多位人大代表也纷纷围绕网络安全、数据安全的未来发展做了提案和建议。 01 “两会”网络安全相关建议和提案回顾 建议统筹智能网联汽车数据收集与共…...
一篇文章带你真正了解接口测试(附视频教程+面试真题)
目录 一、什么是接口测试? 二、为什么要做接口测试? 三、如何开展接口测试? 四、接口测试常见面试题 一、什么是接口测试? 所谓接口,是指同一个系统中模块与模块间的数据传递接口、前后端交互、跨系统跨平台跨数据…...
C/C++每日一练(20230325)
目录 1. 搜索插入位置 🌟 2. 结合两个字符串 🌟 3. 同构字符串 🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C每日一练 专栏 Java每日一练 专栏 1. 搜索插入位置 给定一个排序数…...
Linux操作系统ARM指令集与汇编语言程序设计
一、实验目的1.了解并掌握ARM汇编指令集2.应用ARM指令集编写一个程序操控开发板上的LED灯二、实验要求应用ARM汇编指令集编写程序,实现正常状态下开发板上的LED灯不亮,按下一个按键之后开发板上的LED灯进入流水灯模式。三、实验原理四个LED灯的电路如下图…...
计网之HTTP协议和Fiddler的使用
文章目录一. HTTP概述和fidder的使用1. 什么是HTTP2. 抓包工具fidder的使用2.1 注意事项2.2 fidder的使用二. HTTP协议格式1. HTTP请求格式1.1 基本格式1.2 认识URL1.3 方法2. 请求报头关键字段3. HTTP响应格式3.1 基本格式3.2 状态码一. HTTP概述和fidder的使用 1. 什么是HTT…...
sql性能优化:MS-SQL(SQL Server)跟踪日志信息结果列字段说明,MSSQL的列字段说明(column)
sql性能优化:MS-SQL(SQL Server)跟踪日志信息结果列字段说明,MSSQL的列字段说明(column) 参考: SQL:BatchCompleted 事件类 | Microsoft Learn SQL 跟踪 | Microsoft Learn sp_trace_setevent (…...
DNS主从复制
#前提准备:关闭SElinux 关闭防火墙 时间同步 #环境说明:Centos7 #ip地址:dns-master:10.0.0.100 dns-slave:10.0.0.103 web:10.0.0.101 主DNS服务配置 1.安装软件包: yum install bind -…...
常见的js加密/js解密方法
常见的js加密/js解密方法 当今互联网世界中,数据安全是至关重要的。为了保护用户的隐私和保密信息,开发人员必须采取适当的安全措施。在前端开发中,加密和解密技术是一种常见的数据安全措施,其中 JavaScript 是最常用的语言之一。…...
6 python函数
函数 在实现某个功能对应的代码的时候,如果将实现功能对应的函数放到函数中,那么下一次再需要这个功能的时候,就可以不用再写这个功能对应的代码,直接调用这个功能对应的函数。 1.什么是函数 函数就是实现某一特点功能的代码的封装…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...
Rust 开发环境搭建
环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行: rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu 2、Hello World fn main() { println…...
华为OD机试-最短木板长度-二分法(A卷,100分)
此题是一个最大化最小值的典型例题, 因为搜索范围是有界的,上界最大木板长度补充的全部木料长度,下界最小木板长度; 即left0,right10^6; 我们可以设置一个候选值x(mid),将木板的长度全部都补充到x,如果成功…...
