【深入解析:数据结构栈的魅力与应用】
本章重点
一、栈的概念及结构
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
- 栈顶Top:线性表允许插入和删除的那一端。
- 栈底Bottom:固定的,不允许进行插入和删除的另一端。
- 空栈:不含任何元素的空表。
二、栈的实现方式
由于栈只能在栈顶操作,所以栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。单链表的尾插需要遍历结点,这里使用带头双向循环链表也可,但是空间销毁大。单链表也可以实现,我们就需要让栈顶是头结点,栈底是尾结点,这样入栈就是头插,效率高。
1.顺序堆栈
根据前边的分析可知,顺序堆栈和顺序表的数据成员(元素)是相同的,不同之处是,顺序堆栈的入栈和出栈操作只能对当前栈顶元素进行。
顺序堆栈的存储结构如图3-2所示。其中,a0,a1,a2,表示顺序堆栈要存储的元素序列,stack 表示顺序堆栈存放元素的数组,capacity 表示顺序堆栈数组stack的内存单元容量(表示目前允许存储的元素最大个数),top表示顺序堆栈数组stack的当前栈顶位置。
2.链式堆栈
堆栈有两端,插入元素和删除元素的一端为栈顶,另一端为栈底。对链式堆栈来说,显然,若把靠近头指针的一端定义为栈顶,则插入元素和删除元素时不需要遍历整个链,其时间复杂度为0(1);若把远离头指针的一端定义为栈顶,则每次插入元素和删除元素时都需要遍历整个链,其时间复杂度为0(n)。因此,链式堆栈都设计成把靠近头指针的一端定义为栈顶。链式堆栈的头结点对操作实现的影响不大,因此可有可无。依次向带头结点链式堆栈输入a0,a1,a2,…….an-1后,带头结点链式堆栈的结构示意图如图3-3所示。
三、数组实现栈接口
// 下面是定长的静态栈的结构,实际中一般不实用,所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType a[N];int top; // 栈顶
}Stack;
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top; // 栈顶int capacity; // 容量
}Stack;// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回0,如果不为空返回非零结果
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
1.初始化栈:void StackInit(Stack* ps)
初始化这里我们先不设置容量,后续入栈再申请空间即可,这里需要注意top的值,我们设置的值是0,它是表示非空栈中的栈顶指针始终在栈顶元素的下一个位置上。
// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps->a = NULL;ps->top = 0;//表示栈顶元素的下一个位置ps->capacity = 0;
}
2.入栈:void StackPush(Stack* ps, STDataType data)
满栈:当我们使一个元素入栈的之前,我们往往需要判断一下栈是否为满栈,防止发生上溢的情况。因为我们定义了一个capacity来表示当前已经分配的存储空间,所以我们可以用ps->top == ps->capacity 来判断当前使用的栈空间是否满了。所以当ps->top == ps->capacity时表示已经满了。
满栈我们要首先追加存储空间,然后才能将元素入栈。realloc()函数可以申请空间,如果realloc第一个参数为空,那么realloc的功能就类似于malloc,这也是为什么我们前面初始化没有开辟空间的原因,写在这里能省大量的代码。
// 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps->top == ps->capacity){int newCapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;//如果ps->a == NULL,功能相当与mallocSTDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = data;ps->top++;
}
3.出栈:void StackPop(Stack* ps)
出栈时我们首先要判断栈是否为空栈,由于是顺序栈,我们只需要判断ps->top > 0即可判断当前栈的情况。
// 出栈
void StackPop(Stack* ps)
{assert(ps);//保证不为空assert(ps->top > 0);ps->top--;
}
4.获取栈顶元素:STDataType StackTop(Stack* ps)
取栈顶元素同样需要判断是否为空栈,空栈也不能取出任何数据,所以这里强制断言,一旦为空栈直接程序报错
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);//保证不为空assert(ps->top > 0);return ps->a[ps->top - 1];
}
5.获取栈中有效元素个数:int StackSize(Stack* ps)
由于top是非空栈中的栈顶指针始终在栈顶元素的下一个位置上,所以top就是当前栈中有效元素个数
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}
6.检测栈是否为空,如果为空返回0,如果不为空返回非零结果:int StackEmpty(Stack* ps)
// 检测栈是否为空,如果为空返回0,如果不为空返回非零结果
int StackEmpty(Stack* ps)
{if (ps->top != 0)return ps->top;elsereturn 0;
}
7.销毁栈:void StackDestroy(Stack* ps)
销毁栈只需将申请的空间释放,再把设置的大小和容量设施为0即可。
// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}
四、栈面试题目
括号匹配问题。OJ链接
当开始接触题目时,我们会不禁想到如果计算出左括号的数量,和右括号的数量,如果每种括号左右数量相同,会不会就是有效的括号了呢?
事实上不是的,假如输入是 [ { ] },每种括号的左右数量分别相等,但不是有效的括号。这是因为结果还与括号的位置有关。
仔细分析我们发现,对于有效的括号,它的部分子表达式仍然是有效的括号,比如 { ( )[ ) ] } 是一个有效的括号,( )[ { } ] 是有效的括号,[ ( ) ] 也是有效的括号。并且当我们每次删除一个最小的括号对时,我们会逐渐将括号删除完。比如下面的例子。
这个思考的过程其实就是栈的实现过程。因此我们考虑使用栈,当遇到匹配的最小括号对时,我们将这对括号从栈中删除(即出栈),如果最后栈为空,那么它是有效的括号,反之不是。
bool isValid(char* s)
{Stack st;StackInit(&st);char topVal;while (*s){switch (*s){case'(':case'[':case'{':StackPush(&st, *s);break;case')':case']':case'}'://数量不匹配if (!StackEmpty(&st))//栈为空{StackDestroy(&st);//防止内存泄露return false;}topVal = StackTop(&st);StackPop(&st);//顺序不匹配if (*s == ')' && topVal != '(' || *s == ']' && topVal != '['|| *s == '}' && topVal != '}'){StackDestroy(&st);//防止内存泄露return false;}break; }++s;}//栈不为空,此时只有右括号,false,说明数量不匹配int ret = StackEmpty(&st);StackDestroy(&st);if (ret == 0)return false;elsereturn true;
}
五、概念选择题
1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈,然后再依次出栈,则元素出栈的顺序是( )。
- A 、12345ABCDE
- B 、EDCBA54321
- C 、ABCDE12345
- D 、54321EDCBA
元素出栈的顺序遵循后进先出(Last-In-First-Out,LIFO)原则,因此选择B
2.若进栈序列为 1,2,3,4 ,进栈过程中可以出栈,则下列不可能的一个出栈序列是()
- A 1,4,3,2
- B 2,3,4,1
- C 3,1,4,2
- D 3,4,2,1
A:1入栈后出栈,2,3,4入栈,4出栈,3出栈,2出栈,可能。
B:1,2入栈,2出栈,3入栈,3出栈,4入栈,4出栈,1出栈,可能。
C:1,2,3入栈,3出栈,接下来应该是2出栈或者4入栈,不可能1出栈,不可能。
D:1,2,3入栈,3出栈,4入栈,4出栈,2出栈,1出栈,可能。
本章结束啦!!!
相关文章:

【深入解析:数据结构栈的魅力与应用】
本章重点 栈的概念及结构 栈的实现方式 数组实现栈接口 栈面试题目 概念选择题 一、栈的概念及结构 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。栈中的数…...

安卓机显示屏的硬件结构
显示屏的硬件结构 显示屏的硬件结构主要由背光源、液晶面板和驱动电路构成。可以将液晶面板看成一个三明治的结构,即在两片偏振方向互相垂直的偏光片系统中夹着一层液晶层。自然光源通过起偏器(偏光片之一)后,变成了垂直方向的偏…...

基于swing的超市管理系统java仓库库存进销存jsp源代码mysql
本项目为前几天收费帮学妹做的一个项目,Java EE JSP项目,在工作环境中基本使用不到,但是很多学校把这个当作编程入门的项目来做,故分享出本项目供初学者参考。 一、项目描述 基于swing的超市管理系统 系统有3权限:管…...

常用系统命令
重定向 cat aa.txt > bbb.txt 将输出定向到bbb.txt cat aaa.txt >> bbb.txt 输出并追加查看进程 ps ps -ef 显示所有进程 例⼦:ps -ef | grep mysql |:管道符 kill pid 结束进程, 如 kill 3732;根据进程名结束进程可以先…...

【Spring专题】Spring之Bean生命周期源码解析——阶段四(Bean销毁)(拓展,了解就好)
目录 前言阅读建议 课程内容一、Bean什么时候销毁二、实现自定义的Bean销毁逻辑2.1 实现DisposableBean或者AutoCloseable接口2.2 使用PreDestroy注解2.3 其他方式(手动指定销毁方法名字) 三、注册销毁Bean过程及方法详解3.1 AbstractBeanFactory#requir…...
配置Docker,漏洞复现
目录 配置Docker 漏洞复现 配置Docker Docker的配置在Linux系统中相对简单,以下是详细步骤: 1.安装Docker:打开终端,运行以下命令以安装Docker。 sudo apt update sudo apt install docker.io 2.启动Docker服务:运…...

微信小程序 游戏水平评估系统的设计与实现_pzbe0
近年来,随着互联网的蓬勃发展,游戏公司对信息的管理提出了更高的要求。传统的管理方式已无法满足现代人们的需求。为了迎合时代需求,优化管理效率,各种各样的管理系统应运而生,随着各行业的不断发展,使命召…...
moba登录不进去提示修改问题问题解决方式
问题: 安装moba后,运行时运行不起来,提示输入密码,安装、卸载多个版本都不行 方法: 使用ResetMasterPassword工具进行重置主密码 官网下载地址: MobaXterm Xserver and tabbed SSH client - resetmaster…...

Unsafe upfileupload
文章目录 client checkMIME Typegetimagesize 文件上传功能在web应用系统很常见,比如很多网站注册的时候需要上传头像、上传附件等等。当用户点击上传按钮后,后台会对上传的文件进行判断 比如是否是指定的类型、后缀名、大小等等,然后将其按…...

机器人制作开源方案 | 滑板助力器
我们可以用一块废滑板做些什么呢? 如今,越来越多的人选择电动滑板作为代步工具或娱乐方式,市场上也涌现出越来越多的电动滑板产品。 (图片来源:Backfire Zealot X Belt Drive Electric Skateboard– Backfire Board…...

飞机打方块(二)游戏界面制作
一、背景 1.新建bg节点 二、飞机节点功能实现 1.移动 1.新建plane节点 2.新建脚本GameController.ts,并绑定Canvas GameControll.ts const { ccclass, property } cc._decorator;ccclass export default class NewClass extends cc.Component {property(cc.Node)canvas:…...
自我理解:精度(precision)和召回(recall)
1、精度(precision) 精度是用于评估分类模型的一个重要指标。它反映了模型预测为正例的样本中,实际真正为正例样本的比例。 【注】正例样本指在二分类问题中,被标注为正类的样本。 例如:在垃圾邮件分类任务中,正例样本就是真实的…...
Nginx 使用 HTTPS(准备证书和私钥)
文章目录 Nginx生成自签名证书和配置Nginx HTTPS(准备证书和私钥)准备证书和私钥 Nginx生成自签名证书和配置Nginx HTTPS(准备证书和私钥) 准备证书和私钥 生成私钥 openssl genrsa -des3 -out server.key 2048这会生成一个加密…...

Java:集合框架:Set集合、LinkedSet集合、TreeSet集合、哈希值、HashSet的底层原理
Set集合 创建一个Set集合对象,因为Set是一个接口不能直接new一个对象,所以要用一个实现类来接 HashSet来接 无序性只有一次,只要第一次运行出来后,之后再运行的顺序还是第一次的顺序。 用LinkedSet来接 有序 不重复 无索引 用Tree…...
自定义Taro的navBar的宽度和高度
本方法是计算自定义navbar的宽度和高度,输出的参数有 navBarHeight, menuBottom,menuHeight, menuRectWidth,windowWidth, windowHeight,具体代码如下: export function getCustomNavBarRect():| {navBarHeight: number;menuBottom: number;menuHeight:…...
用Python编程实现百度自然语言处理接口的对接,助力你开发智能化处理程序
用Python编程实现百度自然语言处理接口的对接,助力你开发智能化处理程序 随着人工智能的不断进步,自然语言处理(Natural Language Processing,NLP)成为了解决文本处理问题的重要工具。百度自然语言处理接口提供了一系…...

系统架构设计专业技能 · 系统工程与系统性能
系列文章目录 系统架构设计专业技能 网络技术(三) 系统架构设计专业技能 系统安全分析与设计(四)【系统架构设计师】 系统架构设计高级技能 软件架构设计(一)【系统架构设计师】 系统架构设计高级技能 …...

初识网络原理(笔记)
目录 编辑局域网 网络通信基础 IP 地址 端口号 协议 协议分层 TCP / IP 五层网络模型 网络数据传输的基本流程 发送方的情况: 接收方的情况 局域网 搭建网络的时候,需要用到 交换机 和 路由器 路由器上,有 lan 口 和 wan 口 虽…...

嵌入式C语言基本操作方法之经典
C语言一经出现就以其功能丰富、表达能力强、灵活方便、应用面广等特点迅速在全世界普及和推广。 C语言不但执行效率高而且可移植性好,可以用来开发应用软件、驱动、操作系统等。 C语言也是其它众多高级语言的鼻祖语言,所以说学习C语言是进入编程世界的必…...
postgresql \watch实用的使用方法
文章目录 1.介绍2.语法3.实用的使用方法3.1 慢sql监控3.2 长wait事件3.3 日志输出量3.3结合pg_stat_database使用3.4 结合pg_stat_bgwriter使用3.5 其他 1.介绍 \watch Postgres 9.3 版带来的一个有用的命令,与linux watch指令类似,可以帮我们在指定间隔…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...

微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合
作者:来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布,Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明,Elastic 作为 …...

VisualXML全新升级 | 新增数据库编辑功能
VisualXML是一个功能强大的网络总线设计工具,专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑(如DBC、LDF、ARXML、HEX等),并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...

热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁
赛门铁克威胁猎手团队最新报告披露,数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据,严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能,但SEMR…...