【数据结构】栈

1.58.33

栈

  • 栈
    • 栈的概念及基本结构
    • 栈的存储
    • 栈的基本操作
      • 栈的置空初始化---StackInit()
      • 栈的初始化2.0---给栈开辟一点空间StackInit1()
      • 栈的销毁---StackDestory()
      • 入栈----StackPush()
      • 出栈----StackPop()
      • 获取栈中元素的数量---StackSize()
      • 判断栈是否为空---StackEmpty()
      • 获取栈顶元素---StackTop
      • 栈元素的遍历
    • 程序的运行
      • 头文件---stack.h
      • 源文件编写函数---stack.c
      • 源文件编写--在主函数中运行 test.c
      • 运行结果
  • 栈的应用---括号的匹配
    • 题目---Leetcode20.有效的括号
    • 举例认识---有效的括号
    • 找出规律

栈

栈的概念及基本结构

栈： 栈式一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除的一端称为栈顶，另一端称为栈底。栈中的数据元素遵循后进先出的原则。
压栈： 栈的插入操作叫做进栈/压栈/入栈，插入数据在栈顶。
出栈： 栈的删除操作叫出栈。出栈元素在栈顶。

栈的存储

栈的存储方式有两种：顺序栈和链栈，即栈的顺序存储和链式存储。

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的元素，同时附设一个指针（top）指示当前栈顶的位置。

对于栈数据结构，采用顺序栈更方便进行压栈尤其是出栈，所以本次主要说明利用顺序栈来实现栈的基本操作。

同时这里，利用一组地址连续的存储单元进行存放，同顺序表的存储一样，分为静态存储和动态存储。

在静态存储中，即利用宏定义给定一个顺序表的大小，对于后续操作，尤其是入栈，如果入若干次栈，而由于顺序表的内存空间有限，那么就会直接报错而无法进行后续操作。

在动态存储中，就比较灵活了，正好可以解决这个问题。在动态存储中，我们利用定义的指针在堆上开辟一块内存空间，若空间大小不够，我们可以进行扩容操作。但同时我们动态存储时，也要注意，在栈操作最后要注意堆上内存空间的释放。

typedef int datatype;
typedef struct Stack
{
    datatype *a;
    int top;
    int capacity;
}Stack;

可以形象地来理解以下：

栈的基本操作

栈的置空初始化—StackInit()

void StackInit(Stack *ps)
{
    assert(ps);
    ps->a=NULL;
    ps->top=0;
    ps->capacity=0;
}

这里用到了assert函数，下面几乎每个函数也都会用到。在这里简单说明一下这个函数。
assert函数即断言函数，“断言”在语文中的意思是“断定”、“十分肯定地说”，在编程中是指对某种假设条件进行检测，如果条件成立就不进行任何操作，如果条件不成立就捕捉到这种错误，并打印出错误信息，终止程序执行。
所在头文件：<assert.h>
函数原型：void assert (int expression);
参数：expression即要检测的表达式
返回值：无返回值
如果expression的结果为 0（条件不成立），那么断言失败，表明程序出错，assert() 会向标准输出设备（一般是显示器）打印一条错误信息，并调用 abort() 函数终止程序的执行。
assert()函数相比于return ，更加直接‘暴力“，如果条件不成立，那么程序就将终止。
如果expression的结果为非 0（条件成立），那么断言成功，表明程序正确，assert() 不进行任何操作。

在这里，我们对传入的指针进行断言，如果为空指针，那么程序终止退出程序，若不为空指针，那么不进行任何的操作，程序继续往下执行。

栈的初始化2.0—给栈开辟一点空间StackInit1()

void StackInit1(Stack *ps)
{
    assert(ps);
    ps->a=(datatype *)malloc(sizeof(Stack)*4);//开辟4个空间
    ps->capacity=4;
}

栈的销毁—StackDestory()

因为malloc函数是在堆上开辟的内存空间，而对于堆上的内存空间比较灵活，系统不会自动释放，而需要我们手动释放，所以在一个函数中既然开辟了栈，那就一定要记得最后销毁。

void StackDestory()
{
    assert(ps);
    free(p->a);
    ps->a=NULL;
    ps->top=ps->capacity=0;
}

入栈----StackPush()

void StackPush(Stack *ps,datatype x)
{
    assert(ps);
    //判断栈的空间是否已满
    if(ps->top==ps->capacity)
    {
         //扩容为原容量的2倍
        datatype *tmp=(datatype *)relloc(ps->a,sizeof(Stack)*capacity*2);
        ps->capacity=ps->capacity*2;
    }
    ps->a[ps->top]=x;
    ps->top++;
}

出栈----StackPop()

void StackPop(Stack *ps)
{
    assert(ps);
    //判断当前栈是否为空，若空则无法出栈，退出程序
    assert(ps->top >0);
    
    ps->top--;
}

获取栈中元素的数量—StackSize()

int StackSize(Stack *ps)
{
    assert(ps);
    return ps->top;
}

判断栈是否为空—StackEmpty()

bool StackEmpty()
{
    assert(ps);
    
    //若ps->top==0,为真，则返回True；若ps->top！=0，为假，则返回False
    return ps->top == 0;
}

获取栈顶元素—StackTop

datatype StackTop(Stack *ps)
{
    assert(ps);
    //判断栈是否为空
    assert(ps->top>0);
    return ps->a[ps->top - 1];    
}

栈元素的遍历

栈结构的特点是，后进先出，即后进的元素先进行遍历。所以我们就需要出栈，也就是逐渐删除栈顶元素进行遍历。
首先，我们先在测试函数中创立一个栈：

void TestStack()
{
    Stack s;
    StackInit(&s);
    StackInit1(&s);
    StackPush(&s,1);
    StackPush(&s,2);
    StackPush(&s,3);
    StackPush(&s,4);
    StackPush(&s,4);
    StackDestory(&s);
}

然后，我们一次删除栈顶元素，进行栈的遍历：

void TestStack()
{
    Stack s;
    StackInit(&s);
    StackInit1(&s);
    StackPush(&s,1);
    StackPush(&s,2);
    StackPush(&s,3);
    StackPush(&s,4);
    StackPush(&s,4);
    while(ps->top)
    {
        printf("%d",StackTop(&s));
        StackPop();
    }
    printf("\n");
    StackDestory(&s);
}

程序的运行

头文件—stack.h

#pragma once
#define _CER_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>   //malloc函数
#include <assert.h>    //assert函数
#include <stdbool.h>   //bool类型

typedef int datatype;
typedef struct Stack
{
    datatype* a;
    int top;
    int capacity;
}Stack;

void StackInit(Stack* ps); //置空
void StackInit1(Stack* ps);  //初始化
void StackDestory(Stack* ps);   //销毁
void StackPush(Stack* ps, datatype x); //入栈
void StackPop(Stack* ps);//出栈
int StackSize(Stack* ps); //获取栈中元素的多少
bool StackEmpty(Stack* ps); //判断是否栈空
datatype StackTop(Stack* ps);//获取栈顶元素

源文件编写函数—stack.c

#include "stack.h"

//栈置空
void StackInit(Stack* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->top = 0;
    ps->capacity = 0;
}

//栈初始化
void StackInit1(Stack* ps)
{
    assert(ps);
    ps->a = (datatype*)malloc(sizeof(Stack) * 4);//开辟4个空间
    ps->capacity = 4;
}

//栈的销毁
void StackDestory(Stack *ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}

//入栈
void StackPush(Stack* ps, datatype x)
{
    assert(ps);
    //判断栈的空间是否已满
    if (ps->top == ps->capacity)
    {
        //扩容为原容量的2倍
        datatype* tmp = (datatype*)realloc(ps->a, sizeof(Stack) * ps->capacity * 2);
        ps->capacity = ps->capacity * 2;
    }
    ps->a[ps->top] = x;
    ps->top++;
}

//出栈
void StackPop(Stack* ps)
{
    assert(ps);
    //判断当前栈是否为空，若空则无法出栈，退出程序
    assert(ps->top > 0);

    ps->top--;
}

//获取栈中元素的数量
int StackSize(Stack* ps)
{
    assert(ps);
    return ps->top;
}

//判断栈是否为空
bool StackEmpty(Stack *ps)
{
    assert(ps);

    //若ps->top==0,为真，则返回True；若ps->top！=0，为假，则返回False
    return ps->top == 0;
}

//获取栈顶元素
datatype StackTop(Stack* ps)
{
    assert(ps);
    //判断栈是否为空
    assert(ps->top > 0);
    return ps->a[ps->top - 1];
}

源文件编写–在主函数中运行 test.c


#include "stack.h"
//测试函数的编写---栈元素的遍历
void TestStack()
{
    Stack s;
    StackInit(&s);
    StackInit1(&s);
    StackPush(&s, 1);
    StackPush(&s, 2);
    StackPush(&s, 3);
    StackPush(&s, 4);
    StackPush(&s, 5);
    while (( & s)->top)
    {
        printf("%d", StackTop(&s));
        StackPop(&s);
    }
    printf("\n");
    StackDestory(&s);
}
//主函数
int main()
{
    TestStack();
    return 0;
}

运行结果

栈的应用—括号的匹配

题目—Leetcode20.有效的括号



举例认识—有效的括号

以下面这个例子为例：

我们自左往右进行扫描字符串：
一旦所扫描的是左括号，我们先自动略过，等待匹配
一旦出现右括号，我们会和离它最近的并且未被匹配的左括号进行匹配。如果匹配完成，我们就不需要再考虑这个左括号了。
扫描过程如下：

找出规律

我们会发现先出现的左括号后匹配
因此，进行模式识别，先进后出 ，运用栈结构。
所以，我们可以把左括号加入栈，匹配的过程就是出栈的过程。

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

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

相关文章

Kali Linux：网络与安全专家的终极武器

Kali Linux：网络与安全专家的终极武器

文章目录 一、Kali Linux 简介二、Kali Linux 的优势三、使用 Kali Linux 进行安全任务推荐阅读 ——《Kali Linux高级渗透测试》适读人群内容简介作者简介目录 Kali Linux&#xff1a;网络与安全专家的终极武器 Kali Linux&#xff0c;对于许多网络和安全专业人士来说&#x…
阅读更多...
Windows 的 WSL 中运行 EasyConnect

Windows 的 WSL 中运行 EasyConnect

Windows 的 WSL 中运行 EasyConnect docker-easyconnect 安装 Docker Desktop 通过 Docker 的官网 Docker Desktop 下载并安装. 安装过程一直下一步即可, 默认推荐 WSL 模式 初始化过程需要梯子 安装完后在搜索框搜索 docker-easyconnect hagb/docker-easyconnect 就是需要…
阅读更多...
在线ws/wss调试工具

在线ws/wss调试工具

具体前往&#xff1a;在线webSocket(ws)调试工具
阅读更多...
nacos网关

nacos网关

目录 拉取docker镜像 环境配置 网关搭建架构 wemedia-gateway网关配置 依赖 启动类配置 网关yml配置 nacos配置中心配置网关 wdmedia服务配置 依赖 启动类配置 yml配置 nacos配置 nacos中的配置共享 nacos配置 wmedia模块中yml的配置 参考:https://blog.csdn.net/…
阅读更多...
真心建议看看这个盈亏平衡点计算方法及要点解析！

真心建议看看这个盈亏平衡点计算方法及要点解析！

说实话&#xff0c;进行产品动态盈亏平衡计算是非常考验人的&#xff0c;因为不是人人都具备评估不同产品组合的盈利能力和掌握风险的方法。 当然最简单的方式就是套用诸如单产品动态盈亏平衡表之类的现成模板进行测算&#xff0c;可以实现以下三点基本需求&#xff1a; 弹性输…
阅读更多...
Linux进程——system函数、popen函数

Linux进程——system函数、popen函数

system函数&#xff08;执行shell 命令&#xff09; 头文件 #include <stdlib.h> 函数定义 int system(const char * string); 函数说明 system()会调用fork()产生子进程&#xff0c;由子进程来调用/bin/sh-c string来执行参数string字符串所代表的命令&#xff0c;…
阅读更多...
腾讯微服务平台TSF学习笔记（一）--如何使用TSF的Sidecar过滤器实现mesh应用的故障注入

腾讯微服务平台TSF学习笔记（一）--如何使用TSF的Sidecar过滤器实现mesh应用的故障注入

Mesh应用的故障注入 故障注入前世今生Envoy设置故障注入-延迟类型设置故障注入-延迟类型并带有自定义状态码总结 故障注入前世今生 故障注入是一种系统测试方法&#xff0c;通过引入故障来找到系统的bug&#xff0c;验证系统的稳健性。istio支持延迟故障注入和异常故障注入。 …
阅读更多...
微信第三方平台开发重点概念流程梳理

微信第三方平台开发重点概念流程梳理

标题 微信开发的亿点点概念第三方平台代开发流程亿些概念开发流程 代公众号使用JS SDK一些概念具体流程引用 微信开发的亿点点概念 AppID&#xff1a;AppID是不同类型的产品的账号ID,是账号的唯一标识符。例如公众号的AppID、小程序的AppID、开放平台的AppID、第三方平台的App…
阅读更多...
图像分类(五) 全面解读复现ResNet

图像分类(五) 全面解读复现ResNet

解读 Abstract—摘要 翻译 更深的神经网络往往更难以训练&#xff0c;我们在此提出一个残差学习的框架&#xff0c;以减轻网络的训练负担&#xff0c;这是个比以往的网络要深的多的网络。我们明确地将层作为输入学习残差函数&#xff0c;而不是学习未知的函数。我们提供了非…
阅读更多...
项目出错汇总

项目出错汇总

java: 错误: 无效的源发行版&#xff1a;15 java: 无效的目标发行版: 17 四步加上这个,改一下
阅读更多...
MAYA走线玩

MAYA走线玩

阅读更多...
ADS村田电感.mod（spice netlist文件）和.s2p模型导入与区别

ADS村田电感.mod（spice netlist文件）和.s2p模型导入与区别

ADS村田电感.mod&#xff08;spice netlist文件&#xff09;和.s2p模型导入与区别 简介环境过程s2pspice netlist&#xff08;.mod文件&#xff09;导入和结果对比 简介 记录了ADS村田电感.mod&#xff08;spice netlist文件&#xff09;和.s2p模型导入与区别 环境 ADS2020 …
阅读更多...
Springboot框架中使用 Redis + Lua 脚本进行限流功能

Springboot框架中使用 Redis + Lua 脚本进行限流功能

Springboot框架中使用 Redis Lua 脚本进行限流功能 限流是一种用于控制系统资源利用率或确保服务质量的策略。在Web应用中&#xff0c;限流通常用于控制接口请求的频率&#xff0c;防止过多的请求导致系统负载过大或者防止恶意攻击。 什么是限流&#xff1f; 限流是一种通过…
阅读更多...
【【SOC设计之 数据回路从 DMA到 FIFO再到BRAM 再到FIFO 再写回DMA】】

【【SOC设计之 数据回路从 DMA到 FIFO再到BRAM 再到FIFO 再写回DMA】】

SOC设计之 数据回路从 DMA到 FIFO再到BRAM 再到FIFO 再写回DMA 基本没问题的回路设计 从 DMA出发将数据传递到 FIFO 再 写到 自定义的 RTL文件中 再写到 BRAM 再到 自定义的RTL文件 再到 FIFO 再写回DMA block design 的 设计连接 可以参考我上一个文件的设计 下面介绍两个c…
阅读更多...
gd32关于IO引脚配置的一些问题

gd32关于IO引脚配置的一些问题

一、gd32f103的PA15问题 1、 #define GPIO_SWJ_NONJTRST_REMAP ((uint32_t)0x00300100U) /*!< full SWJ(JTAG-DP SW-DP),but without NJTRST */ #define GPIO_SWJ_SWDPENABLE_REMAP ((uint32_t)0x00300200U) /*!< JTAG-DP disabled and SW-DP enab…
阅读更多...
参数值为列表，不懂代码如何参数化？

参数值为列表，不懂代码如何参数化？

最近在我的教学过程中&#xff0c;我的一个学生问了我一个问题&#xff0c;他们公司的一个接口参数值是列表&#xff0c;列表中值的数量有多有少&#xff0c;问我在 jmeter 中如何让这个参数的值进行参数化&#xff1f; 如果你想学习自动化测试&#xff0c;我这边给你推荐一套视…
阅读更多...
IIC 通信协议之stm32 驱动OLED

IIC 通信协议之stm32 驱动OLED

前言 使用stm32 驱动4 Pin 的OLED&#xff0c; 现在网上开源的资料多的是&#xff0c;但是为了锻炼自己使用第一手资料的能力&#xff0c;今天我还是从数据手册开始&#xff0c;从头造一波轮子&#xff0c;同时也是为了加深自己对 IIC 协议的理解 &#xff0c;本系列内容我会从…
阅读更多...
【Spring总结】注解开发

【Spring总结】注解开发

本篇讲的内容主要是基于Spring v2.5的注解来完成bean的定义 之前都是使用纯配置的方式来定义的bean 文章目录 前言1. Spring v2.5 注解开发定义bean第一步&#xff1a;在需要定义的类上写上注解Component第二步&#xff1a;在Spring Config中定义扫描包第三步&#xff1a;主方法…
阅读更多...
关于链表的几道算法题

关于链表的几道算法题

1.删除链表的倒数第n个节点 力扣https://leetcode.cn/submissions/detail/482739445/ /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(…
阅读更多...
第八部分：JSP

第八部分：JSP

目录 JSP概述 8.1&#xff1a;什么是JSP&#xff0c;它有什么作用&#xff1f; 8.2&#xff1a;JSP的本质是什么&#xff1f; 8.3&#xff1a;JSP的三种语法 8.3.1&#xff1a;jsp头部的page指令 8.3.2&#xff1a;jsp中的常用脚本 ①声明脚本&#xff08;极少使用&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023