【数据结构】栈和队列-->理解和实现(赋源码)
Toc
欢迎光临我的Blog,喜欢就点歌关注吧♥
前面介绍了顺序表、单链表、双向循环链表,基本上已经结束了链表的讲解,今天谈一下栈、队列。可以简单的说是前面学习的一特殊化实现,但是总体是相似的。
前言
栈是一种特殊的线性表,它只允许在一端进行插入和删除操作。这一端被称为栈顶,另一端被称为栈底。栈的特点是后进先出(LIFO),即最后进入的元素最先被移除。
队列是另一种特殊的线性表,它允许在一端进行插入操作,在另一端进行删除操作。插入操作的一端称为队尾,删除操作的一端称为队头。队列的特点是先进先出(FIFO),即最先进入的元素最先被移除。
栈和队列有各自的特点,严格讲用顺序表还是链表的实现都可以。但我们根据结构特点选择一个更加适合的结构进行是实现。
一、栈和队列的理解
对于栈的理解:

栈如同这个图一样,要是想拿出数据,必须从上面一个一个往下面拿。这也正是 LIFO 的体现。
对于队列的理解:

队列如同这个图一样,要是想拿出数据,必须前面一个一个往向后面拿。这也正是 FIFO 的体现。
二、栈的实现(顺组表)
2.1 栈的功能
//初始化
void STInit(ST* ps);
//压栈
void STpush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//大小
int STSize(ST* ps);
//判空
bool STEmpty(ST* ps);
//出栈
STDataType STTop(ST* ps);
//检查容量
void CheckCapacity(ST* ps);
//销毁
void STDestroy(ST* ps);
2.2 栈结构体的定义及其初始化
结构体的定义
typedef int STDataType;typedef struct stack
{STDataType* a;int top;int capacity;
}ST;
初始化(开辟空间)
void STInit(ST* ps)
{assert(ps);ps->a = (ST*)malloc(sizeof(ST)*4);if (ps->a == NULL){perror("malloc fail");return;}ps->capacity = 4;ps->top = 0;
}
2.3 压栈(存储数据)
//压栈
void STpush(ST* ps,STDataType x)
{assert(ps);ps->a[ps->top] = x;ps->top++;
}
2,4 删除数据
在这里面删除数据是配合,栈顶出栈。每次拿出一个数据,就要减少一个数据。
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}
2.5 计算栈内元个数
//大小
int STSize(ST* ps)
{assert(ps);return ps->top;
}
2.6 判断栈内是否为空
这里运用 bool 类型直接返回,比较方便。
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
2.7 出栈
//出栈
STDataType STTop(ST* ps)
{assert(ps);return ps->a[ps->top-1];
}
2.8 增加容量
//检查容量
void CheckCapacity(ST*ps)
{assert(ps);if (ps->top == ps->capacity){ST* tmp = (ST*)realloc(ps->a, sizeof(ST) * (ps->capacity) * 2);if (tmp == NULL){perror("malloc fail");return;}ps->capacity *= 2;ps->a = tmp;}
}
2.9 销毁栈
//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
三、队列的实现(单链表)
3.1 队列的功能
//初始化
void QueueInit(Queue* ps);
//销毁
void QueueDestroy(Queue* ps);
//入队
void QueuePush(Queue* ps, QDataType x);
//删除
void QueuePop(Queue* ps);
//大小
int QueueSize(Queue* ps);
//判空队
bool QueueEmpty(Queue* ps);
//出队头
QDataType QueueTop(Queue* ps);
//出队尾
QDataType QueueBack(Queue* ps);
3.2 队列的结构体定义以及初始化
结构体定义
定义两个结构体,第一个为存放数据,第二个结构体为两个指针,分别指向头和尾
typedef int QDataType;typedef struct QNode
{struct QNode* next;QDataType data;}QNode;typedef struct Queue
{QNode*head;QNode*tail;int szie;
}Queue;
初始化
//初始化
void QueueInit(Queue* ps)
{assert(ps);ps->head = ps->tail = NULL;ps->szie = 0;}
3.3 队列销毁
//销毁
void QueueDestroy(Queue* ps)
{assert(ps);QNode* cur = ps->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}ps->head = ps->tail = NULL;ps->szie = 0;
}
3.4 入队(插入数据)
//入队
void QueuePush(Queue* ps,QDataType x)
{assert(ps);QNode* newcode = (QNode*)malloc(sizeof(QNode));if (newcode == NULL){perror("malloc fail");return ;}newcode->next = NULL;newcode->data = x;if (ps->head == NULL){ps->head = ps->tail = newcode;}else{ps->tail->next = newcode;ps->tail = newcode;}ps->szie++;}
3.5 删除数据(头删)
//删除
void QueuePop(Queue* ps)
{assert(ps);assert(ps->head != NULL);assert(!QueueEmpty(ps));if (ps->head->next == NULL){free(ps->head);ps->head = ps->tail = NULL;}else{QNode* next = ps->head->next;free(ps->head);ps->head = next;}ps->szie--;
}
3.6 计算队列元素个数
//大小
int QueueSize(Queue* ps)
{assert(ps);return ps->szie;
}
3.7 判断是否队列为空
//判空队
bool QueueEmpty(Queue* ps)
{assert(ps);return ps->szie == 0;
}
3.8 出队(头)
//出队头
QDataType QueueTop(Queue* ps)
{assert(ps);assert(!QueueEmpty(ps));return ps->head->data;
}
3.9 出队(尾)
//出队尾
QDataType QueueBack(Queue* ps)
{assert(ps);return ps->tail->data;
}
四、栈和队列的源码
栈
Stack.h
#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int STDataType;typedef struct stack
{STDataType* a;int top;int capacity;
}ST;//初始化
void STInit(ST* ps);
//压栈
void STpush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//大小
int STSize(ST* ps);
//判空
bool STEmpty(ST* ps);
//出栈
STDataType STTop(ST* ps);
//检查容量
void CheckCapacity(ST* ps);
//销毁
void STDestroy(ST* ps);
Stack.c
#define _CRT_SECURE_NO_WARNINGS#include "stack.h"//初始化
void STInit(ST* ps)
{assert(ps);ps->a = (ST*)malloc(sizeof(ST)*4);if (ps->a == NULL){perror("malloc fail");return;}ps->capacity = 4;ps->top = 0;
}
//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}//检查容量
void CheckCapacity(ST*ps)
{assert(ps);if (ps->top == ps->capacity){ST* tmp = (ST*)realloc(ps->a, sizeof(ST) * (ps->capacity) * 2);if (tmp == NULL){perror("malloc fail");return;}ps->capacity *= 2;ps->a = tmp;}
}//压栈
void STpush(ST* ps,STDataType x)
{assert(ps);ps->a[ps->top] = x;ps->top++;
}//删除
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}//判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出栈
STDataType STTop(ST* ps)
{assert(ps);return ps->a[ps->top-1];
}//大小
int STSize(ST* ps)
{assert(ps);return ps->top;
}
test.c
#define _CRT_SECURE_NO_WARNINGS#include "stack.h"void teststack()
{ST st;STInit(&st);STpush(&st, 1);STpush(&st, 2);STpush(&st, 3);STpush(&st, 4);STpush(&st, 5);printf("%d", STSize(&st));printf("\n");while (!STEmpty(&st)){printf("%d ", STTop(&st));STPop(&st);}printf("\n");printf("%d", STSize(&st));STDestroy(&st);}int main()
{teststack();return 0;
}
队列
Queue.h
#pragma once#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>typedef int QDataType;typedef struct QNode
{struct QNode* next;QDataType data;}QNode;typedef struct Queue
{QNode*head;QNode*tail;int szie;
}Queue;//单链表的实现,FIFO//初始化
void QueueInit(Queue* ps);
//销毁
void QueueDestroy(Queue* ps);
//入队
void QueuePush(Queue* ps, QDataType x);
//删除
void QueuePop(Queue* ps);
//大小
int QueueSize(Queue* ps);
//判空队
bool QueueEmpty(Queue* ps);
//出队头
QDataType QueueTop(Queue* ps);
//出队尾
QDataType QueueBack(Queue* ps);
Queue.c
#define _CRT_SECURE_NO_WARNINGS#include "queue.h"//初始化
void QueueInit(Queue* ps)
{assert(ps);ps->head = ps->tail = NULL;ps->szie = 0;}//销毁
void QueueDestroy(Queue* ps)
{assert(ps);QNode* cur = ps->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}ps->head = ps->tail = NULL;ps->szie = 0;
}//入队
void QueuePush(Queue* ps,QDataType x)
{assert(ps);QNode* newcode = (QNode*)malloc(sizeof(QNode));if (newcode == NULL){perror("malloc fail");return ;}newcode->next = NULL;newcode->data = x;if (ps->head == NULL){ps->head = ps->tail = newcode;}else{ps->tail->next = newcode;ps->tail = newcode;}ps->szie++;}//删除
void QueuePop(Queue* ps)
{assert(ps);assert(ps->head != NULL);assert(!QueueEmpty(ps));if (ps->head->next == NULL){free(ps->head);ps->head = ps->tail = NULL;}else{QNode* next = ps->head->next;free(ps->head);ps->head = next;}ps->szie--;
}//大小
int QueueSize(Queue* ps)
{assert(ps);return ps->szie;
}//判空队
bool QueueEmpty(Queue* ps)
{assert(ps);return ps->szie == 0;
}//出队头
QDataType QueueTop(Queue* ps)
{assert(ps);assert(!QueueEmpty(ps));return ps->head->data;
}//出队尾
QDataType QueueBack(Queue* ps)
{assert(ps);return ps->tail->data;
}
test.c
#define _CRT_SECURE_NO_WARNINGS#include "queue.h"void testQueue()
{Queue s;QueueInit(&s);QueuePush(&s, 1);QueuePush(&s, 2);QueuePush(&s, 3);QueuePush(&s, 4);//printf("%d ", QueueTop(&s));//QueuePop(&s);//printf("%d ", QueueTop(&s));//QueuePop(&s); //printf("%d ", QueueTop(&s));//QueuePop(&s); //printf("%d ", QueueTop(&s));//QueuePop(&s);//printf("\n");while (!(QueueEmpty(&s))){printf("%d ", QueueTop(&s));QueuePop(&s);}QueueDestroy(&s);}int main()
{testQueue();return 0;
}相关文章:
【数据结构】栈和队列-->理解和实现(赋源码)
Toc 欢迎光临我的Blog,喜欢就点歌关注吧♥ 前面介绍了顺序表、单链表、双向循环链表,基本上已经结束了链表的讲解,今天谈一下栈、队列。可以简单的说是前面学习的一特殊化实现,但是总体是相似的。 前言 栈是一种特殊的线性表&…...
一篇教会你CSS定位
前言:在网页布局的时候,我们需要将想要的元素放到指定的位置上,这个时候我们就可以使用CSS中的定位操作。 先让我们看一下本篇文章的大致内容: 目录 什么是定位 1.相对定位 2.绝对定位 3. 固定定位 4. 粘性定位 5. 定位层级…...
Hive的常规操作
Hive常规操作 hive常用交互命令 -e执行sql语句 [rootmaster ~]# hive -e "show databases";-f执行sql脚本 [rootmaster ~]# hive -f /usr/local/demo.sql查看hive中输入的所有命令 [rootmaster ~]# cat ~/.hivehistory操作库 创建库 语法: create…...
redis做为缓存,mysql的数据如何与redis进行同步呢?
让我们一步步来实现如何让MySQL数据库的数据和Redis缓存保持同步。想象一下,MySQL是一个大仓库,存放着所有重要的货物(数据),而Redis则像是一个快速取货窗口,让你能更快拿到常用的东西。为了让两者保持一致…...
【Map】集合总结
一、Map 之前学习的Collection集合体系是单列集合,即一次存取一个元素 Map是双列集合,一次存取一对元素,这一对儿称为键值对,key-value,且key是映射到value 所谓键映射到值,是指只能通过键找到值,无法通过值找键 Map中键不能重复!值允许重复 Map中一个键,只能对应一个值 Ma…...
SpringBoot实现发送邮件功能
目录 一、开启邮件服务 二、导入pom依赖 三、配置yml文件 四、发送邮件 4.1、发送文字邮件 4.2、发送html邮件 4.3、发送附件邮件 4.4、发送图片邮件 一、开启邮件服务 这里拿QQ邮箱举例。 翻到下面进行开启,之后获取授权码。 二、导入pom依赖 <dependency><…...
外观数列 ---- 模拟
题目链接 题目: 分析: 题目的意思如下:所以我们需要引用双指针来找到连续的字符有几个, 并添加到答案中, 接着将此字符添加到答案中, 让left right , 继续向后遍历整个字符串, 重复上面的操作将答案重新赋给字符串, 继续重复上述操作, 应该重复n - 1 次, 因为n为1的时候, 直…...
上心师傅的思路分享(二)
Druid monitor 与Springboot常见报错界面渗透小技巧 目录 前言 1.Druid monitor介绍 2.Druid未授权(1rank) 3.druid弱口令 4.Druid进一步利用 4.1 URL监控 4.2 Session监控 利用思路 EditThisCookie(小饼干插件) 5.SpringBoot Actuator未授权访问漏洞 5.1 简介 5…...
116页 | 2024年中国金融行业网络安全研究报告(免费下载)
以上是资料简介和目录,如需下载,请前往星球获取!!!...
基于fabric封装一个简单的图片编辑器(vue 篇)
介绍 前言vue demo版本react 版本 前言 对 fabric.js 进行二次封装,实现图片编辑器的核心功能。核心代码 不依赖 ui响应式框架vue ,react 都适用。 只写了核心编辑相关代码便于大家后续白嫖二次开发 核心代码我就没有打包发布 会 和 业务代码一起放到项目中。 vu…...
Linux中 .PHONY 和 all 在 Makefile 中的作用
1 .PHONY 和 all .PHONY 是 GNU make 工具中的一个特殊指令,用于指示某个目标是一个伪目标。伪目标并不对应于实际的文件,而是用来执行一系列命令的标识符。使用 .PHONY 的好处包括避免与现有文件同名造成的冲突,以及提高 make 的执行效率&am…...
Flutter 中的 FlexibleSpaceBar 小部件:全面指南
Flutter 中的 FlexibleSpaceBar 小部件:全面指南 Flutter 是一个由 Google 开发的跨平台 UI 框架,它提供了丰富的组件来帮助开发者构建高性能、美观的移动、Web 和桌面应用。在 Flutter 的组件库中,FlexibleSpaceBar 是一个与 SliverAppBar …...
每天一个数据分析题(三百五十四)-分析报表
分析报表的主要作用是通过可视化图表的形式将各种分析结果完整、准确地呈现给阅读者,帮助阅读者读懂数据,从而进一步发现数据背后隐藏的业务问题。下列说法正确的是? A. 静态报表的主要载体是电子表格工具 B. BI报表的数据源获取方式是应用…...
卫星通信频段有哪些
卫星通信使用到的频段涵盖L, S, C, Ku, Ka等,而最常用的频段是C(4~8GHz)和Ku(12~18GHz)频段,而Ka(27-40GHz)频段是后起之秀。目前地球赤道上空有限的地球同步卫星轨位几乎已被各国占满,C和Ku频段内的频率资源被大量使用,而Ka频段的…...
RobotMaster编程语言:深度探索与实践挑战
RobotMaster编程语言:深度探索与实践挑战 RobotMaster编程语言,作为机器人编程领域的一颗璀璨明珠,其独特性与复杂性吸引了无数探索者的目光。本文将从四个方面、五个方面、六个方面和七个方面深入剖析这一编程语言的奥秘,同时揭…...
Ascend训练软件栈了解
一.分布式大模型训练的完整流程及注意事项 1. 迁移分析 模型选取与约束说明 : 确保模型能在GPU或CPU上运行并获取性能基线,了解不支持场景,如DP模式、APEX库、bmtrain框架等。支持度分析 : 使用msFmkTransplt工具分析模型算子、…...
官网万词霸屏推广 轻松实现百度万词霸屏源码系统 带完整的安装代码包以及搭建教程
系统概述 官网万词霸屏推广源码系统是一款基于先进技术研发的综合性 SEO 工具。它的设计理念是通过智能化的算法和策略,帮助用户快速提升网站在百度等搜索引擎中的排名,实现大量关键词的霸屏效果。该系统整合了多种优化技术,包括关键词研究、…...
Linux 36.3 + JetPack v6.0@jetson-inference之图像分类
Linux 36.3 JetPack v6.0jetson-inference之图像分类 1. 源由2. imagenet2.1 命令选项2.2 下载模型2.3 操作示例2.3.1 单张照片2.3.2 视频 3. 代码3.1 Python3.2 C 4. 参考资料5. 补充5.1 第一次运行模型本地适应初始化5.2 samba软连接 1. 源由 从应用角度来说,图…...
重庆公司记账代理,打造专业财务管理解决方案的领先企业
重庆公司记账代理,作为专业的财务管理服务提供商,我们的目标是为公司的经营管理和决策提供科学、准确的财务数据支持,我们通过长期的专业经验和对市场的深入理解,为您提供一站式的记账服务和财务咨询。 专业团队 我们拥有一支由经…...
transformers 阅读:Llama 模型
正文 学习一下 transformers 库中,Llama 模型的代码,学习过程中写下这篇笔记,一来加深印象,二来可以多次回顾。 笔者小白,里面错误之处请不吝指出。 层归一化 LlamaRMSNorm transformers 中对于 LlamaRMSNorm 类的…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...
从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...
WEB3全栈开发——面试专业技能点P7前端与链上集成
一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染(SSR)与静态网站生成(SSG) 框架,由 Vercel 开发。它简化了构建生产级 React 应用的过程,并内置了很多特性: ✅ 文件系…...
CppCon 2015 学习:Time Programming Fundamentals
Civil Time 公历时间 特点: 共 6 个字段: Year(年)Month(月)Day(日)Hour(小时)Minute(分钟)Second(秒) 表示…...
