简单数据结构——栈和队列1(栈超全）（初始化，销毁，出栈入栈销毁实现，例题运用）

知识特点

类似数据表链表，在逻辑上依次存储，但对比顺序表和链表有所限制，不能随便存储

一定要先掌握顺序表的实现，本人博客有顺序表专栏大家可以自行查看，看懂顺序表专栏之后再来了解栈的实现会更容易懂。

如果还没有掌握顺序表可以先收藏本篇文章再进行查看本篇内容。

1.栈

1.1栈的概念和结构

一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除的一端叫做栈顶，另一端叫做栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

删除数据：出栈

栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶：压栈

 类比：羽毛球桶和弹夹（后压进去的先出来）

 单链表/双链表都可以实现栈

2.栈的实现

2.1选择实现方式

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小

首先不选择双链表:对比单链表还有2倍指针，不宜维护，更加复杂化了

数组实现栈缺点：插入数据不够了需要扩容，自身有消耗，但是开辟空见释放空间调用速度很快，所以影响不大

数组实现栈优点：cpu高速缓存速率很快

数组和单链表相差不大，我们选择数组来实现

2.2栈的实现创建头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>



typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//用size也可以，两者都行
	int capacity;
}ST;
//初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);


//实现插入，不用分头插尾插，因为只能从栈顶插入
void STPush(ST*pst,STDataType x);
void STPop(ST* pst);//取栈顶数据


//形参需要传过来指针，否则实现完初始化之后无法传回去
//这一部分在结构体里又讲（大家可以去看侧栏合集）
// 

//  获取栈顶数据
STDataType STTop(ST* pst);


//提供两个接口
bool STEmpty(ST* pst);//判断栈是否为空

//获取栈里面的数据个数
int STSize(ST* pst);

 vs中实现图：

2.3栈的实现创建源文件

2.3.1需要注意top（为什么pst->top=-1;)

1.top到底是只想哪里呢？（top指向栈顶数据，但是有两个方法表示）

指向栈顶还是指向栈顶的下一个元素呢？

其实是根据自己的定义来的

 法一：（top指向栈顶元素）
若想要top直接指向栈顶元素，那么初始化的时候top就不能为0

因为top如果为0就无法清楚此时到底是有元素还是没有元素（存在误导）。

所以top一开始初始化就应该指向-1，这样top指向0的时候就可以表示为指向了第一个元素，类似于数组，第一个元素下标为0，第二个元素下标为1；（top指向栈顶元素）

法二：（top指向栈顶下一个元素）

如果top指向了栈顶，直接指向0，那么说明第一个元素指向了1；

（类比size的用法就可）

注意：两种方式都可以，但是前后需要匹配

若pst->top=0;说明top指向栈顶数据的下一个位置。

若pst->top=-1;说明top指向栈顶数据。

一定要区分清楚!!!!!!(用数组设计栈的关键点）

不能误认为top初始化为0并且top还指向栈顶元素。

选择一个方式就行（我们选择初始化为0的方式，也就是说指向栈顶元素的下一个元素，而不是栈顶元素）

2.3.2为什么不能直接用结构体引用而是要用函数呢？

    是否可以用直接自行访问数据?
 

（建议还是要规范运用函数调用而不是自己调用，很容易出错）

2.3.3实现

#include"Stack.h"
void STInit(ST* pst)
{
	assert(pst);//首先需要断言传过来的不能是空指针
	//然后开始对方法中的每一个成员变量初始化
	pst->a = NULL;
	pst->top = 0;//（已经讲解）
	pst->capacity = 0;
}
//摧毁
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);//free掉之后记得要置为空
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}


//入栈出栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);//实 现的第一步都是先进行断言
	//当top==capacity时说明容量已经满了，此时需要扩容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
			//如果没有开辟成功就直接报错
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity; 
	}
	pst->a[pst->top] = x;
	pst->top++;//存入数据之后top需要+1
}   
//出栈
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--; 
}  
//取栈顶数据
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top>0);
	return pst->a[pst->top - 1];//返回
}


bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top==0;//因为top指向的是栈顶的后面一个元素，因此如果是返回0的话说明该栈为空，没有任何元素；
}//这里是判断真假

int STSize(ST* pst)
{
	assert(pst);
	return pst->top;//我们是用法二来定义top的,所以top的使用与size类似，因此，数据个数可以直接返回top就可以计算出来
}

3.栈的例题（括号匹配）

题目：

 

解答：

//利用栈的思想来解题
//在c语言中首先要创建一个栈
#pragma once 
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef char STDataType;//因为是字符

typedef struct Stack
{
    STDataType* a;
    int top;
    int capacity;
}ST;

// 初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);

// 入栈  出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);

// 取栈顶数据
STDataType STTop(ST* pst);

// 判空
bool STEmpty(ST* pst);
// 获取数据个数
int STSize(ST* pst);


// 初始化和销毁
void STInit(ST* pst)
{
    assert(pst);

    pst->a = NULL;
    // top指向栈顶数据的下一个位置
    pst->top = 0;

    // top指向栈顶数据
    //pst->top = -1;

    pst->capacity = 0;
}

void STDestroy(ST* pst)
{
    assert(pst);

    free(pst->a);
    pst->a = NULL;
    pst->top = pst->capacity = 0;
}

// 入栈  出栈
void STPush(ST* pst, STDataType x)
{
    assert(pst);

    // 扩容
    if (pst->top == pst->capacity)
    {
        int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
        if (tmp == NULL)
        {
            perror("realloc fail");
            return;
        }

        pst->a = tmp;
        pst->capacity = newcapacity;
    }

    pst->a[pst->top] = x;
    pst->top++;
}

void STPop(ST* pst)
{
    assert(pst);
    assert(pst->top > 0);

    pst->top--;
}


// 取栈顶数据
STDataType STTop(ST* pst)
{
    assert(pst);
    assert(pst->top > 0);

    return pst->a[pst->top - 1];
}

// 判空
bool STEmpty(ST* pst)
{
    assert(pst);

    return pst->top == 0;
}

// 获取数据个数
int STSize(ST* pst)
{
    assert(pst);

    return pst->top;
}

bool  isValid(char* s)
{
    //新建一个成员变量st
    ST st;
    STInt(&st);
    while (*s)//如果是\0就直接结束了
    {
        //如果是左括号就入栈
        if (*s == '(' || *s == '[' || *s == '{')
        {
            STPush(&st, *s);//入栈
        }
        else//右括号取栈顶左括号尝试匹配
        {
            char top = STTop(&st);
            STPop(&st);//取出一个，删除一个方便取出
            //如果判断匹配，那如果匹配还要再进行下一个比对，因此可以直接判断不匹配的情况
            if ((top == '(' && *s != ')') || (top == '[' && *s != ']')
                || (top == '{' && *s != '}'))
            {
                STDestroy(&st);
                return false;
            }
        }
        ++s;
    }
    //不用栈记得销毁,避免内存泄漏

    //栈不为空，说明左括号比右括号多，数量不匹配
    bool ret = STEmpty(&st);
    STDestroy(&st);
    return ret;
}

完-

这一篇属于将前面几节内容串起来加上运用的知识，所以如果尽量先把前面内容搞懂。

看到这里不容易，这篇内容比较多写了2天，如果有帮助的话，希望得到您的点赞收藏哦。感谢认可，接下来会继续更新队列相关知识点

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/605968.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Xilinx FPGA底层逻辑资源简介(1)：关于LC，CLB，SLICE，LUT，FF的概念

Xilinx FPGA底层逻辑资源简介(1)：关于LC，CLB，SLICE，LUT，FF的概念

LC&#xff1a;Logic Cell 逻辑单元 Logic Cell是Xilinx定义的一种标准&#xff0c;用于定义不同系列器件的大小。对于7系列芯片&#xff0c;通常在名字中就已经体现了LC的大小&#xff0c;在UG474中原话为&#xff1a; 对于7a75t芯片&#xff0c;LC的大小为75K&#xff0c;6输…
阅读更多...
LangChain：简化大模型应用

LangChain：简化大模型应用

LangChain 框架提供了常见用例的抽象&#xff0c;简化了大型语言模型&#xff08;LLM&#xff09;&#xff08;如 OpenAI GPT4 或 Google PaLM&#xff09;的应用。它支持 JavaScript 和 Python。 为了弄清楚为什么需要 LangChain&#xff0c;我们先来看下 LLM 的工作原理。 …
阅读更多...
ctfshow-web入门-102

ctfshow-web入门-102

这个题我想记录一下&#xff0c;主要是这个方法属实是有点惊艳到我了。故而进行记录&#xff0c;也为了方便大家阅读理解。 看题目&#xff0c;根据题目我写一下我的分析&#xff1a; $_POST传入一个v1&#xff0c;$_GET传入一个v2&#xff0c;一个v3。 赋值符号 优先级高于…
阅读更多...
echarts双Y轴,并实现图例等

echarts双Y轴,并实现图例等

一个Y轴时yAxis为对象 yAxis: {type: value,name: 占比(%) },两个Y轴时yAxis为数组 yAxis: [{ // 左侧的type: value,name: 占比(%),nameTextStyle: {padding: [0, 0, 10, -50]},min: 0,max: 100,splitNumber: this.splitNumber, // 设置坐标轴的分割段数interval: 20, // 标轴…
阅读更多...
【牛客】Tokitsukaze and Average of Substring

【牛客】Tokitsukaze and Average of Substring

原题链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析 前缀和。 开一个int类型的前缀和数组pre[30][N]&#xff08;pre[i][j]表示某字符转成的数字 i 在一段区间的前缀个数。因为字母表有‘a’~z…
阅读更多...
并发编程实现

并发编程实现

一、并行编程 1、Parallel 类 Parallel类是System.Threading.Tasks命名空间中的一个重要类&#xff0c;它提供数据并行和任务并行的高级抽象。 For和ForEach Parallel类下的For和ForEach对应着普通的循环和遍历(普通的for和foreach)&#xff0c;但执行时会尝试在多个线程上…
阅读更多...
Blender修改器

Blender修改器

修改器 Modifier&#xff0c;对模型进行修改&#xff0c;相当于一个函数。 修改器图标是界面右下角的扳手样式 每个修改器的顶部都有如下样式&#xff0c;从左到右分别为&#xff1a;展开/折叠&#xff0c;修改器类型&#xff0c;修改器名称&#xff0c;编辑模式按钮&#xff…
阅读更多...
游戏辅助 -- 某游戏一键端配置

游戏辅助 -- 某游戏一键端配置

游戏一键端下载地址及安装视频&#xff1a; https://pan.quark.cn/s/e6a373d94707 ​https://pan.quark.cn/s/ef7ab0c48776 准备工作 Vmware虚拟机软件&#xff1a;用于创建和管理虚拟机。 SecureCRT&#xff1a;一款支持SSH的终端仿真程序&#xff0c;用于远程登陆服务器…
阅读更多...
SoC系统中AXI4 AXI3兼容性及exclusive access

SoC系统中AXI4 AXI3兼容性及exclusive access

AXI4和AXI3是高级扩展接口&#xff08;Advanced eXtensible Interface&#xff09;的两个不同版本&#xff0c;它们都是用于SoC&#xff08;System on Chip&#xff09;设计中的总线协议&#xff0c;用于处理器和其它外设之间的高速数据传输。以下是它们之间的一些主要区别&…
阅读更多...
vscode设置免密登录远程服务器

vscode设置免密登录远程服务器

文章目录 1. 问题描述2. 解决方案3. 原理 1. 问题描述 当我们使用vscode的ssh连接远程服务器后&#xff0c;过一段时间后&#xff0c;总是要求登录服务器的密码。 这就导致一个麻烦就是: 无论是在公司还是在学校&#xff0c;密码往往不是自己设置的&#xff0c;所以记忆起来就…
阅读更多...
利用BACnet分布式IO控制器优化Niagara楼宇自动化系统

利用BACnet分布式IO控制器优化Niagara楼宇自动化系统

在智能建筑领域&#xff0c;随着物联网技术的飞速发展&#xff0c;如何实现高效、灵活且安全的楼宇自动化控制成为了行业关注的焦点。BACnet IP分布式远程I/O模块&#xff0c;作为这一领域的创新成果&#xff0c;正逐渐成为连接智能建筑各子系统的关键桥梁&#xff0c;尤其在与…
阅读更多...
蓝桥杯练习系统（算法训练）ALGO-946 Q神的足球赛

蓝桥杯练习系统（算法训练）ALGO-946 Q神的足球赛

资源限制 内存限制&#xff1a;256.0MB C/C时间限制&#xff1a;1.0s Java时间限制&#xff1a;3.0s Python时间限制&#xff1a;5.0s 问题描述 足球赛上&#xff0c;只见Q神如闪电般的速度带球时而左&#xff0c;时而右&#xff0c;时而前&#xff0c;时而后&#xff…
阅读更多...
带你入门React

带你入门React

目录 前言一&#xff0c;基本配置1.1 环境搭建1.2 页面初始化渲染二&#xff0c;基础学习2.1 结构与样式开发2.2 数据展示2.3 行内样式2.4 条件渲染2.5 列表渲染2.6 点击事件 三&#xff0c;页面更新3.1 组件数据3.2 组件数据共享 总结 前言 笔者之前的工作经验都局限于Vue&am…
阅读更多...
pandas快速使用

pandas快速使用

DataFrame介绍 Dateframe结构和列表类似&#xff0c;区别是对于DataFrame的每一列和每一行均有一个标签。例如以下数据&#xff0c; 上述数据中&#xff0c;日期作为每行的标签。a、b、c、d、e分别是每列的标签 生成连续日期数据 使用方法date_range()&#xff0c;该方法有两…
阅读更多...
Lazada商品详情API接口：深度解析与应用

Lazada商品详情API接口：深度解析与应用

前言 在当今电子商务的繁荣时代&#xff0c;对于电商平台来说&#xff0c;提供一套高效、稳定的API接口是非常重要的。Lazada&#xff0c;作为东南亚领先的电商平台之一&#xff0c;其API接口体系为卖家、开发者以及第三方服务提供了丰富的功能和数据支持。其中&#xff0c;商品…
阅读更多...
邦注科技 模具保护器 CCD电子眼 专业工业视觉检测设备

邦注科技 模具保护器 CCD电子眼 专业工业视觉检测设备

模具保护器是一种用于保护模具的设备&#xff0c;可以在塑料压铸和冲床等加工过程中起到保护模具的作用。以下是关于模具保护器在保护塑料压铸和冲床模具方面的应用&#xff1a; 塑料压铸模具保护器&#xff1a; 防止碰撞&#xff1a;在塑料压铸过程中&#xff0c;模具可能会…
阅读更多...
初识C++ · 内存管理

初识C++ · 内存管理

目录 1 C/C的内存分布 2 C语言的内存管理 3 C的内存管理 4 operator new 和 operator delete 5 定位new 1 C/C的内存分布 语言不同&#xff0c;内存分布是相同的&#xff0c;对于局部变量都是放在栈上&#xff0c;全局变量都是放在静态区&#xff08;数据段&#xff09;&…
阅读更多...
jvm重要参数可视化和线上问题排查

jvm重要参数可视化和线上问题排查

jvm重要参数可视化和线上问题排查 目标jvm参数分类(了解)运行时数据区相关的&#xff08;jdk1.8&#xff09;处理 OOM 相关的垃圾回收器相关的GC 日志记录相关的意义,默认值,调优原则&#xff08;重要&#xff0c; 待拆分&#xff09; 排查 OOM 流程 和 常见原因参考文章 目标 …
阅读更多...
基于C语言中的类型转换，C++标准创造出了更加可视化的类型转换

基于C语言中的类型转换，C++标准创造出了更加可视化的类型转换

目录 前言 一、 C语言中的类型转换 二、为什么C需要四种类型转换 三、C中新增的四种强制类型转换操作符以及它们的应用场景 1.static_cast 2.reinterpret_cast 3.const_cast 4.dynamic_cast 前言 在C语言中&#xff0c;如果赋值运算符左右两侧的类型不同&#xff0c;或者…
阅读更多...
短视频矩阵系统贴牌---saas源头开发

短视频矩阵系统贴牌---saas源头开发

一、短视频矩阵运营注意事项&#xff1a; 如&#xff1a;房产行业 短视频矩阵运营是一个系统化的项目&#xff0c;涉及多个平台和账号的管理&#xff0c;以及内容的创作、发布和优化等多个方面。 以下是短视频矩阵运营的注意事项文档的概要以及结果运营数据 一周持续运营量 二…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站