数据结构学习之路--深入探索栈的核心要点(附C源码)

   哈喽~大家！今天我们来学习栈的特别节目，精彩马上开始~

目录

前言

一、栈 

1 栈的概念

2 栈的结构

3 栈的实现 

3.1 栈的定义

3.2 栈的初始化 

3.3 入栈 

3.4 出栈 

3.5 取栈顶元素 

 3.6 判断栈是否为空

3.7 栈的大小

3.8 栈的销毁 

 二、源代码

前言

   栈和队列均是常见的数据结构。栈的特点是后进先出（即 Last In First Out(LIFO) ），其增删查元素都在栈顶实现。而队列的特点是先进先出，增加元素在队尾实现，删除和查看元素都在队首实现。本期我们来详细学习实现栈的结构。

一、栈 

我们先根据下图直观地了解栈：

1 栈的概念

   栈是一种特殊的线性表，特点是后进先出，它仅允许在固定一端进行插入和删除元素操作，最先加入的元素最后取出，最后加入的元素最先取出。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。文字描述难免过于死板，为了更好的帮助大家理解，附以下图解： 

将数字 1 到 7 依次入栈之后，此时栈顶元素是 7 ，第一个出栈的元素是 7。

2 栈的结构

3 栈的实现 

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

一般栈的实现需要完成几种函数的操作： 

  • 栈的初始化
  • 入栈
  • 出栈
  • 取出栈顶元素
  • 判断栈是否为空
  • 栈的销毁 
//初始化
void StackInit(ST* ps);
//入栈
void StackPush(ST* ps, STDateType x);
//出栈
void StackPop(ST* ps);
//取栈顶元素
STDateType GetTop(ST* ps);
//判空
bool StackEmpty(ST* ps);
//栈大小
int StackSize(ST* ps)
//栈的销毁
void StackDestory(ST* ps);

3.1 栈的定义

//这里我们实现的是动态的栈

typedef int STDateType;    //方便数据类型的替换

typedef struct Stack        
{
	STDateType* a;         //动态开辟数组
	int top;               //栈顶
	int capacity;          //容量，方便扩容
}ST;

首先，定义动态数组 a，采用动态数组的方式主要是便于后期容量的扩充；然后，定义一个变量 top 用于标识栈顶位置；最后，定义一个变量 capacity 用于统计栈可以容纳的数据个数。 

3.2 栈的初始化 

//初始化
void StackInit(ST* ps)
{
	//判空
	assert(ps);

	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

首先，将指向栈中数据内存空间的指针 a 初始化为NULL；然后，将指向栈顶元素的变量 top初始化为0；最后，再将标识栈当前容量的 capacity 初始化为0即可。 

3.3 入栈 

//入栈
void StackPush(ST* ps, STDataType x)
{
	//判空
	assert(ps);
 
	//判断容量是否已满
	//top标识的是最后一个数据的下一个位置，如果想要指向最后一个数据，初始时top=-1
	if (ps->top == ps->capacity)
	{
        //为空就开辟四个空间，不为空，就扩容至二倍
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
 
		if (tmp == NULL)
		{
			printf("malloc fail\n");
			exit(-1);
		}
 
		//将新开辟的内存空间的首地址tmp赋值给a
		ps->a = tmp;
		//更新capacity
		ps->capacity = newCapacity;
	}
 
    //入栈
	ps->a[ps->top] = x;
	//top指向栈顶元素的下一个位置
	ps->top++;
}

在入栈之前，首先需要对顺序栈的空间容量进行检查，这里使用三目运算符进行判断：若当前容量 capacity 为空，则开辟4个数据的内存空间；若当前容量非空但已满，则将 capacity 的大小扩容至 2*capacity。然后调用 realloc 函数开辟新的内存空间，并返回新的内存空间的起始地址 tmp。接着将新开辟的内存空间的起始地址 tmp 赋值给 a，使 a 指向这片新开辟的空间。最后，将 x 插入栈顶位置，并让 top 继续指向栈顶元素的下一个位置。 

3.4 出栈 

//出栈
void StackPop(ST* ps)
{
	//判空
	assert(ps);
 
	//判断栈是否为空
	assert(!StackEmpty(ps));
	
	//出栈
	ps->top--;
}

在出栈之前，首先需要调用 StackEmpty(ps) 函数来判断栈是否为空，若不为空，则可以出栈。出栈操作就是将 top--，这里需要注意的是：出栈的数据还残留在内存中，只是逻辑上被删除了。 

3.5 取栈顶元素 

//取栈顶元素
STDataType StackTop(ST* ps)
{
	//判空
	assert(ps);
 
	//判断栈是否为空
	assert(!StackEmpty(ps));
 
	//取栈顶元素
	return ps->a[ps->top - 1];
}

在取栈顶元素之前，首先需要调用函数 StackEmpty(ps) 判断栈是否为空，若栈不为空则可以取栈顶元素。因为 top 指向栈顶元素的下一个位置，所以 top 需要先进行--，再取栈顶元素。 

 3.6 判断栈是否为空

//判空
bool StackEmpty(ST* ps)
{
	assert(ps);

	return ps->top==0;      //返回栈的top，若为0则为空，非0则不为空；
}

判断一个栈是否为空，若为空则返回 true，否则返回 false。这里需要特别说明的一点是，我们将 top 指向栈顶元素的下一个位置，而非指向栈顶元素本身。 

 注意：

  • 当top初始化为：top=0；此时top指向栈顶元素的下一个位置；
  • 当top初始化为：top=-1；此时top指向栈顶元素。

3.7 栈的大小

//大小
int StackSize(ST* ps)
{
	//判空
	assert(ps);
 
	return ps->top;
}

因为 top 指向栈顶元素的下一个位置，而 top 的下标又是从0开始的，所以 top 所在位置的下标就是所求栈的大小，也就是栈中元素个数。 

3.8 栈的销毁 

//销毁
void StackDestory(ST* ps)
{
	//判空
	assert(ps);
 
	//realloc开辟的空间，需要调用free释放
	free(ps->a);
	ps->a = NULL;
 
	ps->top = ps->capacity = 0;
}

对于栈的销毁，首先需要释放由 realloc 动态申请开辟的内存空间，使用 free 函数进行释放。然后将 top 和 capacity 初始化为0。 

 二、源代码

Stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
​
//这里我们实现的是动态的栈

typedef int STDateType;    //方便数据类型的替换

typedef struct Stack        
{
	STDateType* a;         //动态开辟数组
	int top;               //栈顶
	int capacity;          //容量，方便扩容
}ST;

 
//初始化
void StackInit(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 StackDestory(ST* ps);
Stack.c

#include"Stack.h"

​//初始化
void StackInit(ST* ps)
{
	//判空
	assert(ps);

	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

​​//入栈
void StackPush(ST* ps, STDataType x)
{
	//判空
	assert(ps);
 
	//判断容量是否已满
	//top标识的是最后一个数据的下一个位置，如果想要指向最后一个数据，初始时top=-1
	if (ps->top == ps->capacity)
	{
        //为空就开辟四个空间，不为空，就扩容至二倍
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
 
		if (tmp == NULL)
		{
			printf("malloc fail\n");
			exit(-1);
		}
 
		//将新开辟的内存空间的首地址tmp赋值给a
		ps->a = tmp;
		//更新capacity
		ps->capacity = newCapacity;
	}
 
    //入栈
	ps->a[ps->top] = x;
	//top指向栈顶元素的下一个位置
	ps->top++;
}

​​//出栈
void StackPop(ST* ps)
{
	//判空
	assert(ps);
 
	//判断栈是否为空
	assert(!StackEmpty(ps));
	
	//出栈
	ps->top--;
}

​​//取栈顶元素
STDataType StackTop(ST* ps)
{
	//判空
	assert(ps);
 
	//判断栈是否为空
	assert(!StackEmpty(ps));
 
	//取栈顶元素
	return ps->a[ps->top - 1];
}

​​//判空
bool StackEmpty(ST* ps)
{
	assert(ps);

	return ps->top==0;      //返回栈的top，若为0则为空，非0则不为空；
}

​​//大小
int StackSize(ST* ps)
{
	//判空
	assert(ps);
 
	return ps->top;
}

​​//销毁
void StackDestory(ST* ps)
{
	//判空
	assert(ps);
 
	//realloc开辟的空间，需要调用free释放
	free(ps->a);
	ps->a = NULL;
 
	ps->top = ps->capacity = 0;
}
​
test.c

 
#include"Stack.h"
 
void TestStack()
{
	ST st;
 
	//初始化
	StackInit(&st);
 
	//入栈
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);
    StackPush(&st, 6);
    StackPush(&st, 7);

	//出栈
	while (!StackEmpty(&st))
	{
		//读取栈顶元素
		printf("%d ",StackTop(&st));
		
		//出栈
		StackPop(&st);
	}
	printf("\n");
 
	//销毁
	StackDestory(&st);
}
 
int main()
{
	TestStack();
 
	return 0;
}

   本期的内容不多，相信大家学起来也相对容易，提前透露一下下：我们下期来玩队列哈~如果你们觉得本篇文章对自己有所帮助，给博主留下三连支持噢，你的支持是我创作的最大动力！那我们下期再会啦~

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

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

相关文章

InnoDB架构：磁盘篇

InnoDB架构：磁盘篇

InnoDB架构&#xff1a;磁盘篇 InnoDB是MySQL数据库中默认的存储引擎&#xff0c;它为数据库提供了事务安全型&#xff08;ACID兼容&#xff09;、行级锁定和外键支持等功能。InnoDB的架构设计优化了对于读取密集和写入密集型应用的性能表现&#xff0c;是一个高度优化的存储系…
阅读更多...
ctf.show_web13

ctf.show_web13

上传一句话木马 1.php文件&#xff0c;显示 再改后缀为.jpg&#xff0c;显示错误文件大小 用dirsearch扫一下 备份文件.bak 下载文件源码 <?php header("content-type:text/html;charsetutf-8");$filename $_FILES[file][name];$temp_name $_FILES[file][tm…
阅读更多...
C++项目 -- 负载均衡OJ（一）comm

C++项目 -- 负载均衡OJ（一）comm

C项目 – 负载均衡OJ&#xff08;一&#xff09;comm 文章目录 C项目 -- 负载均衡OJ&#xff08;一&#xff09;comm一、项目宏观结构1.项目功能2.项目结构 二、comm公共模块1.util.hpp2.log.hpp 一、项目宏观结构 1.项目功能 本项目的功能为一个在线的OJ&#xff0c;实现类似…
阅读更多...
【第十五届蓝桥杯大赛软件赛省赛】———— C/C++ 大学B组

【第十五届蓝桥杯大赛软件赛省赛】———— C/C++ 大学B组

蓝桥杯2024年15届省赛b组原题献上
阅读更多...
普通人做抖音小店真的能赚钱吗？可以，但更取决于个人

普通人做抖音小店真的能赚钱吗？可以，但更取决于个人

大家好&#xff0c;我是电商花花。 现在做抖音小店的基本上都是一些新商家&#xff0c;对于我们众多零基础的朋友来说&#xff0c;是期待也是一份挑战。 抖音小店作为一个充满机会的新兴平台&#xff0c;许多人都欣喜的投入其中&#xff0c;期望能够借此来改变自己的命运&…
阅读更多...
【教程】ubuntu20.04 下配置 Charm-crypto 0.5 实验环境

【教程】ubuntu20.04 下配置 Charm-crypto 0.5 实验环境

目录 前言先决条件基本依赖安装准备好 gcc&#xff0c;make 和 perl准备好 m4&#xff0c;flex&#xff0c;bison 和 libssl-dev安装 Python3.x&#xff0c;pip3 和 pyparsing 安装 OpenSSL安装 GMP5.x安装 PBC安装 Charm-crypto5.0安装开发环境检验 Charm-crypto5.0 安装成功参…
阅读更多...
跨国公司网络优化新选择：SD-WAN解决方案

跨国公司网络优化新选择：SD-WAN解决方案

随着全球化的加速推进&#xff0c;跨国企业纷纷实施跨国战略&#xff0c;然而&#xff0c;在各地建立分支机构、数据中心的过程中&#xff0c;往往面临网络性能差异大、数据传输效率低下等问题。在这样的背景下&#xff0c;SD-WAN成为跨国公司网络解决方案的优选。 跨国企业对于…
阅读更多...
IO、存储、硬盘、文件系统相关常识

IO、存储、硬盘、文件系统相关常识

目录 IO 文件系统 文件在硬盘上的存储 IO IO&#xff0c;就是Input和Output&#xff0c;即输入和输出操作。我们的电脑可以通过网络下载文件&#xff0c;也可以通过网络上传文件。通过网络下载文件就是输入操作&#xff0c;上传文件就是输出。如何区分输入和输出呢&#xf…
阅读更多...
imgcat 工具

imgcat 工具

如果经常在远程服务器或嵌入式设备中操作图片&#xff0c;要查看图片效果&#xff0c;就要先把图片dump到本地&#xff0c;比较麻烦。可以使用这个工具&#xff0c;直接在终端上显示。类似于这种效果。 imgcat 是一个终端工具&#xff0c;使用 iTerm2 内置的特性&#xff0c;允…
阅读更多...
精益思维驱动人工智能革新：理论到实践的跃迁之旅

精益思维驱动人工智能革新：理论到实践的跃迁之旅

随着科技的飞速发展&#xff0c;人工智能&#xff08;AI&#xff09;已成为引领未来的关键力量。在这个变革的时代&#xff0c;如何将精益思维与人工智能相结合&#xff0c;推动AI从理论走向实践&#xff0c;成为行业内外关注的焦点。本文&#xff0c;天行健精益生产顾问将分享…
阅读更多...
陇剑杯 流量分析 webshell CTF writeup

陇剑杯 流量分析 webshell CTF writeup

陇剑杯 流量分析 链接&#xff1a;https://pan.baidu.com/s/1KSSXOVNPC5hu_Mf60uKM2A?pwdhaek 提取码&#xff1a;haek目录结构 LearnCTF ├───LogAnalize │ ├───linux简单日志分析 │ │ linux-log_2.zip │ │ │ ├───misc日志分析 │ │ …
阅读更多...
阿里云优惠券种类介绍及领取教程详解

阿里云优惠券种类介绍及领取教程详解

随着互联网技术的快速发展&#xff0c;越来越多的企业和个人开始将业务和数据迁移到云端。阿里云作为国内领先的云服务提供商&#xff0c;为广大用户提供了丰富多样的云产品和服务。为了回馈用户&#xff0c;阿里云经常推出各种优惠活动&#xff0c;其中优惠券就是其中一种常见…
阅读更多...
记录一下我hive连不上DataGrip的问题

记录一下我hive连不上DataGrip的问题

用户名和密码都没问题&#xff0c;但报如下这个错误 原因&#xff1a;是因为我在linux上没启hiveserver2服务 解决&#xff1a; [atguiguhadoop102 hadoop]$ hiveserver2 which: no hbase in (/usr/local/bin:/usr/bin:/usr/local/sbin:/usr/sbin:/opt/module/jdk1.8…
阅读更多...
第19天：信息打点-小程序应用解包反编译动态调试抓包静态分析源码架构

第19天：信息打点-小程序应用解包反编译动态调试抓包静态分析源码架构

第十九天 本课意义 1.如何获取到目标小程序信息 2.如何从小程序中提取资产信息 一、Web&备案信息&单位名称中发现小程序 1.国内主流小程序平台 微信 百度 支付宝 抖音头条 2.小程序结构 1.主体结构 小程序包含一个描述整体程序的app和多个描述各自页面的page …
阅读更多...
RAG算法优化+新增代码仓库支持，CodeGeeX的@repo功能效果提升

RAG算法优化+新增代码仓库支持，CodeGeeX的@repo功能效果提升

CodeGeeX在升级到第三代模型时&#xff0c;就引入了RAG检索增强生成的能力。即模型会根据检索到的相关背景知识生成回答&#xff0c;大幅减轻生成内容的幻觉性。在CodeGeeX插件中&#xff0c;是通过侧边栏对话框中输入“repo”触发 RAG 技术。用户可以对开源代码仓库进行提问&a…
阅读更多...
HG泄露（ctfhub）

HG泄露（ctfhub）

工具准备&#xff1a;dirsearch、dvcs-ripper 网络安全之渗透测试全套工具篇&#xff08;内含安装以及使用方法&#xff09;_dvcs-ripper-CSDN博客 dvcs-ripper&#xff1a;一款perl的版本控制软件信息泄露利用工具&#xff0c;支持bzr、cvs、git、hg、svn... tree //树状…
阅读更多...
突破编程_前端_SVG（使用 svg-pan-zoom 库进行平移与缩放）

突破编程_前端_SVG（使用 svg-pan-zoom 库进行平移与缩放）

1 svg-pan-zoom 概述 svg-pan-zoom 是一个轻量级、高性能且易于使用的 JavaScript 库&#xff0c;专为增强 SVG 图像的浏览体验而设计。它提供了平移和缩放功能&#xff0c;使用户能够无缝探索大型或复杂的 SVG 图形。这个库允许用户对SVG图像进行交互操作&#xff0c;包括缩放…
阅读更多...
App怎么创建百度百科词条

App怎么创建百度百科词条

创建一个App的百度百科词条可以帮助提高App的知名度和权威性&#xff0c;以下是详细的创建步骤和注意事项&#xff1a; 创建步骤 注册百度账号&#xff1a;首先&#xff0c;你需要有一个百度账号&#xff0c;如果没有&#xff0c;你需要按照步骤申请一个&#xff0c;这一步骤是…
阅读更多...
【ENSP】华为三层交换机配置AAA认证，开启telnet服务

【ENSP】华为三层交换机配置AAA认证，开启telnet服务

配置步骤 1.给交换机配置ip地址&#xff0c;以便登陆 2.配置AAA&#xff0c;用户名&#xff0c;密码&#xff0c;服务类型&#xff0c;用户权限 3.配置接入设备的数量 4.开启telnet服务 LSW2交换机配置 u t m #关闭提示 sys …
阅读更多...
[Linux]--关于进程控制

[Linux]--关于进程控制

进程创建,fork/vfork 在linux中fork函数是非常重要的函数&#xff0c;它从已存在进程中创建一个新进程。新进程为子进程&#xff0c;而原进程为父进程。 #include <unistd.h> pid_t fork(void); 返回值&#xff1a;自进程中返回0&#xff0c;父进程返回子进程id&#x…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站