程序员经验分享-hwhale

【数据结构】栈

2023-11-11

1.栈的概念及结构

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

在这里插入图片描述

2.栈的实现

2.1栈的实现思路

栈的实现可以用数组或者链表实现，栈的实现使用数组更优一些，因为数组的在尾上的插入删除代价比较小。（压栈出栈）如果说一定要用链表（节省空间），可以将栈顶元素放置在带哨兵卫头结点的后面，栈底元素放在尾处，这样利于出栈。

2.2概念理解题

若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（C）
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1

A.入栈1，出栈1，入栈2,3,4,出栈4,3,2
B.入栈1,2,出栈2,入栈3，出栈3，入栈4，出栈4，最后出栈1
D.入栈1,2,3,出栈3，入栈4，出栈4，最后接连出栈2,1

2.3栈的结构体定义

//静态
//#define N 100
//typedef int STDataType;
//struct Stack
//{
//	STDataType a[N];
//	int top;//栈顶元素的位置
//};

//动态
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//记录栈顶元素的位置
	int capacity;//栈容量，用于栈的扩容
}ST;

2.4函数接口（功能）

void StackInit(ST* ps);//栈的初始化
void StackDestroy(ST* ps);//栈的销毁
void StackPush(ST* ps, STDataType x);//压栈
void StackPop(ST* ps);//出栈栈顶元素
STDataType StackTop(ST* ps);//获取栈顶元素
bool StackEmpty(ST* ps);//判断栈是否为空，用于出栈前的判断，若栈为空，则断言报错
int StackSize(ST* ps);//统计栈的元素个数

2.5头文件Stack.h

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

//静态
//#define N 100
//typedef int STDataType;
//struct Stack
//{
//	STDataType a[N];
//	int top;//栈顶元素的位置
//};

//动态
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//记录栈顶元素的位置
	int capacity;//栈容量，用于栈的扩容
}ST;

//函数接口
void StackInit(ST* ps);//栈的初始化

void StackDestroy(ST* ps);//栈的销毁

void StackPush(ST* ps, STDataType x);//压栈

void StackPop(ST* ps);//出栈栈顶元素

STDataType StackTop(ST* ps);//获取栈顶元素

bool StackEmpty(ST* ps);//判断栈是否为空，用于出栈前的判断，若栈为空，则断言报错

int StackSize(ST* ps);//统计栈的元素个数

2.6函数实现Stack.c

在这里插入图片描述

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void StackInit(ST* ps)//栈的初始化
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;//这里设定了top一开始的位置是0，即top是栈顶元素的下一个位置。
}
void StackPush(ST* ps, STDataType x)//压栈
{
	assert(ps);
	//扩容
	if(ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;//容量改变

	}
	ps->a[ps->top] = x;
	ps->top++;//压栈一个元素，栈顶元素的位置改变1
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;//top最开始的下标定在0，而不是-1(有两种情况)
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;//栈顶元素位置--
}
STDataType StackTop(ST* ps)
{
	assert(ps);
	return ps->a[ps->top - 1];
}
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;//top即栈顶元素位置，等于栈中元素个数
}
void StackDestroy(ST* ps)//栈的销毁
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

2.7测试函数Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void TestStack()
{
	ST st;//建立一个栈
	//初始化栈
	StackInit(&st);
	//压栈
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	printf("%d ", StackTop(&st));//3
	StackPop(&st);
	printf("%d ", StackTop(&st));//2
	StackPop(&st);

	
	StackPush(&st, 4);
	StackPush(&st, 5);
	//若栈不为空，则打印栈顶元素
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));//5 4 1
		StackPop(&st);//出栈栈顶元素
	}
	StackDestroy(&st);//一定要销毁栈，不然会造成内存泄漏

}
int main()
{
	TestStack();
	return 0;
}

2.8有效的括号（利用栈实现）

在这里插入图片描述
OJ链接：有效的括号

解题思路：
由于本题没有提供C语言的栈，所以我们得先自己写个数据结构栈（C语言）。
1.遇到左括号，则压入栈中
2.遇到右括号，则取栈顶元素–一种类型的左括号（StackTop），看其是否能匹配
3.当循环结束，栈为空，则说明左括号和右括号的数量匹配（因为在取到右括号时，会获取到栈顶元素，即左括号，随之出栈栈顶元素）。
4.最后记得销毁栈，不然会导致内存泄漏

typedef char STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//记录栈顶元素的位置
	int capacity;//栈容量，用于栈的扩容
}ST;

//函数接口
void StackInit(ST* ps);//栈的初始化

void StackDestroy(ST* ps);//栈的销毁

void StackPush(ST* ps, STDataType x);//压栈

void StackPop(ST* ps);//出栈栈顶元素

STDataType StackTop(ST* ps);//获取栈顶元素

bool StackEmpty(ST* ps);//判断栈是否为空，用于出栈前的判断，若栈为空，则断言报错

int StackSize(ST* ps);//统计栈的元素个数

void StackInit(ST* ps)//栈的初始化
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;//这里设定了top一开始的位置是0，即top是栈顶元素的下一个位置。
    ps->capacity=0;
}
void StackPush(ST* ps, STDataType x)//压栈
{
	assert(ps);
	//扩容
	if(ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;//容量改变

	}
	ps->a[ps->top] = x;
	ps->top++;//压栈一个元素，栈顶元素的位置改变1
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;//top最开始的下标定在0，而不是-1(有两种情况)
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;//栈顶元素位置--
}
STDataType StackTop(ST* ps)
{
	assert(ps);
	return ps->a[ps->top - 1];
}
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;//top即栈顶元素位置，等于栈中元素个数
}
void StackDestroy(ST* ps)//栈的销毁
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
bool isValid(char * s)
{
    //1.首先建立一个栈
    ST st;
    //2.初始化栈
    StackInit(&st);
    //匹配
    while(*s)
    {
        
        if(*s=='{'||*s=='('||*s=='[')//是左括号则压入栈中
        {
            StackPush(&st,*s);
        }
        else
        {
            //当左括号的数量少于右括号时，如'}'
            if(StackEmpty(&st))
            {
                StackDestroy(&st);
                return false;
            }
            char  top=StackTop(&st);//获取栈顶元素，即左括号
            StackPop(&st);//及时出栈栈顶元素
            if((*s==')'&&top!='(')||
               (*s=='}'&&top!='{')||
               (*s==']'&&top!='['))
               {
                   StackDestroy(&st);
                   return false;
               }
        }
        s++;
    }
    bool flag=StackEmpty(&st);
    StackDestroy(&st);
    return flag;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

CC 数据结构与算法

数据结构

链表

【数据结构】栈 的相关文章

  • cmake can not determine linker.....

    目录结构如下 a hpp CMakeLists txt 内容如下 add library a a hpp 编译该目录 报上面的错误 cmake实际需要有 cpp的文件才能单独编译 只有hpp不行 但是如果加上链接库也是可以的 上面的内容加上

  • 嵌入式软件开发

随机推荐

  • vue element checkbox多选框 多组联动数据嵌套多选、单选实际应用

    先看我最近项目中要实现的功能 点击 干部管理组 员工管理组 与下属员工复选框实现联动 后台返回的数据结构大概是这样的 title 干部 rows id 1 name 张三 id 2 name 张四 title 员工 rows id 3 na

  • bean的生命周期分析（三）

    目录 二 全流程梳理 2 6 创建bean 2 6 1 createBean 2 6 2 resolveBeanClass 2 6 3 prepareMethodOverrides 2 6 4 resolveBeforeInstantiat

  • 【闲谈】对于华为提出的“端云协同”渲染模式的一些看法

    本帖的主要内容 是发表一些对于华为 端云协同 的顾虑 端云协同是好事 我们本地算力可以云化 本地近乎走瘦终端路线 但这就会引发问题 这将大大增加运营商的网络传输流量业务 所以宽带套餐应该会又有变革 那不得不说一些现实点的状况 一 家用宽带可

  • sqli-labs:less-28(过滤了union和select）

    div div

  • C++——#ifndef和#ifdef宏定义的使用及作用介绍

    建议结合以下博客理解 头文件重复引用 https blog csdn net shenlanzifa article details 21071443 ifndef和 ifdef都是一种宏定义判断 作用是防止多重定义 ifndef是if n

  • element-plus 表单验证

    表单验证是使用率比较高的 和之前element版本也有些差别

  • 科技风UI除了蓝色，还有什么配色选择？

    今年做了一年的科技风 看到蓝色也是甚是觉得审美疲劳 在同类产品中体现出差异性也比较困难 寻思着除了蓝色 就没有别的配色选择了吗 通过对科技类设计的搜集 总结了科技风产品的配色文章参考 尽管我今年对蓝色够够了 但还是要分析下它作为FUI首选配

  • windows下，unity项目突然无法打开的挽救办法

    情景 项目在某次关机后就再也无法通过unity正常打开了 换了机器和unity版本也依然不行 如果你没做存档想必这是个令人非常崩溃的事情 但还有一种挽救的办法 至少是一种可能挽救的办法 那就是使用其他平台的unity打开项目 unity有w

  • 【Python网络蜘蛛】基础 - 多线程和多进程的基本原理

    文章目录 多线程和多进程的基本原理 多线程的含义 并发和并行 Python中的多线程和多进程 多线程和多进程的基本原理 在编写爬虫程序的时候 为了提高爬取效率 我们可能会同时运行多个爬虫任务 其中同样涉及多进程和多线程 多线程的含义 先了解

  • 面试官：为什么MySQL的索引要使用B+树，而不是其它树？比如B树？

    点击上方 Java之间 选择 置顶或者星标 你关注的就是我关心的 来源 https dwz cn exC8JdQS 上一篇 InnoDB的一棵B 树可以存放多少行数据 答案 约2千万 为什么是这么多 因为这是可以算出来的 要搞清楚这个问题

  • pandas创建与保存(导入与导出)dataframe

    文章目录 一 创建Dataframe 1 创建空dataframe 2 从list 创建dataframe 把list当做一列 把list当做一行 3 从 dict key value 创建dataframe 4 从 CSV 创建dataf

  • 布局数据存储，中国电子云意在何为？

    数据存储市场的未来在哪里 答案毋庸置疑是 云端 著名咨询机构Wikibon曾经做过一项统计 将全球三大云服务商的数据存储营收与传统存储厂商的营收进行对比 发现云服务商的数据存储业务规模已然赶上传统存储厂商 这揭示出一个不可阻挡的趋势 即随着

  • 线性回归算法（二）-- 最优解与损失函数

    介绍 要理解最优解和损失函数 我们需要先弄明白什么是误差 以简单线性回归为例 如下图所示 青色数据样本为真实值 y y y 直线上同一 x x x位置的红色样本点为预测值

  • qt操作第三方软件

    QT控制第三方软件方法 背景需求 实现思路 获取句柄方法 QT通过获取的信息操作 例子 控件ID为0或者控件ID和操作句柄相同怎么办 得到窗体x y height width 模拟键盘鼠标操作 附录 键值对照表 背景需求 通过前辈们写的软体

  • Shell--基础--06--传递参数

    Shell 基础 06 传递参数 1 介绍 我们可以在执行 Shell 脚本时 向脚本传递参数 1 1 脚本内获取参数的格式 格式为 n n 代表一个数字 0 执行的文件名 1 为执行脚本的第一个参数 2 为执行脚本的第二个参数 以此类推

  • AI时代，重新理解阿里云

    如果说 在数字化时代 阿里云给外界的标签是基于算力 数据等要素的基建角色 那么 在如今的智能化时代 基于自身强大的云计算能力和长期以往的AI技术积累 它的这种底座底色显然再一次被夯实 彰显 作者 皮爷 出品 产业家 宜昌城东大道 左侧是中国

  • DirectX编程：利用 DirectSound 录音

    DirectX编程 利用 DirectSound 录音 转载 http www cnblogs com stg609 archive 2008 10 24 1318931 html 花了一阵子 把DirectX安装后自带的帮助文件中的那部分

  • ES时间分组统计查询

    创建索引 PUT test 索引结构 PUT test mapping properties insertTime type date id type text fields keyword type keyword ignore abov

  • halcon之Blob分析实战

    Blob分析 Blob Analysis 在计算机视觉中的Blob是指图像中的具有相似颜色 纹理等特征所组成的一块连通区域 Blob分析 Blob Analysis 是对图像中相同像素的连通域进行分析 该连通域称为Blob 其过程其实就是将

  • 【数据结构】栈

    文章目录 1 栈的概念及结构 2 栈的实现 2 1栈的实现思路 2 2概念理解题 2 3栈的结构体定义 2 4函数接口 功能 2 5头文件Stack h 2 6函数实现Stack c 2 7测试函数Test c 2 8有效的括号 利用栈实现

热门标签