栈的实现与OJ括号匹配

今日备忘录: "不破不立. "

本文索引

  • 1. 前言
  • 2. 顺序表与链表的区别
  • 3. 什么是栈
  • 4. 栈的实现
  • 5. OJ括号匹配
  • 6. 总结

1. 前言

人总是在坍塌中重建, 有些东西必须摧毁, 才能迎来新生, 不管是那些消耗你的人, 还是令你感到焦虑的事情, 还是一份你觉得毫无意义并且又不喜欢的工作, 又或者是那个内心敏感的自己, 总之你害怕什么, 就要去面对什么, 你想要什么, 就要去靠近什么, 在声色名利中守住本性, 在世俗目光中信步前行, 大浪淘沙, 去伪存真, 破而后立, 否极泰来.

本文旨在探讨数据结构中栈的实现以及顺序表与链表区别总结.
更多精彩, 期待关注 主页: 酷酷学!!!

2. 顺序表与链表的区别

在实现栈之前, 我们先总结一下顺序表和链表
在这里插入图片描述
以上是顺序表与链表比较全面的区别总结, 在插入数据时链表没有容量的概念指的是链表的空间是使用多少开辟多少, 不会进行扩容操作, 也不会造成容量的浪费.

那么什么是缓存利用率,简单讲解一下

在这里插入图片描述
以上是存储器的结构层次,由于CPU的访问速度非常的快, 它不会直接访问内存, 因为内存的读写速度太慢了, 而是将数据先逐层转移到寄存器或者高速缓存中,在进行读写, 一般寄存器存放字节大小为8的数据, 然后CPU再进行访问, 但是如何将数据转移到缓存当中的呢, 为什么说顺序表缓存利用率高而链表低呢?

在这里插入图片描述

在将内存中的数据运送到缓存中的时候, 不是一个一个传输的,而是将连带后面的一块空间直接一起运送到缓存中, 如同一辆大巴车一样, 不是一个一个运送, 而是包括后面的一块空间一起运输, 然后CPU在从缓存中进行读写, 那么, 如果继续往后读写, 在缓存中, 我们称之为缓存命中, 直接访问, 如果不在缓存中, 我们称之为不命中, 要把数据从内存加载到缓存中, 在进行访问, 如此看来所以 顺序表的缓存利用率肯定高于链表

更多资讯, 可以点击参考 与程序员相关的CPU缓存知识

3. 什么是栈

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

压栈 : 栈的插入操作叫做压栈或入栈, 入数据在栈顶
出栈 : 栈的删除操作叫做出栈. 出数据也在栈顶.

在这里插入图片描述
在这里插入图片描述

4. 栈的实现

栈的实现一般可以使用数组或者链表进行实现, 相对而言数组的结构实现更优一些, 因为在数组上尾插数据的代价比较小, 而且数组的缓存利用率比较高.

在这里插入图片描述
在这里插入图片描述
第一步:

创建三个文件
在这里插入图片描述
在头文件中进行结构定义和函数声明

#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 InitStack(ST* pst);
//销毁
void Destory(ST* pst);

//压栈
void Push(ST* pst,STDatatype x);
//出栈
void Pop(ST* pst);
//取栈顶元素
STDatatype STTop(ST* pst);

//判空
bool Empty(ST* pst);
//获取元素个数
int Size(ST* pst);

第二步:
实现栈的方法

  • 初始化
void InitStack(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}

注意
top的值根据自己的情况定义, 若top=0,表示指向栈顶数据下一个位置, top=-1,表示指向栈顶数据.
在这里插入图片描述

首先断言,这里肯定不能给我传一个NULL, 然后进行常规操作

  • 销毁
void Destory(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}

动态顺序表, 空间需要手动释放

  • 压栈
void Push(ST* pst, STDatatype x)
{
	assert(pst);
	if (pst->capacity == pst->top)
	{
		int Newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDatatype* tmp = (STDatatype*)realloc(pst->a,sizeof(STDatatype) * Newcapacity);
		if (tmp == NULL)
		{
			perror("malloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = Newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}

因为我们初始化的时候没有开辟空间, 所以如果栈为空的时候, 我们先开辟四个空间, 当栈满时, 我们在成倍扩容, 然后先用临时变量存储首地址, 防止申请失败原地址丢失, 然后更改空间容量大小, 最后在进行写入数据.

  • 销毁
void Pop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}

首先栈不能为NULL, 并且需要有数据, 然后直接top-- 就行.

  • 获取栈顶元素
STDatatype STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top-1];
}

直接返回top的前一个位置

  • 判断栈是否为空
bool Empty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}

如果top为0则栈为空

  • 获取数据个数
int Size(ST* pst)
{
	assert(pst);
	return pst->top;
}

top表示下标, 也就是元素个数

5. OJ括号匹配

题目链接: 有效的括号

题目描述:

在这里插入图片描述
题目分析:

首先题目有三个要求

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

如果我们直接用左括号个数与右括号进行比较的话, 那么顺序问题我们无法解决, 而栈这种后进先出的结构恰好可以解决这种问题, 当遇到左括号时进行压栈, 遇到右括号时将左括号出栈, 进行比较, 正好解决了顺序问题, 但是C语言没有栈这种结构, 所以我们需要自己写栈这种结构.
于是我们很容易写出下面的代码.

bool isValid(char* s) {
	ST stack;
	InitStack(&stack);
	while (*s)
	{
		//左括号压栈
		if (*s == '(' || *s == '{' || *s == '[')
		{
			Push(&stack, *s);
			s++;
		}
		//右括号与栈顶左括号进行匹配
		else
		{

			char tmp = STTop(&stack);
			Pop(&stack);
			//如果不匹配
			if ((tmp == '(' && *s != ')')
				|| (tmp == '[' && *s != ']')
				|| (tmp == "{" && *s != '}'))
			{
				return false;
				Destory(&stack);
			}
		}
	}
	return true;
	Destory(&stack);
}

但是这样写真的对吗, 答案是错的, 因为如果只有左括号的情况, 和只有右括号的情况, 我们还需要加以判断. 修正代码
字符串只有右括号, 先判断栈是否为空, 若为空返回false,并且释放栈

字符串只有左括号, 循环结束, 看看栈中元素还有没有, 如果还有则返回false,并且销毁栈

bool isValid(char* s) {
    ST stack;
    InitStack(&stack);
    while (*s) {
        // 左括号压栈
        if (*s == '(' || *s == '{' || *s == '[') {
            Push(&stack, *s);
        }
        // 右括号与栈顶左括号进行匹配
        else {
            if (Empty(&stack)) {
                Destory(&stack);
                return false;
            }
            char tmp = STTop(&stack);
            Pop(&stack);
            // 如果不匹配
            if ((tmp == '(' && *s != ')') || (tmp == '[' && *s != ']') ||
                (tmp == '{' && *s != '}')) {
                Destory(&stack);
                return false;
            }
        }
        ++s;
    }
    bool ret = Empty(&stack);
    Destory(&stack);
    return ret;
}

全部代码如下:

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

// 初始化
void InitStack(ST* pst);
// 销毁
void Destory(ST* pst);

// 压栈
void Push(ST* pst, STDatatype x);
// 出栈
void Pop(ST* pst);
// 取栈顶元素
STDatatype STTop(ST* pst);

// 判空
bool Empty(ST* pst);
// 获取元素个数
int Size(ST* pst);

void InitStack(ST* pst) {
    assert(pst);
    pst->a = NULL;
    pst->capacity = pst->top = 0;
}

void Destory(ST* pst) {
    assert(pst);
    free(pst->a);
    pst->a = NULL;
    pst->top = pst->capacity = 0;
}

void Push(ST* pst, STDatatype x) {
    assert(pst);
    if (pst->capacity == pst->top) {
        int Newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
        STDatatype* tmp =
            (STDatatype*)realloc(pst->a, sizeof(STDatatype) * Newcapacity);
        if (tmp == NULL) {
            perror("malloc fail");
            return;
        }
        pst->a = tmp;
        pst->capacity = Newcapacity;
    }
    pst->a[pst->top] = x;
    pst->top++;
}

void Pop(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 Empty(ST* pst) {
    assert(pst);
    return pst->top == 0;
}

int Size(ST* pst) {
    assert(pst);
    return pst->top;
}

bool isValid(char* s) {
    ST stack;
    InitStack(&stack);
    while (*s) {
        // 左括号压栈
        if (*s == '(' || *s == '{' || *s == '[') {
            Push(&stack, *s);
        }
        // 右括号与栈顶左括号进行匹配
        else {
            if (Empty(&stack)) {
                Destory(&stack);
                return false;
            }
            char tmp = STTop(&stack);
            Pop(&stack);
            // 如果不匹配
            if ((tmp == '(' && *s != ')') || (tmp == '[' && *s != ']') ||
                (tmp == '{' && *s != '}')) {
                Destory(&stack);
                return false;
            }
        }
        ++s;
    }
    bool ret = Empty(&stack);
    Destory(&stack);
    return ret;
}

6. 总结

栈是一种线性数据结构，具有后进先出（LIFO）的特点，即最后进入栈的元素最先被访问或删除。栈通常有两种基本操作：压栈（push）和弹栈（pop），分别用于将元素压入栈顶和从栈顶弹出元素。

栈的应用非常广泛，常见的应用包括表达式求值、函数调用、浏览器的前进后退功能等。在计算机科学中，栈也被用于实现递归算法、解决括号匹配等问题。

栈的实现方式有多种，包括基于数组和基于链表的实现。基于数组的实现通常需要指定栈的最大容量，而基于链表的实现则可以动态调整大小。

总的来说，栈是一种非常重要且常用的数据结构，掌握栈的基本操作和应用场景对于理解算法和数据结构有着重要的意义。

如果此文有帮助 感谢点赞关注!!!

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

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

相关文章

CSS3私有前缀+新增盒模型相关属性+新增背景属性（如果想知道CSS3私有前缀、新增盒模型相关属性的知识点，那么只看这一篇就足够了！）

CSS3私有前缀+新增盒模型相关属性+新增背景属性（如果想知道CSS3私有前缀、新增盒模型相关属性的知识点，那么只看这一篇就足够了！）

前言&#xff1a;CSS3 是CSS2 的升级版本&#xff0c;它在CSS2 的基础上&#xff0c;新增了很多强大的新功能&#xff0c;从而解决一些实际面临的问题。 ✨✨✨这里是秋刀鱼不做梦的BLOG ✨✨✨想要了解更多内容可以访问我的主页秋刀鱼不做梦-CSDN博客 先让我们看一下本篇文章的…
阅读更多...
解聘7名教授！高校取消终身教授制度，启动全员“末位淘汰”

解聘7名教授！高校取消终身教授制度，启动全员“末位淘汰”

如今&#xff0c;高校是越来越卷了&#xff0c;身处其中的每个人似乎都无法避免。 前一段时间&#xff0c;国内某985高校说是要搞职称降级聘任&#xff0c;另一所985高校说要淘汰多少比例的教师&#xff0c;引发学术圈广泛讨论。 国外呢&#xff0c;同样要卷起来了&#xff0…
阅读更多...
[代码比较工具下载及使用]你真的需要一个代码比较工具

[代码比较工具下载及使用]你真的需要一个代码比较工具

&#x1f496;&#x1f496;&#x1f496;欢迎来到我的博客&#xff0c;我是anmory&#x1f496;&#x1f496;&#x1f496; 又和大家见面了 欢迎来到资源分享系列 这里有你想要的各种高质量资源 先来自我推荐一波 个人网站欢迎访问以及捐款 推荐阅读 如何低成本搭建个人网站 …
阅读更多...
STM32-LCD液晶屏（ILI9341）

STM32-LCD液晶屏（ILI9341）

MCU&#xff1a;STM32F103VET6 开发环境&#xff1a;STM32CubeMXMDK5 目录 STM32液晶屏LCD&#xff08;ILI9341&#xff09; LCD液晶显示 液晶控制原理 ILI9341液晶控制器简介 8080写时序 8080读时序 FSMC模拟8080时序 液晶屏的信号线 STM32CubeMX配置FSMC 测试部分 …
阅读更多...
都是免费的SSL证书，有什么区别

都是免费的SSL证书，有什么区别

国内做SSL证书的服务商还是比较多&#xff0c;但也不是所有服务商都提供免费的SSL证书&#xff0c;一般只有少数几家提供免费SSL证书。那么&#xff0c;同样都是免费的SSL证书&#xff0c;有哪些不一样的地方呢&#xff1f; 1、验证类型&#xff1a;免费SSL证书通常只提供域名…
阅读更多...
网络实验新境界，PNETLab模拟器部署指南

网络实验新境界，PNETLab模拟器部署指南

在网络工程领域&#xff0c;拥有一个可靠的网络实验平台至关重要。PNETLab模拟器是一款功能强大的网络仿真工具&#xff0c;它支持包括华为、华三、锐捷、思科在内的多种设备&#xff0c;并且以开源免费的形式提供&#xff0c;这使得它在业界备受青睐。 软件介绍 PNETLab&am…
阅读更多...
网络安全防护：抵御DDoS和CC攻击

网络安全防护：抵御DDoS和CC攻击

在当今数字化时代&#xff0c;网络安全已成为任何组织或个人不可忽视的重要议题。DDoS&#xff08;分布式拒绝服务&#xff09;攻击和CC&#xff08;命令与控制&#xff09;攻击作为两种最为常见的网络攻击方式&#xff0c;给网络运营者和用户带来了巨大的威胁和影响。本文将介…
阅读更多...
BGP练习

BGP练习

一&#xff0c;拓扑 二&#xff0c;要求 用BGP连接AS 100,200,300 三&#xff0c;配置 r1: 配置IP: [r1]interface GigabitEthernet 0/0/0 [r1-GigabitEthernet0/0/0]ip address 12.0.0.1 24 [r1]interface LoopBack 0 [r1-LoopBack0]ip address 1.1.1.1 32 [r1]interfac…
阅读更多...
爱普生推出适用于物联网小尺寸温补晶振TG1612SLN

爱普生推出适用于物联网小尺寸温补晶振TG1612SLN

爱普生推出一款小尺寸温补晶振TG1612SLN&#xff0c;之前推出的小尺寸温补晶振TG2016SLN&#xff0c;封装2016已经是很小了&#xff0c;而TG1612SLN的尺寸仅为1.6x1.2x0.45毫米&#xff0c;不得不佩服爱普生的研发能力。 温度补偿晶体振荡器TG1612SLN使用爱普生开发和制造…
阅读更多...
FebHost：注册新西兰.NZ域名考虑哪些因素？

FebHost：注册新西兰.NZ域名考虑哪些因素？

在考虑注册.nz域名时&#xff0c;需要考虑新西兰的经济规模、电子商务的普及程度和互联网用户数量。以下是一些关键因素&#xff1a; 市场潜力 虽然与大国相比&#xff0c;新西兰的经济规模可能较小&#xff0c;但它仍然为商业提供了机会&#xff0c;特别是那些针对本地市场的…
阅读更多...
消费新纪元：探索消费增值的财富之旅

消费新纪元：探索消费增值的财富之旅

你是否曾对日常消费感到一丝无奈&#xff0c;觉得钱一旦花出去就如同流水般逝去&#xff0c;再也无法追回&#xff1f;现在&#xff0c;让我为你揭示一种革命性的消费观念——消费增值&#xff0c;它不仅能满足你的物质需求&#xff0c;还能让你的资金像滚雪球般持续增长&#…
阅读更多...
一键自动化博客发布工具,用过的人都说好(csdn篇)

一键自动化博客发布工具,用过的人都说好(csdn篇)

CSDN应该是大家接触到最多的博客平台了&#xff0c;所以一款能够发布到CSDN的自动化工具还是非常有必要的。 今天给大家讲讲自动化CSDN博客发布的思路和一些问题的解决办法。 解决问题的思路一定是最重要的&#xff0c;知识是死的&#xff0c;问题是活的&#xff0c;如何在工作…
阅读更多...
【学习笔记】人群归因分数 PAF 以及combined PAF（更新）

【学习笔记】人群归因分数 PAF 以及combined PAF（更新）

在此推荐2篇发表在lancet以及jama子刊上的paf文章&#xff0c;这两篇文章套路是一样的&#xff0c;只是在不同国家进行。 在计算combined PAF或者说weighted PAF的时候&#xff0c;先建立了相关矩阵&#xff0c;再做主成分分析&#xff0c;得到communality。详细信息大家可翻阅…
阅读更多...
法国签证照片尺寸怎么调整？图片调整尺寸的方法介绍

法国签证照片尺寸怎么调整？图片调整尺寸的方法介绍

在我们的平时生活中&#xff0c;个人证件照是我们必不可少的身份证明&#xff0c;它是一种具有严格尺寸和比例要求的特殊照片&#xff0c;对于一些特定的场合&#xff0c;比如我们在申请法国签证的时候&#xff0c;需要把照片调整到规定的大小尺寸&#xff0c;那么&#xff0c;…
阅读更多...
RK3568外置RTC芯片PCF8563T（或替代型号）实验

RK3568外置RTC芯片PCF8563T（或替代型号）实验

RK3568 外接 PCF8563 RTC Chapter0 RK3568 外接 PCF8563 RTC1 menuconfig中打开pcf8563驱动2 设备树DTS3 修改驱动 Chapter1 【正点原子Linux连载】第三十一章 外置RTC芯片AT8563T实验 摘自【正点原子】ATK-DLRK3568嵌入式Linux驱动开发指南第三十一章 外置RTC芯片AT8563T实验3…
阅读更多...
GBase 8s 数据库集群切换及恢复

GBase 8s 数据库集群切换及恢复

GBase 8s 数据库切换分为自动切换、由CM控制的按FOC规则的切换、手工切换。 自动切换 全自动切换用于HAC集群中&#xff0c;由于集群只有两个节点&#xff0c;数据库相互之前进行状态检查&#xff0c;发现异常时&#xff0c;能按DRAUTO的配置方式进行自动切换。 在HAC集群中&…
阅读更多...
MyBatis（该篇足已）

MyBatis（该篇足已）

目录 一.MyBatis是什么&#xff1f; 二.为什么学习MyBatis呢&#xff1f; 三.MyBatis的学习 3.1MyBatis的开发流程 3.2MyBatis项目 四.MyBatis的增删改操作 五.参数占位符 #{} 和 ${} 六.映射返回 七.映射失败 八.数据库连接池 九.动态SQL 9.1<if>标签 9.2&…
阅读更多...
https从入门到放弃（概念+实战+上线）

https从入门到放弃（概念+实战+上线）

什么是HTTPS 大家都知道http&#xff0c;为什么现在又多了一个https呢&#xff1f;HTTP是明文传输的&#xff0c;也就意味着&#xff0c;介于发送端、接收端中间的任意节点都可以知道传输的内容是什么。这些节点可能是路由器、代理等。 举个最常见的例子&#xff0c;用户登陆…
阅读更多...
微服务领域的寻路者 —— Eureka深度探索与实战秘籍

微服务领域的寻路者 —— Eureka深度探索与实战秘籍

文章目录 一、引言定义目标一个接地气的例子引言小结 二、Eureka架构2.1 Eureka Server一个有趣的例子2.2 Eureka Client一段简单的代码示例架构小结 三、工作流程1. 服务注册2. 心跳检测3. 服务发现4. 健康检查与失效剔除工作流程小结 四、核心机制4.1 服务注册与续约4.2 服务…
阅读更多...
五、VGA 叠加图像原理和实现（十字光标）

五、VGA 叠加图像原理和实现（十字光标）

前言&#xff1a;该案例在VGA项目&#xff1a;联合精简帧双fifosobel算法 实现VGA显示项目的基础上进行改动。 要求&#xff1a;通过串口助手把 198x198 的十字光标图像二进制数据传递给 FPGA 板卡&#xff0c;FPGA 板 卡接收到后存储到 Ram 中用于 VGA 叠加显示。 预期效果展…
阅读更多...
最新文章

Copyright @ 2022~2023