手撕数据结构之栈+例题

目录

一、栈的概念及结构

二、栈的头文件及基本框架

三、接口实现

1、对栈的初始化

 2、栈的销毁

3、入栈操作

4、出栈操作

 5、判断栈是否为空

6、返回栈顶元素

7、遍历栈

四、有效的括号 - 力扣(LeetCode)

题目描述:

 思路:

代码:


一、栈的概念及结构

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出的原则。

如同子弹夹,我们进行添子弹和出子弹,很形象。

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。

出栈:栈的删除操作叫做出栈。出数据也在栈顶。

 接下来,我们以数组栈的形式去模拟。

二、栈的头文件及基本框架

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

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;//就是以a开头的一段连续的空间
	int top;//定义栈顶位置
	int capacity;
}ST;

void SLInit(ST* ps);
void SLDestroy(ST* ps);
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
STDataType STTop(ST* ps);//获取栈顶元素

三、接口实现

1、对栈的初始化

void SLInit(ST* ps)
{
	ST* ret = (ST*)malloc(4 * sizeof(ST));
	if (ret == NULL)
	{
		perror(malloc);
		exit(-1);
	}
	ps->a = ret;
	ps->capacity = 4;
	ps->top = 0;
}

 2、栈的销毁

void SLDestroy(ST* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

3、入栈操作

void STPush(ST* ps, STDataType x)
{
	assert(ps != NULL);
	//检查需不需要扩容
	if (ps->top == ps->capacity)
	{
		ps->capacity += 4;
		ST* ret = (ST*)realloc( ps->a, sizeof(ST) * ps->capacity);
		if (ret == NULL)
		{
			perror(realloc);
			exit(-1);
		}
		ps->a = ret;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

4、出栈操作

void STPop(ST* ps)
{
	assert(ps);
	ps->top--;
}

 5、判断栈是否为空

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
    如果右边等式成立返回true,反之返回false
}

6、返回栈顶元素

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

7、遍历栈

不同于其他数据结构,遍历栈不用print

//遍历栈的特殊方式
	while (!STEmpty(&ps))
	{
		printf("%d ", STTop(&ps));
		STPop(&ps);
	}

四、有效的括号 - 力扣(LeetCode)

题目描述:

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

 思路:

如果是左括号就入栈,如果是右括号就与栈顶元素进行比较。这样就正好匹配题目的要求,但博主目前没有学过STL库,所以只能将上面的手撕栈CV一下啦,下面的代码为了避免冗余去除掉这一部分~

代码:

bool isValid(char * s)
{
    char* ret = s;
    int num = 0;
    //利用奇数偶数判断数量是否匹配
    while(*ret)
    {
        num++;
        ret++;
    }
    if(num%2 != 0)
    {
        return false;
    }
    ST ps;
	SLInit(&ps);
    while(*s)
    {
    switch(*s)
    {
        case '{':
        case '[':
        case '(':
            STPush(&ps,*s);
            break;
        case ')':
        case ']':
        case '}':
            if(STSize(&ps) == 0)
                return false;
            if(*s == ']' && STTop(&ps) != '['||
               *s == ')' && STTop(&ps) != '('||
               *s == '}' && STTop(&ps) != '{')
            {
                SLDestroy(&ps);
                return false;
            }
            STPop(&ps);
            break;
    }
    s++;
    }
    //防止((出现
    if(!STEmpty(&ps))
        return false;
    return true;
}

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

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

相关文章

QT自带PDF库的使用

QT自带PDF库可以方便的打开PDF文件&#xff0c;并将文件解析为QImage&#xff0c;相比网上提供的开源库&#xff0c;QT自带PDF库使用更方便&#xff0c;也更加可靠&#xff0c;然而&#xff0c;QT自带PDF库的使用却不同于其他通用库的使用&#xff0c;具备一定的技巧。 1. 安装…

Session与Cookie的区别(五)

储存状态的方式 小明的故事说完了&#xff0c;该来把上面这一段变成网络的实际案例了。其实在网络世界中问题也是一样的。 前面已经提到过我们会把状态存在 Cookie 里面&#xff0c;让 Request 之间能够变得有关联。 假设我们今天要来做一个会员系统&#xff0c;那我要怎么知道…

UML箭头汇总

参考&#xff1a;http://www.cnblogs.com/damsoft/archive/2016/10/24/5993602.html 1.UML简介 Unified Modeling Language (UML)又称统一建模语言或标准建模语言。 简单说就是以图形方式表现模型&#xff0c;根据不同模型进行分类&#xff0c;在UML 2.0中有13种图&#xff…

青大数据结构【2015】

一、单选 二、简答 5.如果一组关键字&#xff0c;以不同的次序输入后建立起来的二叉排序树是否相同&#xff1f;当中序遍历这些二叉排序树时&#xff0c;其遍历的结果是否相同&#xff1f;为什么&#xff1f; 不同&#xff0c;因为输入次序不同&#xff0c;所放置的位置与上一…

idea打开多个项目需要开多个窗口(恢复询问弹窗)

【版权所有&#xff0c;文章允许转载&#xff0c;但须以链接方式注明源地址&#xff0c;否则追究法律责任】【创作不易&#xff0c;点个赞就是对我最大的支持】 前言 仅作为学习笔记&#xff0c;供大家参考 总结的不错的话&#xff0c;记得点赞收藏关注哦&#xff01; 使用…

【C++】异常exception

文章目录 1. C语言中传统的处理错误方法2. C中的异常3. 异常的使用3.1 异常的抛出和捕获3.2 异常的重新抛出3.3 异常安全3.4 异常规范 4. 自定义异常体系5. 异常的优缺点 &#x1f4dd; 个人主页 &#xff1a;超人不会飞)&#x1f4d1; 本文收录专栏&#xff1a;《C的修行之路》…

拥抱创新:用Kotlin开发高效Android应用

拥抱创新&#xff1a;用Kotlin开发高效Android应用 引言 在当今数字时代&#xff0c;移动应用已经成为人们生活中不可或缺的一部分。无论是社交媒体、电子商务还是健康管理&#xff0c;移动应用已经深刻地影响了我们的生活方式。随着移动设备的普及和功能的增强&#xff0c;A…

无涯教程-Perl - endpwent函数

描述 此功能告诉系统您不再希望使用getpwent从密码文件读取条目。在Windows下,使用Win32API::Net函数从域服务器获取信息。 语法 以下是此函数的简单语法- endpwent返回值 此函数不返回任何值。 例 以下是显示其基本用法的示例代码- #!/usr/bin/perlwhile(($name, $pas…

vr虚拟仿真消防模拟演练提升受训者的安全观念和防范技能

纵观多年来的火灾事故教训得知&#xff0c;火灾发生的原因复杂多样&#xff0c;仅采取单一教育形式无法达到预期效果。消防安全重在预防&#xff0c;VR消防模拟演练系统将火灾安全问题&#xff0c;经采集和汇集处理&#xff0c;以可视化的形式在安全培训平台上进行实时展现&…

Elasticsearch同时使用should和must

问题及解决方法 must和should组合查询&#xff0c;should失效。使用must嵌套查询&#xff0c;将should组成的bool查询包含在其中一个must查询中。 SearchRequest request new SearchRequest(); request.indices("function_log");SearchSourceBuilder sourceBuilde…

Linux C 语言 mosquitto 方式 MQTT 发布消息

1 说明 采用 mosquitto 库&#xff0c;实现对主题发布消息。 其中服务器有做限制&#xff0c;需要对应的 cilent id &#xff0c;cafile 、certfile 、keyfile 等配置 2 开发环境 采用ubuntu 直接编译调试 安装mosquitto 库 sudo apt install libmosquitto-dev sudo apt-ge…

Linux 上安装部署Nacos

标题&#xff1a;在Linux上安装和部署Nacos Nacos是一个开源的分布式服务发现和配置管理平台&#xff0c;它可以帮助开发人员实现微服务架构中的服务注册、发现和动态配置管理。 步骤1&#xff1a;准备工作 在开始安装Nacos之前&#xff0c;确保您已经具备以下条件&#xff1…

ProComponent 用法学习

相信很多同学都用过 Ant Design 这一 react 著名组件库&#xff0c;而 ProComponents 则是在 antd 之上进行封装的页面级组件库&#xff08;指一个组件就可以搞定一个页面&#xff09;。它同时也是 Ant Design Pro 中后台框架所用的主要组件库。如果你手上有要用 react 开发的中…

LiveGBS流媒体平台GB/T28181常见问题-无法注册不上海康NVR摄像机自带物联网卡摄像头注册GB/T28181国标平台看不到设备的时候如何抓包及排查

LiveGBS无法注册不上海康NVR摄像机自带物联网卡摄像头注册GB/T28181国标平台看不到设备的时候如何抓包及排查 1、设备注册后查看不到1.1、是否是自带物联网卡的摄像头1.2、关闭萤石云1.3、防火墙排查1.4、端口排查1.5、IP地址排查1.6、设备TCP/IP配置排查1.7、设备多网卡排查1.…

合并区间——力扣56

文章目录 题目描述解法一 排序题目描述 解法一 排序 vector<vector<int>> merge(vector<vector<int>>& intervals

8.10论文阅读

文章目录 The multimodal MRI brain tumor segmentation based on AD-Net摘要本文方法损失函数 实验结果 max-vit - unet:多轴注意力医学图像分割摘要本文方法实验结果 The multimodal MRI brain tumor segmentation based on AD-Net 摘要 基于磁共振成像(MRI)的多模态胶质瘤…

使用乐观锁解决超卖问题

目录 什么是超卖&#xff1f; 乐观锁和悲观锁的定义 悲观锁&#xff1a; 乐观锁&#xff1a; 乐观锁的实现方式 1.版本号 2.CAS法 什么是超卖&#xff1f; 举个例子&#xff1a;订单系统中&#xff0c;用户在执行下单操作时&#xff0c;可能同一时间有无数个用户同时下单&…

无涯教程-Perl - keys函数

描述 此函数以列表形式返回哈希的所有键。键以随机顺序返回,但实际上,它们与值和每个值使用相同的顺序。 语法 以下是此函数的简单语法- keys HASH返回值 此函数在标量context中返回哈希中的键数,在列表context中返回键列表。 例 以下是显示其基本用法的示例代码- #!/u…

了解华为(H3C)网络设备和OSI模型基本概念

目录 一&#xff0c;认识华为 1.华为发展史 2.华为网络设备介绍 3.VRP概述 二&#xff0c;OSI七层模型 1.七层模型详细表格 2.各层的作用 3.数据在各层之间的传递过程 4.OSI四层网络模型 一&#xff0c;认识华为 官网&#xff1a;https://www.huawei.com/cn/ 1.华为发…

leetcode - 75. 颜色分类(java)

颜色分类 leetcode - 75. 颜色分类题目描述双指针代码演示 双指针算法专题 leetcode - 75. 颜色分类 难度 - 中等 原题链接 - 颜色分类 题目描述 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums &#xff0c;原地对它们进行排序&#xff0c;使得相同颜色的元素相邻&…