C语言数据结构之栈

目录

    • 1.栈的概念及结构
    • 2.栈的实现
    • 3.栈的代码实现
    • 4.相关例题

在这里插入图片描述
•͈ᴗ•͈ 个人主页：御翮
•͈ᴗ•͈ 个人专栏：C语言数据结构
•͈ᴗ•͈ 欢迎大家关注和订阅!!!
在这里插入图片描述

1.栈的概念及结构

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

讲到栈，就要提到它的两种基本操作：压栈（入栈）和出栈。

入栈和出栈遵循一种规则：后进先出（进入栈晚的数据先出栈，就像是先进去的数据被后进入的数据压住了，只能先把上面的数据拿走才能拿到下面的数据）。

在这里插入图片描述

连续入栈和连续出栈：

在这里插入图片描述

2.栈的实现

对于栈的实现，我们有两种结构可以选择：顺序表和链表。考虑到先进后出的规则，链表尾插和尾删的成本比顺序表高，不太适合，顺序表尾插和尾删只需要改变加减的size的大小就可以做到，所以我们采用顺序表来实现栈。

关于栈，我们要实现以下几个接口：

在这里插入图片描述

3.栈的代码实现

test.c

#include "Stack.h"

void menu()
{
	printf("********************************************\n");
	printf("***************    请选择    ***************\n");
	printf("******   1.PushStack    2.PopStack   *******\n");
	printf("******   3.PrintStack   4.TopStack   *******\n");
	printf("******   5.SizeStack    6.CheckEmpty *******\n"); 
	printf("******             0.Exit            *******\n");
	printf("********************************************\n");
}

int main()
{
	int input = 0;
	int value = 0;
	Stack s;

	Init_Stack(&s);
	do
	{
		menu();
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			printf("请输入你要入栈的值>:");
			scanf("%d", &value);
			Push_Stack(&s, value);
			break;
		case 2:
			Pop_Stack(&s);
			break;
		case 3:
			Print_Stack(&s);
			break;
		case 4:
			if (Empty_Stack(&s) != 0)
			{
				printf("栈为空\n");
				break;
			}
			printf("栈顶的元素是%d\n", Top_Stack(&s));
			break;
		case 5:
			printf("栈中有效元素的个数为%d\n", Size_Stack(&s));
			break;
		case 6:
			if (Empty_Stack(&s) != 0)
				printf("栈为空\n");
			else
				printf("栈不为空\n");
			break;
		case 0:
			Destroy_Stack(&s);
			printf("销毁栈成功\n");
			break;
		default:
			printf("选择错误，请重新选择\n");
			break;
		}
	} while (input);

	return 0;
}

Stack.c

#include "Stack.h"


//初始化栈
void Init_Stack(Stack* ptr)
{
	assert(ptr); // ptr要解引用，不能为空指针

	STDataType* tmp = (STDataType*)malloc(3*sizeof(STDataType));

	if (tmp == NULL) //申请空间可能失败，失败会返回NULL，不能解引用，要终止程序
	{
		perror("Init_Stack\n");
		exit(1);
	}

	ptr->stack = tmp; //申请空间成功就正常初始化
	ptr->capacity = 3;
	ptr->size = 0;
}



//销毁栈
void Destroy_Stack(Stack* ptr)
{
	assert(ptr); // ptr要解引用，不能为空指针

	free(ptr->stack);
	ptr->stack = NULL;
}



//检查栈是否满了，满了则扩容
void Check_Capacity(Stack* ptr)
{
	assert(ptr); // ptr要解引用，不能为空指针

	if (ptr->size == ptr->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ptr->stack, 2 * ptr->capacity * sizeof(STDataType));

		if (tmp == NULL) //申请空间可能失败，失败会返回NULL，不能解引用，要终止程序
		{
			perror("Check_Capacity\n");
			exit(1);
		}

		ptr->stack = tmp;   //要把申请到的空间赋给原指针，不然后面操作不了这块空间
		ptr->capacity *= 2; //扩容之后要修改capacity的值，不然检查栈的大小时会一直扩容
	}
}



//打印栈里面的数据
void Print_Stack(Stack* ptr)
{
	assert(ptr); // ptr要解引用，不能为空指针

	for (int i = 0; i < ptr->size; i++)
	{
		printf("%d ", ptr->stack[i]);
	}

	printf("\n");
}



//数据入栈
void Push_Stack(Stack* ptr,STDataType val)
{
	assert(ptr); // ptr要解引用，不能为空指针

	Check_Capacity(ptr); //入栈时要检查空间是否足够

	ptr->stack[ptr->size] = val;
	ptr->size++;
}



//数据出栈
void Pop_Stack(Stack* ptr)
{
	assert(ptr); // ptr要解引用，不能为空指针

	if (ptr->size == 0)
	{
		printf("栈为空\n");
		return;
	}

	ptr->size--; //出栈就相当于顺序表可以读取的元素少一个，size - 1 就可以了
}



//获取栈顶数据
STDataType Top_Stack(Stack* ptr)
{
	assert(ptr); // ptr要解引用，不能为空指针

	return ptr->stack[ptr->size-1];
}



//获取栈储存的元素个数
int Size_Stack(Stack* ptr)
{
	assert(ptr); // ptr要解引用，不能为空指针

	return ptr->size;
}



//判断栈是否为空
int Empty_Stack(Stack* ptr)
{
	assert(ptr); // ptr要解引用，不能为空指针

	if (ptr->size == 0)
		return 1;
	else
		return 0;
}

Stack.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <errno.h>

typedef int STDataType;  // 栈储存的数据的类型

typedef struct Stack
{
	STDataType* stack;  //动态开辟的空间，在堆上
	int size;			//储存元素的个数
	int capacity;		//栈的大小（容量），可变化
}Stack;


//栈的初始化
void Init_Stack(Stack* ptr);


//打印栈里面的数据
void Print_Stack(Stack* ptr);


//数据入栈
void Push_Stack(Stack* ptr, STDataType val);


//数据出栈
void Pop_Stack(Stack* ptr);


//获取栈顶数据
STDataType Top_Stack(Stack* ptr);


//获取栈储存元素的个数
int Size_Stack(Stack* ptr);


//判断栈是否为空
int Empty_Stack(Stack* ptr);


//销毁栈
void Destroy_Stack(Stack* ptr);

4.相关例题

题目描述：

在这里插入图片描述

参考解析：

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

typedef int STDataType;

typedef struct Stack
{
	STDataType* stack;
	int size;
	int capacity;
}Stack;

void Init_Stack(Stack* ptr)
{
	assert(ptr);

	STDataType* tmp = (STDataType*)malloc(3 * sizeof(STDataType));
	if (tmp == NULL)
	{
		perror("Init_Stack\n");
		exit(1);
	}

	ptr->stack = tmp;
	ptr->capacity = 3;
	ptr->size = 0;
}

void Destroy_Stack(Stack* ptr)
{
	assert(ptr);

	free(ptr->stack);
	ptr->stack = NULL;
}

void Check_Capacity(Stack* ptr)
{
	assert(ptr);

	if (ptr->size == ptr->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ptr->stack, 2 * ptr->capacity * sizeof(STDataType));

		if (tmp == NULL)
		{
			perror("Check_Capacity\n");
			exit(1);
		}

		ptr->stack = tmp;
		ptr->capacity *= 2;
	}
}

void Print_Stack(Stack* ptr)
{
	assert(ptr);

	for (int i = 0; i < ptr->size; i++)
	{
		printf("%d ", ptr->stack[i]);
	}

	printf("\n");
}

void Push_Stack(Stack* ptr, STDataType val)
{
	assert(ptr);

	Check_Capacity(ptr);

	ptr->stack[ptr->size] = val;
	ptr->size++;
}

void Pop_Stack(Stack* ptr)
{
	assert(ptr);

	if (ptr->size == 0)
	{
		return;
	}

	ptr->size--;
}

STDataType Top_Stack(Stack* ptr)
{
	assert(ptr);

	return ptr->stack[ptr->size - 1];
}

int Size_Stack(Stack* ptr)
{
	assert(ptr);

	return ptr->size;
}

int Empty_Stack(Stack* ptr)
{
	assert(ptr);

	if (ptr->size == 0)
		return 1;
	else
		return 0;
}


//解题思路：
//该题比较简单，是对栈特性很好的应用，具体操作如下：
//循环遍历String中的字符，逐个取到每个括号，如果该括号是：
//1. 左括号，直接入栈
//2. 右括号，与栈顶的左括号进行匹配，如果不匹配直接返回false
//否则继续循环
//循环结束后，如果栈空则匹配，否则左括号比右括号多肯定不匹配

bool isValid(char* s) 
{
	Stack st;

	Init_Stack(&st);

	while (*s)
	{
		switch (*s)
		{
			//是左括号则入栈
		case '(':
		case '{':
		case '[':
			Push_Stack(&st, *s);
			break;
			//是右括号则从栈顶获取左括号来检测是否匹配
		case ')':
		case '}':
		case ']':
			if (Size_Stack(&st) == 0) // 如果有右括号，而栈里面左括号已经没有了，就不是匹配的
				return false;

			char tmp = Top_Stack(&st);
			Pop_Stack(&st);			 // 取完元素要从栈中删除

			if (tmp == '(' && *s != ')')
				return false;

			else if (tmp == '{' && *s != '}')
				return false;

			else if (tmp == '[' && *s != ']')
				return false;
		}
		s++;
	}

	if (Empty_Stack(&st)) // 如果完全匹配，循环结束时栈内一定是空的
		return true;
	else
		return false;
}

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

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

相关文章

AI大模型系列：自然语言处理，从规则到统计的演变

AI大模型系列：自然语言处理，从规则到统计的演变

自然语言处理&#xff0c;从规则到统计的演变 自然语言处理&#xff08;Natural Language Processing&#xff0c;NLP&#xff09;是人工智能的一个重要分支&#xff0c;主要研究如何让计算机理解、解释和生成人类语言。从自然语言处理的字面上来看&#xff0c;最重要的是“语言…
阅读更多...
Unity | 集成 Protobuf（proto 转 cs 插件及序列化与反序列化）

Unity | 集成 Protobuf（proto 转 cs 插件及序列化与反序列化）

1. 添加 dll 1. 下载 protobuf 源码 根据需要下载 protobuf 指定版本的源码&#xff0c;这里以 v3.21.12&#xff08;protobuf-csharp-3.21.12.zip&#xff09;为例&#xff1a; 下载地址&#xff1a;「https://github.com/protocolbuffers/protobuf/releases」 2. 下载 Vis…
阅读更多...
防火墙技术基础篇：认识安全策略、安全区域、域间转发及报文转发流程

防火墙技术基础篇：认识安全策略、安全区域、域间转发及报文转发流程

防火墙技术基础篇&#xff1a;认识安全策略、安全区域、域间转发及报文转发流程 一、安全策略匹配机制 简单通俗的讲&#xff0c;防火墙设备最基本的用途就是定义数据如何转发&#xff0c;靠什么定义呢&#xff1f;最基本的就是安全策略&#xff0c;当流量来到防火墙之后首先…
阅读更多...
组播技术原理概述

组播技术原理概述

组播与广播和单播的对比 l 组播、广播和单播工作模式的对比 单播&#xff1a;数据报文从一台主机&#xff0c;点对点的发给另外一台主机 广播&#xff1a;数据报文从一台主机&#xff0c;发给广播域内的全部主机 组播&#xff1a;数据报文从一台主机&#xff0c;发给…
阅读更多...
JS----前端将列表数据转树型数据

JS----前端将列表数据转树型数据

前端将列表数据转树型数据 场景&#xff1a;后端返回列表数据&#xff0c;由前端根据业务需求完成树型数据转换&#xff0c; 常用于侧边导航菜单&#xff0c;下拉树型数据项等 export function listToTree(data: []) {var map: any {},tree: any []data.forEach((item: any…
阅读更多...
ansible-playbook获取当前执行任务的ip及hostname

ansible-playbook获取当前执行任务的ip及hostname

目录 概述注意实践代码 概述 注意 此问题&#xff0c;配置上一个文件即可解决 实践 代码 --- - name: Get IP Addresshosts: allgather_facts: notasks:- name: Get IP Addressansible.builtin.setup:register: host_ip- name: Print IP Addressansible.builtin.debug:msg:…
阅读更多...
网络程序 -- TCP版服务器

网络程序 -- TCP版服务器

一 多进程版TCP服务器 1.1 核心功能 对于之前编写的 字符串回响程序 来说&#xff0c;如果只有一个客户端进行连接并通信&#xff0c;是没有问题的&#xff0c;但如果有多个客户端发起连接请求&#xff0c;并尝试进行通信&#xff0c;服务器是无法应对的 原因在于 服务器是一个…
阅读更多...
数据结构 - 队列 [动画+代码注释超详解]，萌新轻松上手！！！

数据结构 - 队列 [动画+代码注释超详解]，萌新轻松上手！！！

一. 队列的概念 队列是一种特殊的线性表&#xff0c;用于存储元素&#xff0c;并且按照先进先出(First In First Out)的顺序进行管理&#xff0c;这意味着最先加入队列的元素将会是最先从队列中被移除的元素 队列的原型&#xff1a;只允许在一端进行插入数据的操作&#xff0c…
阅读更多...
【嵌入式AI开发】轻量级卷积神经网络MobileNetV2详解

【嵌入式AI开发】轻量级卷积神经网络MobileNetV2详解

前言：MobileNetV2网络先升维后降维，在降维时使用线性激活函数，带残差的Inverted bottleck模块，防止ReLU信息丢失。在图像分类、目标检测、语义分割等任务上实现了网络轻量化、速度和准确度的权衡。 回顾MobileNetV1的理论和MobileNetV2项目实战可查阅如下链接： 【嵌入式AI…
阅读更多...
使用SDRPI运行openwifi和设置网口

使用SDRPI运行openwifi和设置网口

目录 一 制作启动盘 二 使用串口的方式启动openwifi 三 无线连接 四 网口设置&#xff0c;有线连接 五 使用SSH登录 一 制作启动盘 在github上下载img文件&#xff0c;由于github上下载速度比较慢&#xff0c;我会上传网盘链接 githun下载img文件地址: https://git…
阅读更多...
OS对软件的管理，进程，PCB、子进程

OS对软件的管理，进程，PCB、子进程

进程 可执行程序加载到内存中&#xff0c;操作系统为内个程序都形成一个PCB对象&#xff08;结构体对象&#xff09;&#xff0c;PCB里存放着这个程序的所有的属性。进程可执行程序PCB &#xff0c;CPU执行程序也是先通过该程序的PCB找到相应的程序代码&#xff0c;然后一条一…
阅读更多...
SpringCloud之Hystrix

SpringCloud之Hystrix

Hystrix理解 熔断器本身是一种开关装置&#xff0c;用于在电路上保护线路过载。当线路中有电器发生短路时&#xff0c;熔断器能够及时切断故障电路&#xff0c;防止发生过载、发热甚至起火等严重后果。这种保护机制被借鉴到分布式系统的设计中&#xff0c;形成了类似Hystrix中…
阅读更多...
基于SpringBoot+Vue校园二手交易系统的设计与实现

基于SpringBoot+Vue校园二手交易系统的设计与实现

系统介绍 自从新冠疫情爆发以来&#xff0c;各个线下实体越来越难做&#xff0c;线下购物的人也越来越少&#xff0c;随之带来的是一些不必要的浪费&#xff0c;尤其是即将毕业的大学生&#xff0c;各种用品不方便携带走导致被遗弃&#xff0c;造成大量的浪费。本系统目的就是让…
阅读更多...
安装好fedora_kde系统后的操作

安装好fedora_kde系统后的操作

文章目录 1 前言2 办公软件2.1 输入法2.1.1 安装 fcitx52.1.2 安装 fcitx5-rime2.1.3 安装 東風破2.1.4 使用 東風破 安装 郭斌勇 大神的 新世纪五笔 项目2.1.5 配置 fcitx5-rime2.1.6 重新部署 3 感谢阅读~ 1 前言 本文用的是 fedora 40 kde plasma 6。 因为有很多的软件都同时…
阅读更多...
2024全国大学生高新技术竞赛——算法智星挑战赛（A~J）

2024全国大学生高新技术竞赛——算法智星挑战赛（A~J）

好多都是之前的原题&#xff0c;甚至有上次第二届全国大学生信息技术认证挑战赛的原题&#xff0c;刚打完又来一遍&#xff0c;没绷住。 A. 手机 原题之一&#xff0c;具体出处忘了 最无脑的方法直接用map记录每个按下的值就行了&#xff0c;代码仅供参考。 #include <bit…
阅读更多...
MATLAB矩阵

MATLAB矩阵

MATLAB 矩阵 矩阵是数字的二维数组。 在MATLAB中&#xff0c;您可以通过在每行中以逗号或空格分隔的数字输入元素并使用分号标记每行的结尾来创建矩阵。 例如&#xff0c;让我们创建一个45矩阵一- 示例 a [ 1 2 3 4 5; 2 3 4 5 6; 3 4 5 6 7; 4 5 6 7 8] MATLAB将执行上述语…
阅读更多...
pycharm使用ssh连接服务器

pycharm使用ssh连接服务器

1、具体流程 打开pycharm – File – Setting 输入服务器的IP地址&#xff0c;端口号、登录账号名 输入登陆账号的密码 下一步 一些初级设置 2、一些需要注意的小问题 2.1 更改代码地址 2.2 本地代码上传到服务器 首先在需要上传文件右键 2.3 在服务器的环境中上新安装库&am…
阅读更多...
Docker 简单使用及安装常用软件

Docker 简单使用及安装常用软件

一、Docker 安装、配置与卸载 1.1、Docker 安装 # 1.安装gcc环境 yum -y install gcc gcc-c && \# 2. 卸载docker旧版本&#xff08;可能之前有安装&#xff09; yum -y remove docker docker-common docker-selinux docker-engine && \# 3. 安装依赖的软件包…
阅读更多...
【项目学习01_2024.04.27_Day01】

【项目学习01_2024.04.27_Day01】

学习笔记 项目学习链接第2章 内容管理模块v3.11 模块需求分析1.1 什么是需求分析1.2 模块介绍1.3 业务流程1.4 界面原型 2 创建模块工程2.1 模块工程结构父工程和子工程之间的继承关系以及工程与工程之间的依赖关系&#xff0c;通俗理解&#xff1a;2.2 创建模块工程\pom\含义及…
阅读更多...
go 安装软件报go.mod file not found

go 安装软件报go.mod file not found

执行 go get -u github.com/go-sql-driver/mysql 下载mysql 报错 解决方法: 控制台&#xff1a;输入go env 返回如下&#xff1a; 红圈值为NUL&#xff0c;需要设置GOMOD的值, 然后再控制台执行 &#xff08;1&#xff09;mkdir mod (2)go mod init mod 然后再执行下载&…
阅读更多...
最新文章

Copyright @ 2022~2023