数据结构和算法之《栈》详解_csdn 栈-程序员宅基地
标题：栈的思路及代码实现
作者：@Ggggggtm
寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景
文章目录：
一、栈的概念及结构
1、1 栈的概念
栈是一种特殊的线性表，其只允许在固定的一段进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的元素遵循后进先出LIFQ（Last In First Out）的原则。
压栈：栈的元素插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的元素删除操作叫做出栈，出数据也在栈顶。
1、2 栈的结构
二、栈的思路及代码实现详解
2、1 栈的实现思路详解
栈的操作无非解释插入和删除，我们可以想到用顺序表或者链表来实现。在栈中的插入和删除操作我们可以看作尾插和尾删。相对与链表来说，顺序表的尾插尾删效率还是高的。 因为单链表的尾删还要记录前一个元素，相对而言效率就低了。如果是双向循环链表，则效率会更高。当然，在栈中的插入和删除操作我们还可以看作头插和头删。这时候链表的效率就比顺序表的效率高了。因为顺序表的头插或者头删都需要移动整个顺序表的元素。
在这里我就给大家讲解栈的插入和删除操作以尾插和尾删的顺序表形式实现。
完整的栈实现都需要有哪些模块呢？我给大家一一列举一下：
- 定义一个结构体，该结构体包含一个可以存放数据的数组指针及一个记录栈顶的变量和一个记录数组容量的变量；
- 初始化结构体；
- 释放动态开辟数组；
- 判断栈是否为空；
- 插入数据；
- 删除数据；
- 栈顶元素；
- 栈的大小。
接下来我给大家一一讲解实现。
2、2 栈的代码实现
2、2、1 定义结构体
上面我们提到，定义结构体时该结构体包含一个可以存放数据的数组指针及一个记录栈顶的变量和一个记录数组容量的变量，那么代码的实现就简单了。
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;2、2、2 初始化结构体
初始化结构体时，我们只需要把数组置空，栈顶和容量置零即可。
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}2、2、3 释放动态开辟数组
当我们定义一个栈并且初始化后，当然会进行一系列的插入和删除操作。一定要记得释放栈，避免内存泄漏。
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}2、2、4 判断栈是否为空
当我们删除元素，或者找栈顶元素使都需要判断栈是否为空。所以我们这里先实现一下这个模块。
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}2、2、5 插入数据
插入数据时，我们首先要判断数组是否满了。如果满了的话，我们需要扩容。当然，第一次扩容时，我们应该先给其赋一个值，因为第一次扩容时，capacity为0，乘以任何数为0，所以我们要考虑到这种情况。插入数据也就是顺序表的尾插，实现简单。我们来看一下代码。
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->capacity == ps->top)
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newCapacity);
if (tmp == NULL)
{
printf("realloc failed\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newCapacity;
}
ps->a[ps->top] = x;
ps->top++;
}2、2、6 删除数据
删除元素，首先要判断栈不能为空。顺序表的删除十分简单，我们看代码实现。
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}2、2、7 栈顶元素
找栈顶元素，我们因为这里用了top-1为栈顶元素，所以要判断栈不能为空。一但为空，就会越界访问。
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}2、2、8 栈的大小
栈的大小即为top-1，非常简单，直接看代码实现。
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}三、取出栈中的元素
我们直到，栈中的元素遵循后进先出LIFQ（Last In First Out）的原则。所以我们打印栈顶的元素后，就进行对栈顶删除，直到栈为空停止。我们看一下代码的实现。
ST s;
StackInit(&s);
StackPush(&s, 1);
StackPush(&s, 2);
StackPush(&s, 3);
StackPush(&s, 4);
printf("%d ", StackTop(&s));
StackPop(&s);
printf("%d ", StackTop(&s));
StackPop(&s);
StackPush(&s, 5);
StackPush(&s, 6);
//StackPop(&s);
//取出栈中的数据
while (!StackEmpty(&s))
{
printf("%d ", StackTop(&s));
StackPop(&s);
}
StackDestroy(&s);
while (!StackEmpty(&s))
{
printf("%d ", StackTop(&s));
StackPop(&s);
}上面的代码是我们先压栈四个元素，然后打印并且出栈两个元素，再次压栈两个元素，最后一次取出。那么结构就是：4 3 6 5 2 1。
综上就是我们整个栈的实现了，希望本篇文章会对您有所帮助，感谢阅读。
后续会一直更新数据结构与算法的内容的哦ovo~
智能推荐
Eclipse中配置WebMagic(已配置好Maven)_使用eclipse搭建webmagic工程-程序员宅基地
文章浏览阅读364次。1.WebMagicWebMagic是一个简单灵活的Java爬虫框架。基于WebMagic，你可以快速开发出一个高效、易维护的爬虫。2.在Eclipse中配置WebMagic1.首先需要下载WebMagic的压缩包官网地址为：WebMagic官网最新版本为：WebMagic-0.7.3，找到对应版本，打开下载界面，注意，下载要选择Source code(zip)版本，随便下载到哪里都可以；2.下载好的压缩包需要解压，此时解压到的位置即为后续新建的Eclipse的project位置，比如我的Ecli_使用eclipse搭建webmagic工程
linux启动mysql_linux如何启动mysql服务_linux启动mysql服务命令是什么－系统城-程序员宅基地
文章浏览阅读1.9k次。mysql数据库是一种开放源代码的关系型数据库管理系统，有很多朋友都在使用。一些在linux系统上安装了mysql数据库的朋友，却不知道该如何对mysql数据库进行配置。那么linux该如何启动mysql服务呢？接下来小编就给大家带来linux启动mysql服务的命令教程。具体步骤如下：1、首先，我们需要修改mysql的配置文件，一般文件存放在/etc下面，文件名为my.cnf。2、对于mysql..._linux中 mysql 启动服务命令
php实现在线oj,详解OJ(Online Judge)中PHP代码的提交方法及要点-程序员宅基地
文章浏览阅读537次。详解OJ(Online Judge)中PHP代码的提交方法及要点Introduction of How to submit PHP code to Online Judge SystemsIntroduction of How to commit submission in PHP to Online Judge Systems在目前常用的在线oj中，codeforces、spoj、uva、zoj..._while(fscanf(stdin, "%d %d", $a, $b) == 2)
java快捷键调字体_设置MyEclipse编码、补全快捷键、字体大小-程序员宅基地
文章浏览阅读534次。一、设置MyEclipse编码(1)修改工作空间的编码方式：Window-->Preferences-->General-->Workspace-->Text file encoding(2)修改一类文件的编码方式：Window-->Preferences-->General-->content Types-->修改default Encoding(..._java修改快捷缩写内容
解析蓝牙原理_蓝牙原理图详解-程序员宅基地
文章浏览阅读1.4w次，点赞19次，收藏76次。1.前言市面上关于Android的技术书籍很多，几乎每本书也都会涉及到蓝牙开发，但均是上层应用级别的，而且篇幅也普遍短小。对于手机行业的开发者，要进行蓝牙模块的维护，就必须从Android系统底层，至少框架层开始，了解蓝牙的结构和代码实现原理。这方面的文档、网上的各个论坛的相关资料却少之又少。分析原因，大概因为虽然蓝牙协议是完整的，但是并没有具体的实现。蓝牙芯片公司只负责提供最底层的API_蓝牙原理图详解
从未在一起更让人遗憾_“从未在一起和最终没有在一起哪个更遗憾”-程序员宅基地
文章浏览阅读7.7k次。图/源于网络文/曲尚菇凉1.今天早上出门去逛街，在那家冰雪融城店里等待冰淇淋的时候，听到旁边两个女生在讨论很久之前的一期《奇葩说》。那期节目主持人给的辩论题是“从未在一起和最终没有在一起哪个更遗憾”，旁边其中一个女生说，她记得当时印象最深的是有个女孩子说了这样一句话。她说:“如果我喜欢一个人呢，我就从第一眼到最后一眼，把这个人爱够，把我的感觉用光，我只希望那些年让我成长的人是他，之后的那些年他喝过..._从未在一起更遗憾
随便推点
Spring Cloud Alibaba 介绍_sprngcloud alba-程序员宅基地
文章浏览阅读175次。Spring Cloud Alibaba 介绍Sping体系Spring 以 Bean（对象） 为中心，提供 IOC、AOP 等功能。Spring Boot 以 Application（应用） 为中心，提供自动配置、监控等功能。Spring Cloud 以 Service（服务） 为中心，提供服务的注册与发现、服务的调用与负载均衡等功能。Sping Cloud介绍官方介绍 Tools for building common patterns in distributed systems_sprngcloud alba
测试 数据类型的一些测试点和经验_基础字段的测试点-程序员宅基地
文章浏览阅读3.2k次，点赞4次，收藏21次。我这里是根据之前在测试数据类项目过程中的一些总结经验和掉过个坑，记录一下，可以给其他人做个参考，没什么高深的东西，但是如果不注意这些细节点，后期也许会陷入无尽的扯皮当中。1 需求实现的准确度根据产品需求文档描述发现不明确不详细的或者存在歧义的地方一定要确认，例如数据表中的一些字段，与开发和产品确认一遍，如有第三方相关的，要和第三方确认，数据类项目需要的是细心，哪怕数据库中的一个字段如果没有提前对清楚，后期再重新补充，会投入更大的精力。2 数据的合理性根据业务场景/常识推理，提..._基础字段的测试点
一文看懂：行业分析怎么做？_码工小熊-程序员宅基地
文章浏览阅读491次。大家好，我是爱学习的小xiong熊妹。在工作和面试中，很多小伙伴会遇到“对XX行业进行分析”的要求。一听“行业分析”四个字，好多人会觉得特别高大上，不知道该怎么做。今天给大家一个懒人攻略，小伙伴们可以快速上手哦。一、什么是行业？在做数据分析的时候，“行业”两个字，一般指的是：围绕一个商品，从生产到销售相关的全部企业。以化妆品为例，站在消费者角度，就是简简单单的从商店里买了一支唇膏回去。可站在行业角度，从生产到销售，有相当多的企业在参与工作（如下图）在行业中，每个企业常常扮._码工小熊
LLaMA 简介：一个基础的、650 亿参数的大型语言模型_llma-程序员宅基地
文章浏览阅读1.6w次，点赞2次，收藏2次。还需要做更多的研究来解决大型语言模型中的偏见、有毒评论和幻觉的风险。我们在数万亿个令牌上训练我们的模型，并表明可以仅使用公开可用的数据集来训练最先进的模型，而无需诉诸专有和不可访问的数据集。在大型语言模型空间中训练像 LLaMA 这样的小型基础模型是可取的，因为它需要更少的计算能力和资源来测试新方法、验证他人的工作和探索新的用例。作为 Meta 对开放科学承诺的一部分，今天我们公开发布 LLaMA（大型语言模型元 AI），这是一种最先进的基础大型语言模型，旨在帮助研究人员推进他们在 AI 子领域的工作。_llma
强化学习在制造业领域的应用：智能制造的未来-程序员宅基地
文章浏览阅读223次，点赞3次，收藏5次。1.背景介绍制造业是国家经济发展的重要引擎，其产能和质量对于国家经济的稳定和发展具有重要意义。随着工业技术的不断发展，制造业的生产方式也不断发生变化。传统的制造业通常依赖于人工操作和手工艺，这种方式的缺点是低效率、低产量和不稳定的质量。随着信息化、智能化和网络化等新技术的出现，制造业开始向智能制造迈出了第一步。智能制造的核心是通过大数据、人工智能、计算机视觉等技术，实现制造过程的智能化、自动化...
ansible--安装与使用_pip安装ansible-程序员宅基地
文章浏览阅读938次。系列文章目录文章目录系列文章目录 前言 一、ansible是什么？ 二、使用步骤 1.引入库 2.读入数据 总结前言菜鸟一只，刚开始使用，仅作以后参考使用。边学习，边记录，介绍一下最基础的使用，可能会有理解不到位的地方，可以共同交流，废话不多说，走起。一、ansible 简介？ansible是自动化运维工具的一种，基于Python开发，可以实现批量系统配置，批量程序部署，批量运行命令，ansible是基于模块工作的，它本身没有批量部署的能力，真正.._pip安装ansible