数据结构·一篇搞定栈！

好久不见，超级想念
废话不多说，直接看
请添加图片描述

引言

在数据结构的大家族中，栈（Stack）是一种非常重要的线性数据结构，它的特点是后进先出（LIFO，Last In First Out）。栈在程序设计中有着广泛的应用，比如函数调用栈、浏览器的前进后退功能等。本文将详细介绍栈的基本概念、操作以及使用C语言实现栈的方法。

栈的基本概念

栈是一种只能在一端（称为栈顶，top）进行插入和删除操作的线性表。在栈中，允许插入和删除的一端称为栈顶，另一端称为栈底（bottom）。栈没有后驱结点，插入和删除运算都只能在栈顶进行。

栈的实现

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

在这里插入图片描述

// 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈

typedef int STDataType;
#define N 10
typedef struct Stack
{
 STDataType _a[N];
 int _top; // 栈顶
}Stack;

我只做部分讲解，不太难哈哈哈

#include <stdio.h>  
#include <stdlib.h>  
#include <stdbool.h>  
  
// 定义栈的数据类型  
typedef int STDataType;  
  
// 定义栈的结构体  
typedef struct Stack  
{  
    STDataType* _a;  
    int _top; // 栈顶  
    int _capacity; // 容量  
} Stack;  
  
// 初始化栈  
void StackInit(Stack* ps)  
{  
    ps->_a = NULL;  
    ps->_top = -1;  
    ps->_capacity = 0;  
}  

// 扩容栈  
void StackResize(Stack* ps, int newCapacity)  
{  
    STDataType* temp = (STDataType*)realloc(ps->_a, sizeof(STDataType) * newCapacity);  
    if (!temp)  
    {  
        exit(-1); // 内存分配失败，退出程序  
    }  
    ps->_a = temp;  
    ps->_capacity = newCapacity;  
}

在函数中，首先通过realloc函数重新分配内存，将栈的数据数组_a扩充到新的容量newCapacity。realloc函数的第一个参数是原有的数据数组_a，第二个参数是新的容量newCapacity乘以每个元素的大小。

接着，将realloc返回的新内存地址赋值给临时指针变量temp。如果realloc函数分配内存失败，temp将为NULL。在这种情况下，通过if语句检查temp是否为NULL，如果是，则调用exit(-1)函数退出程序，表示内存分配失败。

如果realloc函数成功分配了新的内存空间，将临时指针temp指向的内存地址赋值给栈结构体指针ps的数据数组_a，以此来更新栈的数据数组。

最后，将新的容量newCapacity赋值给栈结构体指针ps的_capacity，表示栈的容量已经扩充到新的值。这样，栈就成功扩容了。

// 入栈  
void StackPush(Stack* ps, STDataType data)  
{  
    if (ps->_top == ps->_capacity - 1) // 栈满，扩容  
    {  
        int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;  
        StackResize(ps, newCapacity);  
    }  
    ps->_a[++(ps->_top)] = data; // 先移动指针再赋值  
}

在函数中，首先通过条件判断检查栈是否已满。判断条件为栈顶指针_top是否等于栈的容量_capacity减去1。如果栈已满，即栈顶指针指向了最后一个位置，则需要对栈进行扩容。

在扩容的部分，首先计算新的容量newCapacity。如果栈当前容量为0（即栈为空），则新容量设为4；否则新容量设为当前容量的两倍。接着调用StackResize函数，将栈结构体指针ps和新容量newCapacity作为参数，进行栈的扩容操作。

如果栈未满，或者扩容完成后，接着执行入栈操作。将要入栈的数据data存入栈的数据数组_a中，存储位置为栈顶指针_top的下一个位置，即++(ps->_top)。这里使用了前置递增运算符，先将栈顶指针_top加1，然后再将数据data存入该位置，表示先移动指针再赋值。

通过这段代码，实现了将数据入栈的功能，并在栈满时自动扩容，保证了栈的容量能够满足存储需求。

// 出栈  
void StackPop(Stack* ps)  
{  
    if (!StackEmpty(ps)) // 栈不为空  
    {  
        ps->_top--;  
        // 如果栈中元素过少，可以考虑缩容，这里省略  
    }  
}  
  
// 获取栈顶元素  
STDataType StackTop(Stack* ps)  
{  
    if (!StackEmpty(ps))  
    {  
        return ps->_a[ps->_top];  
    }  
    return -1; // 栈为空，返回-1或其他错误标识  
}  
  
// 获取栈中有效元素个数  
int StackSize(Stack* ps)  
{  
    return ps->_top + 1;  
}  
  
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0  
int StackEmpty(Stack* ps)  
{  
    return ps->_top == -1;  
}  
  
// 销毁栈  
void StackDestroy(Stack* ps)  
{  
    free(ps->_a);  
    ps->_a = NULL;  
    ps->_top = -1;  
    ps->_capacity = 0;  
}  
  
int main()  
{  
    Stack s;  
    StackInit(&s);  
  
    // 入栈操作  
    StackPush(&s, 1);  
    StackPush(&s, 2);  
    StackPush(&s, 3);  
  
    // 获取栈顶元素  
    printf("栈顶元素为：%d\n", StackTop(&s));  
  
    // 出栈操作  
    StackPop(&s);  
    printf("出栈后，栈顶元素为：%d\n", StackTop(&s));  
  
    // 获取栈中有效元素个数  
    printf("栈中有效元素个数为：%d\n", StackSize(&s));  
  
    // 销毁栈  
    StackDestroy(&s);  
  
    return 0;  
}

在这里插入图片描述

例题

括号匹配

#define MAX_SIZE 10000

typedef struct {
    char data[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack *stack) {
    stack->top = -1;
}

bool isEmpty(Stack *stack) {
    return stack->top == -1;
}

bool isFull(Stack *stack) {
    return stack->top == MAX_SIZE - 1;
}

void push(Stack *stack, char c) {
    if (isFull(stack)) {
        printf("Stack overflow\n");
    } else {
        stack->data[++stack->top] = c;
    }
}

char pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow\n");
        return '\0';
    } else {
        return stack->data[stack->top--];
    }
}

bool isValid(char *s) {
    Stack stack;
    initStack(&stack);

    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
            push(&stack, s[i]);
        } else {
            if (isEmpty(&stack)) {
                return false;
            }
            char left = pop(&stack);
            if ((s[i] == ')' && left != '(') || (s[i] == '}' && left != '{') || (s[i] == ']' && left != '[')) {
                return false;
            }
        }
    }

    return isEmpty(&stack);
}

这段代码定义了一个基于数组的栈结构，并实现了栈的基本操作（初始化、判断是否为空、判断是否已满、压栈、弹栈），以及一个isValid函数，用于检查一个给定的字符串s中的括号是否有效。

栈的定义和操作

  1. 栈的定义：使用了一个结构体Stack，其中包含一个字符数组data（用于存储栈元素）和一个整数top（用于表示栈顶的位置）。
  2. 初始化：initStack函数将栈顶指针top初始化为-1，表示栈为空。
  3. 判断是否为空：isEmpty函数检查top是否为-1。
  4. 判断是否已满：isFull函数检查top是否等于MAX_SIZE - 1。
  5. 压栈：push函数在栈未满时将字符c压入栈中。
  6. 弹栈：pop函数在栈非空时弹出栈顶元素，并返回该元素。

isValid函数分析
isValid函数用于检查一个字符串s中的括号是否有效。它使用前面定义的栈结构，并遵循以下逻辑：

  1. 遍历字符串s中的每个字符。
  2. 如果遇到左括号（(、{ 或 [），则将其压入栈中。
  3. 如果遇到右括号（)、} 或 ]），则执行以下步骤：
    首先检查栈是否为空。如果为空，说明没有对应的左括号可以匹配，返回false。
    然后弹出栈顶元素（即最近压入的左括号），检查它是否与当前的右括号匹配。如果不匹配，返回false。
  4. 遍历完字符串后，如果栈为空，则说明所有括号都有效匹配，返回true；否则，返回false。

注意事项

  1. 代码中使用的MAX_SIZE定义了栈的最大容量，但请注意，这个值在实际使用中可能需要调整，以确保足够大以处理可能的输入字符串。
  2. pop函数在栈空时返回\0，这只是一个表示错误的标记。在实际应用中，可能还需要考虑其他错误处理机制。
  3. 字符串s只包含括号字符，没有考虑其他字符（如字母、数字或空格）。如果输入字符串包含这些字符，isValid函数可能无法正确工作。
  4. isValid函数只考虑了三种括号类型（圆括号、大括号和方括号），并且假设它们的匹配是成对出现的。如果输入字符串包含其他类型的括号或括号不成对出现，函数将无法正确工作。

那么看到这里，这篇小文章就快结束了哦
不要忘了今天是母亲节，大家不要忘了问候自己的妈妈哦，嘻嘻嘻
在这里插入图片描述
那么各位，我们下期再见咯，今天没有预告哈哈哈

在这里插入图片描述

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

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

相关文章

Star15.3k，开源数据可视化分析工具项目

Star15.3k，开源数据可视化分析工具项目

好东西来了&#xff0c;这是一个人人可用的开源数据可视化分析工具项目&#xff0c;V 哥迫不及待的要给大家推荐这个项目&#xff0c;帆软、Tableau 等商业 BI 工具的开源替代&#xff0c;已在 Github 上被 Star了15.3k了&#xff0c;大家一起来了解一下。自己搭建起来可用&…
阅读更多...
consul启动Error_server_rejoin_age_max (168h0m0s) - consider wiping your data dir

consul启动Error_server_rejoin_age_max (168h0m0s) - consider wiping your data dir

consul 启动报错&#xff1a; consul[11880]: 2024-05-12T08:37:51.095-0400 [ERROR] agent: startup error: error"refusing to rejoin cluster because server has been offline for more than the configured server_rejoin_age_max (168h0m0s) - consider wiping you…
阅读更多...
MFC桌面应用中窗口的客户区与非客户区的

MFC桌面应用中窗口的客户区与非客户区的

在MFC&#xff08;Microsoft Foundation Class&#xff09;中&#xff0c;窗口被分为客户区和非客户区。理解这两个概念对于设计和开发Windows应用程序至关重要。 客户区&#xff08;Client Area&#xff09;&#xff1a; 客户区是窗口中用于显示应用程序内容的区域。它是窗口…
阅读更多...
机器学习周报第三十八周 iTransformer

机器学习周报第三十八周 iTransformer

文章目录 week38 iTransformer摘要Abstract一、文献阅读1. 题目2. abstract3. 网络架构**转置Embedding&#xff1a;****LayerNorm&#xff08;层归一化&#xff09;****Feed-forward network&#xff08;前馈网络&#xff09;****Multivariate-Attention&#xff08;多变量注意…
阅读更多...
深度学习中的一些概念

深度学习中的一些概念

训练术语 欠拟合 欠拟合是指模型没有很好地捕获到数据特性&#xff0c;不能完整地表示数据的全部信息&#xff0c;也就是模型的复杂度低于应有的水平。例如&#xff0c;假设一个数据集实际上服从二阶多项式分布&#xff0c;但我们使用一阶线性模型去拟合它&#xff0c;这样的…
阅读更多...
WebView基础知识以及Androidx-WebKit的使用

WebView基础知识以及Androidx-WebKit的使用

文章目录 摘要WebView基础一、启动调整模式二、WebChromeClient三、WebViewClient四、WebSettings五、WebView和Native交互 Androidx-WebKit一、启动安全浏览服务二、设置代理三、安全的 WebView 和 Native 通信支持四、文件传递五、深色主题的支持六、JavaScript and WebAssem…
阅读更多...
全国药品价格目录数据库-药品价格查询

全国药品价格目录数据库-药品价格查询

药品定价是一个复杂且多维的问题&#xff0c;它涉及到医疗保健系统、政府政策、市场需求、研发成本以及药品效果等多个因素。随着中国医疗改革的不断深入&#xff0c;药品定价机制也在逐步调整和完善。本文将详细探讨我国药品定价机制&#xff0c;包括其发展历程、定价方法、影…
阅读更多...
微信小程序 17：小程序使用 npm 包和组件应用

微信小程序 17：小程序使用 npm 包和组件应用

目前&#xff0c;小程序中已经支持实用 npm 安装第三方包&#xff0c;从而提高小程序的开发效率&#xff0c;但是在小程序中使用 npm 包有三个限制&#xff1a; 不支持 Node.js内置库的包不支持依赖于浏览器内置对象的包不支持依赖于 C插件的包 Vant Weapp Vant Weapp是有赞…
阅读更多...
Verilog复习（四）| 组合逻辑

Verilog复习（四）| 组合逻辑

一位全加器结构描述&#xff1a; 数据流描述&#xff1a; 行为描述&#xff1a; 只要有事件发生&#xff08;列表中任何 信号有变化&#xff09;&#xff0c;就执行begin…end 的语句 。 always的事件控制方式 边沿触发 always (posedge clk) // clk从低电平->高&#x…
阅读更多...
io_uring的使用示例及其解释

io_uring的使用示例及其解释

io_uring的使用示例及其解释 1 io_uring机制1.1 io_uring机制1.2 io_uring系统调用接口功能介绍1.2.1 io_uring_setup()&#xff1a;1.2.2 io_uring_enter()&#xff1a;1.2.3 io_uring_register()&#xff1a; 2 liburing2.1 liburing简介2.2 liburing编译2.2.1 liburing的代码…
阅读更多...
ACM实训冲刺第五天

ACM实训冲刺第五天

第一道题 注意&#xff1a;tmp<z #include<stdio.h> int main(){int flag[26];for(int i0;i<26;i){flag[i]0;}char tmp;while(tmp!}){scanf("%c",&tmp);if(tmp}) break;if(tmp<z&&tmp>a){flag[tmp-a];}}int cnt0;for(int i0;i<26…
阅读更多...
深度学习UNet网络

深度学习UNet网络

DDPM主干模型&#xff1b; UNet是一种分类网络架构&#xff0c;输入一张图片&#xff0c;网络进行分类是目标物体还是背景像素&#xff1f; 像素级的判断。 最终输出是单通道388*388 但是输入是572&#xff0c;输入572是填充过来的 而且UNet使用的是镜像填充 镜像填充目的是…
阅读更多...
实现字符串复制（C语言）

实现字符串复制（C语言）

一、N-S流程图&#xff1b; 二、运行结果&#xff1b; 三、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>int main() {//初始化变量值&#xff1b;int i 0;char a[100], b[100];//获取字符串&#xff1b;printf("请为数组a输入字符串…
阅读更多...
SpringMVC传递参数

SpringMVC传递参数

1.RequestMapping RequestMapping本身可以处理&#xff0c;get或post,指定了get或post之后&#xff0c;就只能处理对应的请求。 RequestMapping(value{"haihiyo","goodMoring"},methodRequestMethod.POST)2.RestFul风格 RestFul是一种风格 比如:网站的访…
阅读更多...
C++--类与对象(二)

C++--类与对象(二)

类的六个成员函数 如果一个类中什么成员都没有&#xff0c;简称为空类。 空类中真的什么都没有吗&#xff1f;并不是&#xff0c;任何类在什么都不写时&#xff0c;编译器会自动生成以下6个默认成员 函数。 默认成员函数&#xff1a;用户没有显式实现&#xff0c;编译器会生…
阅读更多...
pixhawk无人机飞控解锁

pixhawk无人机飞控解锁

飞控解锁 GitBook 左手油门的遥控解锁是油门右下角拨&#xff0c;右手油门是油门最低&#xff0c;方向最右。 飞控如何加锁? 左手油门&#xff1a;油门左下角 右手油门&#xff1a;油门最低&#xff0c;方向最左 飞控解锁成功后&#xff0c;不推油门的情况下&#xff0c;…
阅读更多...
2005-2022年各省居民人均可支配收入数据（含城镇居民人均可支配收入、农村居民人均可支配收入）（无缺失）

2005-2022年各省居民人均可支配收入数据（含城镇居民人均可支配收入、农村居民人均可支配收入）（无缺失）

2005-2022年各省居民人均可支配收入数据&#xff08;含城镇居民人均可支配收入、农村居民人均可支配收入&#xff09;&#xff08;无缺失&#xff09; 1、时间&#xff1a;2005-2022年 2、来源&#xff1a;国家统计局、统计年鉴 3、指标&#xff1a;全体居民人均可支配收入、…
阅读更多...
【GlobalMapper精品教程】080：WGS84转UTM投影

【GlobalMapper精品教程】080：WGS84转UTM投影

参考阅读：ArcGIS实验教程——实验十：矢量数据投影变换 文章目录 一、加载实验数据二、设置输出坐标系三、数据导出一、加载实验数据 打开配套案例数据包中的data080.rar中的矢量数据，如下所示： 查看源坐标系：双击图层的，图层投影选项卡，数据的已有坐标系为WGS84地理坐标…
阅读更多...
WEB后端复习——Servlet

WEB后端复习——Servlet

Servlet是运行在Web服务器或应用服务器上的java程序&#xff0c;它是一个中间层&#xff0c;负责连接来自web浏览器或其他HTTP客户程序和[HTTP服务器]上应用程序 Servlet执行下面的任务: 1&#xff09;读取客户发送的显示数据。 2&#xff09;读取由浏览器发送的隐式请求数据。…
阅读更多...
（CVE-2012-1823）PHP-CGI远程代码执行漏洞（80端口）

（CVE-2012-1823）PHP-CGI远程代码执行漏洞（80端口）

&#xff08;CVE-2012-1823&#xff09;PHP-CGI远程代码执行漏洞&#xff08;80端口&#xff09; 一、介绍二、漏洞影响三、原理四、漏洞复现 一、介绍 php-cgi是一个类似于消息的“传递者”&#xff0c;它接收web容器收到的http数据包&#xff0c;并把里面的数据交给PHP解释器…
阅读更多...
最新文章

Copyright @ 2022~2023