数据结构------栈的介绍和实现

目录

1.栈的一些初步认识

2.栈的实现

3.相关的函数介绍

（1）栈的初始化

（2）栈的销毁

（3）栈的数据插入 

（6）判断是否为空

（7）栈的大小

4.栈的实现完整代码

（1）stack.h

（2）stack.c

（3）test.c

5.栈的应用--有效的括号

1.栈的一些初步认识

相信前面看过我的函数栈帧的创建和销毁这篇博客的小伙伴们对于栈已经有了一个初步的了解

因为在那个博客里面，我们提到了栈顶指针，栈底指针，压栈，出栈等等一些专业术语；

现在我们来系统的认识一下栈：

栈实际上也是一个存储数据的结构，和我们的线性表是一样的，但是栈肯定是有自己的独特之处的，否则也不会作为一个单独的数据结构存在，确实，栈的特殊性就在于我们的数据都是从栈顶进入，栈顶出去，这个就是栈的特殊之处；

栈的这个特性使得先进去的数据后出来，后进栈的数据先出来，这个有什么好处呢？我们现在可能还体会不到，我通过一个例子大家就可以体会到栈的用途，栈是有用的；

比如我们想要判断一串符号的顺序：看看是不是一一对应的，例如{（【】）}这个肯定就是一一对应的符号组合，但是对于{【（}】）这个就不是一一对应的符号，我们是用肉眼可以看出来的，但是如果有题目让我们设计程序进行判断呢？

拿这个{（【】）}作为案例，我们的{先进栈，（再进栈，【再进栈，这个时候我们的左边的括号都判断完了，我们需要判断右边的符号和左边的是不是一一对应的，这个时候就可以使用栈这个数据结构，因为我们的栈是后进先出，前面的3个符号进栈之后，我们就可以让他们依次出栈和我们后面的几个符号进行比较，例如这里的大括号第一个进栈，小括号第二个进栈，中括号第三个进栈，我们要向看看是否匹配，就只需要判断第四个的符号中括号和我们第一个出栈的符号是否匹配，这个时候栈这个数据结构就可以帮助我们判断这个一串符号前后是不是一一对应的。

2.栈的实现

我们还是写一个系统的文件，包括栈的实现的头文件，源文件和测试文件这三个文件；

我们在头文件里面进行相关函数的声明，源文件里面进行相关的函数的定义，测试文件里面定义一个栈进行我们写的函数的测试；

我们这里是定义了一些函数：栈的初始化，栈的销毁，栈里面插入数据，栈里面删除数据，返回栈顶的数据，判断栈是否是空的，栈的大小；

3.相关的函数介绍

（1）栈的初始化

这里就是把数组置空，栈顶的位置设为0，容量设置为0，这里是top指的是栈顶的位置，我们这里初始化为0，实际上指的是栈顶的下一个元素，实际情况下，栈这个时候是空的，我们应该初始化为-1，我们初始化为0方便后面的插入数据，我们插入数据就是在栈顶的下一个位置进行插入的，因此我们初始化为0可以方便后续的数据的插入；

（2）栈的销毁

就是释放掉数组的空间，栈顶位置和栈的容量都设置为0就可以了；

（3）栈的数据插入 

我们要为这个栈开辟空间，把我们要插入的数据给插入进去，再让栈顶的位置加加就行了；

（4）栈的元素删除 

这个就是不断的删除栈顶的元素，让栈顶位置元素不断的弹出，最后不断的让top--,但是这个栈的元素的个数是有限的，肯定不能一直进行top--把，我们调用这个判断是否为空的函数进行断言，因为这个函数判断的是为空的，所以我们断言的时候取非，这个时候过了再进行top--；

（5）取出栈的元素

返回值就是我们取出来的元素，还是要进行断言，因为栈里面的元素个数是有限的，我们肯定不能一直取出元素；

（6）判断是否为空

我们设置布尔值，pst->top为0时候，说明栈里面没有元素，是空的，我们就返回true,否则就返回false;

（7）栈的大小

我们还是返回pst->top表示的是栈顶的下一个位置，下表和个数是相差1的，如果是2个元素，我们的pst->top表示的是栈顶的下一个元素位置，下标是从0开始的，栈顶的下一个元素就是第三个元素，下标就是2，我们返回的就是2个元素的个数； 

4.栈的实现完整代码

（1）stack.h

#pragma once
#include<stdbool.h>
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int sldatatype;
typedef struct stack
{
	sldatatype* a;
	int top;
	int capacity;
}stack;

void stackinit(stack* pst);

void stackdestory(stack* pst);

void stackpush(stack* pst, sldatatype x);

void stackpop(stack* pst);

sldatatype stacktop(stack* pst);

bool stackempty(stack* pst);

int size(stack* pst);

（2）stack.c

#include"stack.h"

void stackinit(stack* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;//指向栈顶的下一个元素
	pst->capacity = 0;
}

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

void stackpush(stack* pst, sldatatype x)
{
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : (pst->capacity * 2);
		sldatatype* temp = (sldatatype*)realloc(pst->a, newcapacity * sizeof(sldatatype));
		if (temp == NULL)
		{
			perror("realloc fail!");
			return;
		}
		pst->a = temp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}

void stackpop(stack* pst)
{
	assert(pst);
	assert(!stackempty(pst));
	pst->top--;
}

sldatatype stacktop(stack* pst)
{
	assert(pst);
	assert(!stackempty(pst));
	return pst->a[pst->top - 1];
}

bool stackempty(stack* pst)
{
	assert(pst);
	return pst->top == 0;
}

int size(stack* pst)
{
	assert(pst);
	return pst->top;
}

（3）test.c

#include"stack.h"

void test1()
{
	stack s1;
	stackinit(&s1);
	stackpush(&s1, 1);
	stackpush(&s1, 2);
	stackpush(&s1, 3);
	stackpush(&s1, 4);
	while (!stackempty(&s1))
	{
		printf("%d ", stacktop(&s1));
		stackpop(&s1);
	}
	stackdestory(&s1);
}
int main()
{
	test1();
	return 0;
}

我们这里进行栈里面的数据打印的时候是设置了一个循环，我们每打印一个数据，就弹出栈顶位置的元素，这个时候就有一个新的数据成为栈顶，我们再打印新的栈顶位置数据 。

5.栈的应用--有效的括号

这里的应用就是我们开始提到的括号的匹配问题，我们要判断这个括号之间是否是相互匹配的；

因为现阶段我们还是使用C语言进行实现，所以我们要自己实现栈，如果是C++，我们可以使用相应的一些库，我们可以直接进行调用，这里我们就把上面实现的函数复制过来就可以了。

代码展示：

#include<stdbool.h>
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef char sldatatype;
typedef struct stack
{
	sldatatype* a;
	int top;
	int capacity;
}stack;

void stackinit(stack* pst);

void stackdestory(stack* pst);

void stackpush(stack* pst, sldatatype x);

void stackpop(stack* pst);

sldatatype stacktop(stack* pst);

bool stackempty(stack* pst);

int size(stack* pst);

void stackinit(stack* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;//指向栈顶的下一个元素
	pst->capacity = 0;
}

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

void stackpush(stack* pst, sldatatype x)
{
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : (pst->capacity * 2);
		sldatatype* temp = (sldatatype*)realloc(pst->a, newcapacity * sizeof(sldatatype));
		if (temp == NULL)
		{
			perror("realloc fail!");
			return;
		}
		pst->a = temp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}

void stackpop(stack* pst)
{
	assert(pst);
	assert(!stackempty(pst));
	pst->top--;
}

sldatatype stacktop(stack* pst)
{
	assert(pst);
	assert(!stackempty(pst));
	return pst->a[pst->top - 1];
}

bool stackempty(stack* pst)
{
	assert(pst);
	return pst->top == 0;
}

int size(stack* pst)
{
	assert(pst);
	return pst->top;
}
bool isValid(char* s) 
{
    stack s1;
    stackinit(&s1);
    while(*s)
    {
        if(*s=='('||*s=='['||*s=='{')
        {
            stackpush(&s1,*s);
        }
        else
        {
            if(stackempty(&s1))
            {
                stackdestory(&s1);
                return false;
            }
            char top=stacktop(&s1);
            stackpop(&s1);
            if(*s==']'&&top!='['||*s=='}'&&top!='{'||*s==')'&&top!='(')
            {
                stackdestory(&s1);
                return false;
            }
            else
            {

            }
        }
        ++s;
    }
    bool ret=stackempty(&s1);
    stackdestory(&s1);


    return ret;
}

（1）这个代码看上去比较复杂，实际上前面的很多都是在自己实现一个栈，只有inValid才是真正的一个接口函数，其他的都是为这个函数服务的，我们的inValid函数调用其他的函数进行相应的判断；

（2）因为我们这里是对符号进行判断，所以我们的头文件里面的int需要修改为char类型数据，这个时候我们的typedef int sldatatype的作用就显示了出来。

 

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

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

相关文章

C语言例题31：在屏幕上显示一个菱形

C语言例题31：在屏幕上显示一个菱形

题目要求&#xff1a;在屏幕上显示一个菱形 #include <stdio.h>void main() {int i, j;int x;printf("输入菱形行数(3以上的奇数&#xff09;&#xff1a;");scanf("%d", &x);//显示菱形上面的大三角形for (i 1; i < (x 1) / 2; i) {for (…
阅读更多...
【R语言数据分析】相关性分析：pearson与spearman

【R语言数据分析】相关性分析：pearson与spearman

相关性分析是探寻两个变量之间关联关系的分析方法&#xff0c;注意相关性分析仅仅针对连续型变量和有序分类变量&#xff0c;对于无需分类变量就不存在相关性分析了&#xff0c;而是通过差异分析来间接反映相关性。比如性别和身高的关系就无法做相关性分析&#xff0c;虽然我们…
阅读更多...
RHCE shell-第一次作业

RHCE shell-第一次作业

要求&#xff1a; 1、判断当前磁盘剩余空间是否有20G&#xff0c;如果小于20G&#xff0c;则将报警邮件发送给管理员&#xff0c;每天检査- 次磁盘剩余空间。 2、判断web服务是否运行(1、查看进程的方式判断该程序是否运行&#xff0c;2、通过查看端口的方式 判断该程序是否运…
阅读更多...
动态规划——最短编辑距离

动态规划——最短编辑距离

一、问题描述 最短编辑距离(Minimum Edit Distance)&#xff0c;也被称为Levenshtein距离&#xff0c;是一种计算两个字符串间的差异程度的字符串度量(string metric)。我们可以认为Levenshtein距离就是从一个字符串修改到另一个字符串时&#xff0c;其中编辑单个字符&#xff…
阅读更多...
从零开始学AI绘画，万字Stable Diffusion终极教程（二）

从零开始学AI绘画，万字Stable Diffusion终极教程（二）

【第2期】关键词 欢迎来到SD的终极教程&#xff0c;这是我们的第二节课 这套课程分为六节课&#xff0c;会系统性的介绍sd的全部功能&#xff0c;让你打下坚实牢靠的基础 1.SD入门 2.关键词 3.Lora模型 4.图生图 5.controlnet 6.知识补充 在第一节课里面&#xff0c;我们…
阅读更多...
CPP#类与对象4

CPP#类与对象4

友元 关键字&#xff1a;friend 友元的实现&#xff1a;全局函数做友元&#xff1b; 类做友元&#xff1b; 成员函数做友元。 .1全局函数做友元 class Point { private:double x, y; public:Point(double xx, double yy); friend int Distance(Point &a, Point &b)…
阅读更多...
关于win平台c语言引入开源库的问题与解决

关于win平台c语言引入开源库的问题与解决

许久不写博客&#xff0c;五一还在加班&#xff0c;就浅浅写一篇吧 最近除了做物联网平台 还对网关二次开发程序做了修改&#xff0c;网关的二次开发去年年底的时候做过&#xff0c;但是当时的逻辑不是十分完善&#xff0c;差不多已经过了半年了&#xff0c;很多细节已经忘记了…
阅读更多...
探索APP托管服务分发平台的魅力 - 小猪APP分发平台(APP托管)

探索APP托管服务分发平台的魅力 - 小猪APP分发平台(APP托管)

什么是APP托管服务分发平台 APP托管服务分发平台是一个集成了代码托管、构建集成、测试、发布和监控等全面性服务的平台。让开发者可以专注于创作探索APP托管服务分发平台的魅力 - 小猪APP分发平台&#xff0c;而不必花费太多精力在app的维护和分发上。 为什么要选择APP托管服…
阅读更多...
D3CTF2024

D3CTF2024

文章目录 前言notewrite_flag_where【复现】D3BabyEscapePwnShell 前言 本次比赛笔者就做出两道简单题&#xff0c;但队里师傅太快了&#xff0c;所以也没我啥事。然后 WebPwn 那题命令行通了&#xff0c;但是浏览器不会调试&#xff0c;然后就简单记录一下。 note 只开了 N…
阅读更多...
绘图神器===draw.io

绘图神器===draw.io

文章目录 前言打开看看版本总结 前言 看到一个好玩的神器&#xff0c;Draw.io 看到一个网页draw.io&#xff0c;打开一看&#xff0c;还不错&#xff0c;是一款网页端的绘图平台。支持各种各样的绘制需求&#xff0c;像类图&#xff0c;流程图&#xff0c;泳道图&#xff0c;…
阅读更多...
OpenCV如何模板匹配(59)

OpenCV如何模板匹配(59)

返回:OpenCV系列文章目录&#xff08;持续更新中......&#xff09; 上一篇&#xff1a;OpenCV如何实现背投(58) 下一篇 &#xff1a;OpenCV在图像中寻找轮廓(60) 目标 在本教程中&#xff0c;您将学习如何&#xff1a; 使用 OpenCV 函数 matchTemplate()搜索图像贴片和输入…
阅读更多...
李沐-46 语义分割和数据集【动手学深度学习v2】

李沐-46 语义分割和数据集【动手学深度学习v2】

在语义分割中&#xff0c;不是一张图片分配一个label&#xff0c;而是为图片的每一个像素点分配一个label。假设我们输入的是RGB三通道的图片&#xff0c;即每个像素点颜色可以表示为(x, y, z)&#xff0c;那么为了给像素点打上label&#xff0c;我们需要构建一个映射关系&…
阅读更多...
这是一个简单的照明材料网站，后续还会更新

这是一个简单的照明材料网站，后续还会更新

1、首页效果图 代码 <!DOCTYPE html> <html><head><meta charset"utf-8" /><title>爱德照明网站首页</title><style>/*外部样式*/charset "utf-8";*{margin: 0;padding: 0;box-sizing: border-box;}a{text-dec…
阅读更多...
24.哀家要长脑子了！

24.哀家要长脑子了！

目录 1.594. 最长和谐子序列 - 力扣&#xff08;LeetCode&#xff09; 2.350. 两个数组的交集 II - 力扣&#xff08;LeetCode&#xff09; 3.554. 砖墙 - 力扣&#xff08;LeetCode&#xff09; 4.9. 回文数 - 力扣&#xff08;LeetCode&#xff09; 5.13. 罗马数字转整数 …
阅读更多...
使用D3.js进行数据可视化

使用D3.js进行数据可视化

D3.js介绍 D3.js是一个流行的JavaScript数据可视化库&#xff0c;全称为Data-Driven Documents&#xff0c;即数据驱动文档。它以数据为核心&#xff0c;通过数据来驱动文档的展示和操作。D3.js提供了丰富的API和工具&#xff0c;使得开发者能够创建出各种交互式和动态的数据可…
阅读更多...
Linux服务器常用命令总结

Linux服务器常用命令总结

view查找日志关键词 注意日志级别&#xff0c;回车后等一会儿&#xff0c;因为文件可能比较大加载完需要时间 当内容显示出来后&#xff0c;使用“/关键词”搜索 回车就能搜到&#xff0c;n表示查找下一个&#xff0c;N表示查找上一个 find 查找 find Family -name book …
阅读更多...
华为平板手机如何清理应用市场的存储空间

华为平板手机如何清理应用市场的存储空间

如何清理应用市场的存储空间 适用产品&#xff1a; 手机&#xff0c;平板 适用版本&#xff1a;不涉及系统版本 如果您的应用市场显示应用的数据较大&#xff0c;可能是下载的安装包没有安装成功&#xff0c;导致安装包未自动删除。&#xff08;可参考&#xff1a;应用市场下…
阅读更多...
Delta lake with Java--将数据保存到Minio

Delta lake with Java--将数据保存到Minio

今天看了之前发的文章&#xff0c;居然有1条评论&#xff0c;看到我写的东西还是有点用。 今天要解决的问题是如何将 Delta产生的数据保存到Minio里面。 1、安装Minio&#xff0c;去官网下载最新版本的Minio&#xff0c;进入下载目录&#xff0c;运行如下命令&#xff0c;曾经…
阅读更多...
2024年第11届生物信息学研究与应用国际会议（ICBRA 2024）即将召开！

2024年第11届生物信息学研究与应用国际会议（ICBRA 2024）即将召开！

2024年第11届生物信息学研究与应用国际会议&#xff08;ICBRA 2024&#xff09;将于2024年9月13-15日在意大利米兰举行。生物信息学&#xff0c;作为连接生物学与信息技术的桥梁&#xff0c;正日益成为探索生命奥秘、推动生命科学发展的重要力量。ICBRA 2024的召开&#xff0c;…
阅读更多...
使用PyTorch从头实现Transformer

使用PyTorch从头实现Transformer

前言 本文使用Pytorch从头实现Transformer&#xff0c;原论文Attention is all you need paper&#xff0c;最佳解读博客&#xff0c;学习视频GitHub项目地址Some-Paper-CN。本项目是译者在学习长时间序列预测、CV、NLP和机器学习过程中精读的一些论文&#xff0c;并对其进行了…
阅读更多...
最新文章

Copyright @ 2022~2023