【C语言】栈的实现(数据结构)


前言:

还是举一个生活中的例子,大家都玩过积木,当我们把积木叠起来的时候,如果要拿到最底部的积木,我们必须从顶端一个一个打出,最后才能拿到底部的积木,也就是后进先出(先进后出)的道理,今天分享栈的实现的本质也就是后进先出(先进后出)。

目录

前言:

栈的概念及结构

栈的实现

栈的结构定义

初始化栈

压栈(数据的添加)

出栈(数据的删除)

获取栈顶元素

获取栈中有效元素个数

判断栈是否为空

栈实现的总代码(vs2022)

头文件Stack.h

函数文件Stack.c

测试Text.c


栈的概念及结构

要去实现栈,我们要知道什么是 栈,栈的结构是什么,该从什么方向去实现。

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

 

如图我们会发现数据进栈出栈后的顺序倒置了,其实栈不只是可以将顺序导致,我们也可以先把A,B放进去,拿出来之后,再将C,D放进去,全部拿出来可以得到C,D,A,B,所以栈最后导致的结果是多种多样的,这取决你如何运用栈了。

栈的实现

  栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上
插入数据的代价比较小。  
我们在这里使用数组进行实现,如图所示我们把数组的尾部作为栈顶,这样可以轻松的进行压栈操作(增加数据),如果使用链表的话,我们找到尾节点需要进行遍历找尾(利用循环去找为节点),这样就增多了时间的消耗,这里使用数组来实现栈,可以提高算法效率。

栈的结构定义

typedef int STDataType;

typedef struct Stack
{ 
	STDataType* a;
	int top;     //栈顶
	int capacity;//栈容量
}Stack;

栈只需要对栈顶进行操作,所以我们有一个变量top表示栈顶。后面需要判断栈是否为空,我们需要一个变量capacity表示栈容量。

初始化栈

void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	ps->top = 0;
	ps->capacity = 4;
}

这里我们创造了4个整型变量的空间,所以capacity给4。

压栈(数据的添加)

void StackPush(Stack* ps,STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)//考虑到空间大小不够,使用realloc进行增容操作
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)//要注意tmp可能为空的情况。
		{
			printf("realloc fail!!!");
			exit(-1);
		}
		ps->a = tmp;//别忘了把指针a指向新开辟的空间
		ps->capacity *= 2;
	}
	ps->a[ps->top] = x;
	ps->top++;//注意个数的增加
}

在压栈的时候要注意几点:

1.压栈时要考虑空间的大小是否足够,不够时要进行增容操作。

2.增容操作后的原指针要指向新指针,保证数据不会丢失。

3.压栈过后要对将top往后移动一位,因为top的指向是数组最后元素的下一个位置。

出栈(数据的删除)

void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);//top不能小于或等于0,因为top是指向栈顶元素的下一个位置
	ps->top--;
}

因为是用数组进行栈的实现,我们只需要把栈顶往前移动一位,就表示删除了数据。

获取栈顶元素

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];//因为top是指向栈顶元素的下一个位置,所以要-1

}

一定注意对ps->top>0进行断言,保证栈的元素不为空。

获取栈中有效元素个数

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

}

top指向的数组尾部元素后一位,刚好是数组中有效元素的个数。

判断栈是否为空

bool StackEmpty(Stack* ps)//bool也可以使用 表示真假
{
	assert(ps);
	return ps->top == 0;
}

检查栈是否为空,如果不为空则返回0,如果为空则返回非零结果。

栈实现的总代码(vs2022)

头文件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 StackDestory(Stack* ps);
//压栈
void StackPush(Stack* ps,STDataType x);
//出栈
void StackPop(Stack* ps);
//获取栈顶元素
STDataType StackTop(Stack* ps);
//获取栈中有效元素的个数
int StackSize(Stack* ps);
//检查栈是否为空,如果不为空则返回0,如果为空则返回非零结果
bool StackEmpty(Stack* ps);//bool也可以使用 表示真假

函数文件Stack.c

#include"Stack.h"


void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	ps->top = 0;
	ps->capacity = 4;
}
void StackDestory(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;

}
//入栈
void StackPush(Stack* ps,STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)//考虑到空间大小不够,使用realloc进行增容操作
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)//要注意tmp可能为空的情况。
		{
			printf("realloc fail!!!");
			exit(-1);
		}
		ps->a = tmp;//别忘了把指针a指向新开辟的空间
		ps->capacity *= 2;
	}
	ps->a[ps->top] = x;
	ps->top++;//注意个数的增加
}
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);//top不能小于或等于0,因为top是指向栈顶元素的下一个位置
	ps->top--;
}
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];//因为top是指向栈顶元素的下一个位置,所以要-1

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

}
bool StackEmpty(Stack* ps)//bool也可以使用 表示真假
{
	assert(ps);
	return ps->top == 0;
}

测试Text.c

#include"Stack.h"

void StackText()
{
	Stack st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	StackDestory(&st);
}

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

好啦,这就是今天学习的分享啦!看到希望大家的三连呀!

如果有不当之处,欢迎大佬指正!


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

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

相关文章

项目的小结

1.实现实时聊天 1.服务端建立一个ConcurrentHashMap<> 用来存储在线用户&#xff0c;用户账号和socket然后&#xff0c;如果有个人发了信息&#xff0c;就去数据库中查询&#xff0c;然后根据这个在线用户进行传递信息 服务端框架&#xff1a; public class ServerMain {…

系统架构设计师教程 第4章 信息安全技术基础知识-4.3 信息安全系统的组成框架4.4 信息加解密技术-解读

系统架构设计师教程 第4章 信息安全技术基础知识-4.3 信息安全系统的组成框架 4.3 信息安全系统的组成框架4.3.1 技术体系4.3.1.1 基础安全设备4.3.1.2 计算机网络安全4.3.1.3 操作系统安全4.3.1.4 数据库安全4.3.1.5 终端安全设备4.3.2 组织机构体系4.3.3 管理体系4.4 信息加…

Ubuntu 22.04.4 LTS (linux) Tomcat 项目部署

1 war包直接放在tomcat webapps 下面 2 修改server.xml &#xff0c;改成自定义目录 sudo vim /data/tomcat/conf/server.xml <Host name"localhost" appBase"webapps" --> <Host name"localhost" appBase"" <Conte…

今日分享丨用双钻模型设计中后台产品

随着C端市场的快速进化&#xff0c;用户的审美标准与产品体验认知均达到了前所未有的高度&#xff0c;这一转变深刻影响了用户对B端产品的期待。在面对B端产品时&#xff0c;用户不自觉地以C端产品的优质体验为参照&#xff0c;希望产品不仅能高效完成工作任务&#xff0c;同时…

收藏:高性价比https证书

在当今的数字化世界中&#xff0c;网络安全已经成为了每个网站所有者的首要关注点&#xff0c;为了保护网站的安全&#xff0c;防止数据被窃取或篡改&#xff0c;使用SSL证书已经成为了一种标准的做法&#xff0c;SSL证书是一种用于加密网站和用户之间数据传输的证书&#xff0…

easyExcel和poi的版本对应

easypoi3.0.5对应的poi版本_easypoi和poi版本对应-CSDN博客 https://github.com/alibaba/easyexcel/blob/v3.2.0/pom.xml 解决 java.lang.NoClassDefFoundError: org/apache/poi/POIXMLTypeLoader 报错-CSDN博客 参考这个文档解决的- 引入最佳版本是3.15版本 java.lang.NoClas…

ubuntu一些好用的开发工具及其配置

1 终端模糊搜索fzf https://github.com/junegunn/fzf 输入某命令&#xff0c;比如 conda &#xff0c;按下ctrlR&#xff0c;会显示和该命令匹配的历史命令的列表 有了这个工具再也不用记忆太复杂的命令&#xff0c;只需要知道大概几个单词&#xff0c;输入即可搜索。 其搜索…

可见性::

目录 定义&#xff1a; 解决方法&#xff1a; ①使用synchronized实现缓存和内存的同步 修改一&#xff1a; 加入语句&#xff1a; 代码&#xff1a; 修改2&#xff1a; 在代码块中加入&#xff1a; 代码&#xff1a; 执行结果&#xff1a; 原因&#xff1a; ②使用…

RPA软件-影刀使用

流程自动化 影刀将操作进行抽象&#xff0c;分为一下几个对象&#xff1a; 网页自动化 &#xff08;1&#xff09; 网页自动化应用场景&#xff1a;网页操作、数据抓取 &#xff08;2&#xff09; 网页操作&#xff1a;基础操作-指令操作&#xff0c;智能操作-关联元素&#…

PTrade常见问题系列15

某容器占用内存很高需要关闭处理&#xff1f; 1、若只是关闭部分进程&#xff0c;则需要进入容器后top -b 排序出资源占用消耗最高的几个进程&#xff0c;通过kill -9的方式进行清理&#xff1b; 2、若要关闭对应容器&#xff0c;则在管理端勾选后进行关闭容器操作或者在后台执…

【学习笔记】解决Serial Communication Library编译问题

【学习笔记】解决编译 Serial Communication Library 时的 Catkin 依赖问题 Serial Communication Library 是一个用 C 编写的用于连接类似 rs-232 串口的跨平台库。它提供了一个现代的 C 接口&#xff0c;它的工作流程设计在外观和感觉上与 PySerial 相似&#xff0c;但串口速…

本地化部署一个简单的AI大模型,Llama3.1

7 月 23 日消息&#xff0c;Meta 今晚正式发布llama3.1&#xff0c;提供 8B、70B 及 405B 参数版本。 Meta 称 4050 亿参数的 Llama 3.1-405B 在常识、可引导性、数学、工具使用和多语言翻译等一系列任务中&#xff0c;可与 GPT-4、GPT-4o、Claude 3.5 Sonnet 等领先的闭源模型…

KETTLE运行出现乱码和无法执行问题及解决方案

一、乱码问题 &#xff08;1&#xff09;出现乱码&#xff0c;在数据库连接里面的选项里面加入&#xff1a;characterEncodingutf8和tinyInt1isBitfalse &#xff08;2&#xff09;取消简易转换&#xff0c;点开表输入&#xff0c;取消”允许简易转换”选项&a…

学习笔记:MySQL数据库操作5

1. 触发器&#xff08;Triggers&#xff09; 触发器是数据库的一种高级功能&#xff0c;它允许在执行特定数据库操作&#xff08;如INSERT、UPDATE、DELETE&#xff09;之前或之后自动执行一段代码。 1.1 创建商品和订单表 商品表&#xff08;goods&#xff09; gid: 商品编号…

【LeetCode:3098. 求出所有子序列的能量和 + 记忆化缓存】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…

c++ 内存管理(newdeletedelete[])

因为在c里面新增了类&#xff0c;所以我们在有时候会用malloc来创建类&#xff0c;但是这种创建只是单纯的开辟空间&#xff0c;没有什么默认构造的。同时free也是free的表面&#xff0c;如果类里面带有指针指向堆区的成员变量就会free不干净。 所以我们c增加了new delete和de…

22、Python之面向对象:万类霜天竞自由

引言 虽然&#xff0c;截止目前从来没有系统性地讲述面向对象的内容&#xff0c;但是阅读过前面文章的童鞋&#xff0c;关于Python中的面向对象应该有如下观念了&#xff1a; 1、Python中一切皆对象&#xff0c;对象有三个核心内容&#xff1a;id、类型、值。 2、Python中的…

2024 微信小程序 学习笔记 第二天

1. WXML 模板语法 数据绑定 事件绑定 条件渲染 列表渲染 2. WXSS 模板样式 rpx 样式导入 全局和局部样式 3. 全局配置 window tabBar 配置tabBar案例 4. 网络数据请求 Get请求 Post 请求 加载时请求 5. 案例 -本地生活&#xff08;首页&#xff09; 导航栏 轮播图 九宫格效果…

设计模式--创建型

实现 #include <iostream> #include <memory>// 抽象产品类 class Product {public:virtual ~Product() {}virtual void Operation() const 0; };// 具体产品 类A class ConcreteProductA : public Product {public:virtual void Operation() const override {st…

Ubuntu 22.04.4 LTS (linux) Tomcat 9 内存和线程优化

1 Apache Tomcat 9.0.91 线程 #在70行左右&#xff0c;增加如下 sudo vim /data/tomcat/conf/server.xmlmaxThreads"800" #客户请求最大线程数minSpareThreads"200" #最小线程数maxSpareThreads"500" #最大线程数acceptCount"800"…