DS：顺序栈的实现

                                                    创作不易，友友们给个三连吧！！

一、栈的概念及结构

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

二、顺序栈的实现

数组实现栈：

首元素当栈低，栈顶是数组的尾元素，压栈就是尾插，出栈就是尾删

链表实现栈：

链表的最后一个结点当栈底，栈顶是链表的头结点，压栈就是头插，出栈就是头删

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

由于这些操作和顺序表的实现基本上是一样的，所以以下的介绍不做详细讲解。

建议大家看看博主关于顺序表的实现，再来看下面代码就易如反掌了！！

DS：顺序表的实现-CSDN博客

2.1 栈相关结构体

下面是定长的静态栈的结构，实际中一般不实用，因为设置得太小容易不够，设置得太大容易浪费

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

以我们主要实现下面的支持动态增长的栈

typedef int STDataType;
//支持动态增长的栈
typedef struct Stack
{
	STDataType* a;
	int top;//栈顶
	int capacity;//栈容量
}Stack;

2.2 初始化栈

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

     ps->top并不指向栈顶元素，而是指向栈顶元素的下一个位置，如果想要指向栈顶元素，则需要给top赋值-1.但是给top赋值0也有好处，就是top的值就相当于是顺序表中的size，即表示栈中的有效数据个数

2.3 压栈

void StackPush(Stack* ps, STDataType x)
{
	assert(ps);
	//判断是否需要扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* temp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newcapacity);
		if (temp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		ps->a = temp;
		ps->capacity = newcapacity;
	}
	//压栈
	ps->a[ps->top++] = x;
}

2.4 出栈

void StackPop(Stack* ps)
{
	assert(ps);
	//如果栈为空，则没有删除的必要
	assert(!StackEmpty(ps));
	ps->top--;
}

2.5 获取栈顶元素

STDataType StackTop(Stack* ps)
{
	assert(ps);
	//如果栈为空，不可能有栈顶元素
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

要注意:因为我们初始化的top是0，所以top指向的是栈顶元素的下一个位置！ 

2.6 获取栈中有效元素个数

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

因为top初始赋值为0， 所以top其实就相当于栈中的有效数据个数，专门封装一个函数只是想提高可读性！

2.7 检测栈是否为空

bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

      在顺序表中，是否为空只需要看有效容量个数是不是0即可，但是在顺序栈中有效数据个数size被替换成了 top，虽然我们知道top和size的意思差不多，但是如果在代码里直接用的话可读性就没有size这么好，所以单独设置一个检测栈是否为空的函数。

2.8 销毁栈

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

2.9 打印栈 

     栈相比较于顺序表，并不具备随机访问的特点，因为栈是后进先出的，也就是说如果我们要遍历栈去访问栈中的每个元素，那么就需要一边获取栈顶元素一边出栈，这其实就会破坏原先栈的结构了，一般只能使用一次，不具备复用性，因此没必要单独封装一个函数。如果实在想打印栈，那么就在main函数中这样测试一下

#include"Stack.h"

int main()
{
	Stack sk;
	StackInit(&sk);
	StackPush(&sk, 1);
	StackPush(&sk, 2);
	StackPush(&sk, 3);
	StackPush(&sk, 4);
	while (!StackEmpty(&sk))
	{
		printf("%d ", StackTop(&sk));//一边打印栈顶元素
		StackPop(&sk);//一边出栈
	}
}

三、顺序栈实现的所有代码 

3.1 Stack.h

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

typedef int STDataType;
//支持动态增长的栈
typedef struct Stack
{
	STDataType* a;
	int top;//栈顶
	int capacity;//栈容量
}Stack;

void StackInit(Stack* ps);//初始化栈
void StackPush(Stack* ps, STDataType x);//入栈
void StackPop(Stack* ps);//出栈
STDataType StackTop(Stack* ps);//获取栈顶元素
int StackSize(Stack* ps);//获取栈中有效元素个数
bool StackEmpty(Stack* ps);//检测栈是否为空，为空返回true
void StackDestory(Stack* ps);//销毁栈

3.2 Stack.c

#include"Stack.h"

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

void StackPush(Stack* ps, STDataType x)
{
	assert(ps);
	//判断是否需要扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* temp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newcapacity);
		if (temp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		ps->a = temp;
		ps->capacity = newcapacity;
	}
	//压栈
	ps->a[ps->top++] = x;
}


void StackPop(Stack* ps)
{
	assert(ps);
	//如果栈为空，则没有删除的必要
	assert(!StackEmpty(ps));
	ps->top--;
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	//如果栈为空，不可能有栈顶元素
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

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

bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

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

3.3 test.c(测试)

#include"Stack.h"

int main()
{
	Stack sk;
	StackInit(&sk);
	StackPush(&sk, 1);
	StackPush(&sk, 2);
	StackPush(&sk, 3);
	StackPush(&sk, 4);
	while (!StackEmpty(&sk))
	{
		printf("%d ", StackTop(&sk));//一边打印栈顶元素
		StackPop(&sk);//一边出栈
	}
}

 四、栈的相关oj题

4.1 选择题

1、一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出
栈的顺序是（B）。
A  12345ABCDE
B  EDCBA54321
C  ABCDE12345
D  54321EDCBA
解析：后进先出的特点，进栈过程中如果没有出栈，入栈和出栈的顺序是相反的。

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
解析：虽然是后进先出，但是入栈和出栈顺序相反是相对的，重点就是要判断进栈过程中是否有出栈，题目有明确提出这一点，所以这题最好同过画图去排除可能性，比如C，3出栈说明1和2都在栈内，下一个要出栈的话只能是2不能是1,1不可能在2的前面出栈。

4.2 有效的括号（OJ题） 

有效的括号（力扣）

条件的意思是：括号可以相互包含，放不能参差摆放

思路：利用栈结构后进先出的特点，让左括号入栈，右括号出栈匹配，当左右括号相等的前提下，如果最后栈为空，则符合题目要求，左括号大于右括号和右括号大于左括号要分开讨论。

typedef char STDataType;
//支持动态增长的栈
typedef struct Stack
{
	STDataType* a;
	int top;//栈顶
	int capacity;//栈容量
}Stack;
void StackInit(Stack* ps);//初始化栈
void StackPush(Stack* ps, STDataType x);//入栈
void StackPop(Stack* ps);//出栈
STDataType StackTop(Stack* ps);//获取栈顶元素
int StackSize(Stack* ps);//获取栈中有效元素个数
bool StackEmpty(Stack* ps);//检测栈是否为空，为空返回true
void StackDestory(Stack* ps);//销毁栈
void StackInit(Stack* ps)
{
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void StackPush(Stack* ps, STDataType x)
{
	assert(ps);
	//判断是否需要扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* temp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newcapacity);
		if (temp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		ps->a = temp;
		ps->capacity = newcapacity;
	}
	//压栈
	ps->a[ps->top++] = x;
}


void StackPop(Stack* ps)
{
	assert(ps);
	//如果栈为空，则没有删除的必要
	assert(!StackEmpty(ps));
	ps->top--;
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	//如果栈为空，不可能有栈顶元素
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

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

bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

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

bool isValid(char* s) 
{
    Stack st;
    StackInit(&st);
    while(*s)
    {
        if(*s=='('||*s=='{'||*s=='[')
        StackPush(&st,*s);
        else
        {
            //如果右比左多，栈为空
            if(StackEmpty(&st))
            {
                StackDestory(&st);
                return false;
            }
            char top=StackTop(&st);
            StackPop(&st);
            //不匹配
            if((*s==')'&&top!='(')||(*s=='}'&&top!='{')||(*s==']'&&top!='['))
            {
                StackDestory(&st);
                return false;
            }
        }
        ++s;
    }
    //如果左括号比右括号多，栈也有元素
    bool ret=StackEmpty(&st);
    StackDestory(&st);
    return ret;
}

要注意中间的条件判断！！ 

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

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

相关文章

test222

test222

欢迎关注博主 Mindtechnist 或加入【Linux C/C/Python社区】一起探讨和分享Linux C/C/Python/Shell编程、机器人技术、机器学习、机器视觉、嵌入式AI相关领域的知识和技术。 磁盘满的本质分析 专栏&#xff1a;《Linux从小白到大神》 | 系统学习Linux开发、VIM/GCC/GDB/Make工具…
阅读更多...
【SpringBoot】Redis集中管理Session和自定义用户参数解决登录状态及校验问题

【SpringBoot】Redis集中管理Session和自定义用户参数解决登录状态及校验问题

&#x1f3e1;浩泽学编程&#xff1a;个人主页 &#x1f525; 推荐专栏&#xff1a;《深入浅出SpringBoot》《java对AI的调用开发》 《RabbitMQ》《Spring》《SpringMVC》 &#x1f6f8;学无止境&#xff0c;不骄不躁&#xff0c;知行合一 文章目录 前言一、分布…
阅读更多...
【C语言】一道相当有难度的指针某大厂笔试真题(超详解)

【C语言】一道相当有难度的指针某大厂笔试真题(超详解)

这是比较复杂的题目&#xff0c;但是如果我们能够理解清楚各个指针代表的含义&#xff0c;画出各级指针的关系图&#xff0c;这道题就迎刃而解了。 学会这道笔试题&#xff0c;相信你对指针的理解&#xff0c;对数组&#xff0c;字符串的理解都会上一个档次。 字符串存储使用的…
阅读更多...
Linux之umask的使用

Linux之umask的使用

一、umask的作用 umask值用于设置用户在创建新文件和目录时的默认权限。umask值一共有4组数字&#xff0c;其中第1组数字用于定义特殊权限&#xff0c;一般不关心&#xff0c;日常工作中大家用的更多的是后面三组数字。以下图为例&#xff0c;输入“umask”命令之后&#xff0c…
阅读更多...
《动手学深度学习(PyTorch版)》笔记7.7

《动手学深度学习(PyTorch版)》笔记7.7

注&#xff1a;书中对代码的讲解并不详细&#xff0c;本文对很多细节做了详细注释。另外&#xff0c;书上的源代码是在Jupyter Notebook上运行的&#xff0c;较为分散&#xff0c;本文将代码集中起来&#xff0c;并加以完善&#xff0c;全部用vscode在python 3.9.18下测试通过&…
阅读更多...
DolphinScheduler-3.2.0 集群搭建

DolphinScheduler-3.2.0 集群搭建

本篇文章主要记录DolphinScheduler-3.2.0 集群部署流程。 注&#xff1a;参考文档&#xff1a; DolphinScheduler-3.2.0生产集群高可用搭建_dophinscheduler3.2.0 使用说明-CSDN博客文章浏览阅读1.1k次&#xff0c;点赞25次&#xff0c;收藏23次。DolphinScheduler-3.2.0生产…
阅读更多...
MySQL篇----第十八篇

MySQL篇----第十八篇

系列文章目录 文章目录 系列文章目录前言一、SQL 语言包括哪几部分？每部分都有哪些操作关键二、完整性约束包括哪些？三、什么是锁？四、什么叫视图？游标是什么？前言 前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站，…
阅读更多...
【51单片机】自定义静态数码管显示（设计思路＆代码演示）

【51单片机】自定义静态数码管显示（设计思路＆代码演示）

前言 大家好吖&#xff0c;欢迎来到 YY 滴单片机系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过单片机的老铁 主要内容含&#xff1a; 本章节内容为【实现动静态数码管】项目的第三个模块完整章节&#xff1a;传送门 欢迎订阅 YY滴C专栏&#xff01;更多干货持…
阅读更多...
3D立方体图册

3D立方体图册

<!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-width, initial-scale1.0" /><title>3D立方体图册</title><style>* {pad…
阅读更多...
JVM相关-JVM模型、垃圾回收、JVM调优

JVM相关-JVM模型、垃圾回收、JVM调优

一、JVM模型 JVM内部体型划分 JVM的内部体系结构分为三部分&#xff0c;分别是&#xff1a;类加载器&#xff08;ClassLoader&#xff09;子系统、运行时数据区&#xff08;内存&#xff09;和执行引擎 1、类加载器 概念 每个JVM都有一个类加载器子系统&#xff08;class l…
阅读更多...
如何在vue中使用拖动排序组件sortablejs

如何在vue中使用拖动排序组件sortablejs

效果图&#xff1a; 1.首先&#xff0c;我们需要在vue项目中安装依赖&#xff1a; npm install -save sortablejs2.创建demo文件>demoTest.vue&#xff0c;直接附上实例代码&#xff1a; <template><div><div id"table-names"><div class&…
阅读更多...
EasyExcel操作Excel表格

EasyExcel操作Excel表格

一、EasyExcel介绍 1.1 介绍 EasyExcel 是一个基于 Java 的简单易用的 Excel 文件读写工具&#xff0c;它提供了一种简单而又高效的方式来读取、写入和操作 Excel 文件。EasyExcel 是阿里巴巴开源的项目&#xff0c;它旨在简化开发人员处理 Excel 文件的流程&#xff0c;使得…
阅读更多...
SpringMVC第二天

SpringMVC第二天

一、SSM整合【重点】 1 SSM整合配置 问题导入 请描述“SSM整合流程”中各个配置类的作用&#xff1f; 1.1 SSM整合流程 创建工程 SSM整合 Spring SpringConfig MyBatis MybatisConfig JdbcConfig jdbc.properties SpringMVC ServletConfig SpringMvcConfig 功能模块…
阅读更多...
初识文件包含漏洞

初识文件包含漏洞

目录 什么是文件包含漏洞&#xff1f; 文件包含的环境要求 常见的文件包含函数 PHP伪协议 file://协议 php://协议 php://filter php://input zip://、bzip2://、zlib://协议 zip:// bzip2:// zlib:// data://协议 文件包含漏洞演示 案例1&#xff1a;php://inp…
阅读更多...
VBA技术资料MF117：测试显示器大小

VBA技术资料MF117：测试显示器大小

我给VBA的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的工作效率&#xff0c;而且可以提高数据的准确度。我的教程一共九套&#xff0c;分为初级、中级、高级三大部分。是对VBA的系统讲解&#xff0c;从简单的入门&#xff0c;到…
阅读更多...
[SAP] ABAP设置非系统关键字代码提示功能

[SAP] ABAP设置非系统关键字代码提示功能

在事务码SE38(ABAP编辑器)屏幕右下角&#xff0c;点击【Options选项】图标 勾选【代码完成】|【建议文本中的非关键字】&#xff0c;并点击【保存】按钮 在下面的程序代码中&#xff0c;当我需要输入在11行的位置输入非关键字lv_str的时候&#xff0c;会有非关键字代码提示的功…
阅读更多...
Blazor入门100天 : 自做一个手势滑动组件

Blazor入门100天 : 自做一个手势滑动组件

####0. 我想在blazor模仿app实现触摸返回,下拉刷新 … 现在用 blazor 做 app (blazor hybird) 和支持手机浏览页面越来越多, net8 也推出了一个webapp auto模式,可谓是极大的利好, 2024 让auto流行起来, &#x1f603; 配套源码 demo https://blazor.app1.es/b20Gesture ##…
阅读更多...
vscode +git +gitee 文件管理

vscode +git +gitee 文件管理

文章目录 前言一、gitee是什么&#xff1f;2. Gitee与VScode连接大概步骤 二、在vscode中安装git1.安装git2.安装过程3.安装完后记得重启 三、使用1.新建文件夹first2.vscode 使用 四、连接git1.初始化仓库2.设置git 提交用户和邮箱3.登陆gitee账号新建仓库没有的自己注册一个4…
阅读更多...
用Python来实现2024年春晚刘谦魔术

用Python来实现2024年春晚刘谦魔术

简介 这是新春的第一篇&#xff0c;今天早上睡到了自然醒&#xff0c;打开手机刷视频就被刘谦的魔术所吸引&#xff0c;忍不住用编程去模拟一下这个过程。 首先&#xff0c;声明的一点&#xff0c;大年初一不学习&#xff0c;所以这其中涉及的数学原理约瑟夫环大家可以找找其…
阅读更多...
MYSQL笔记：约束条件

MYSQL笔记：约束条件

MYSQL笔记&#xff1a;约束条件 主键约束 不能为空&#xff0c;值必须是不同的&#xff08;唯一性&#xff09; 一个表只能修饰一个主键 PRIMARY KEY自增约束 AUTO_INCREMENT唯一键约束 可以为空 unique非空约束 not null 默认值约束 default 外键约束 foreign key …
阅读更多...
最新文章

Copyright @ 2022~2023