【数据结构】线性表之《栈》超详细实现

栈

  • 一.栈的概念及结构
  • 二.顺序栈与链栈
    • 1.顺序栈
    • 2.链栈
      • 1.单链表栈
      • 2.双链表栈
  • 三.顺序栈的实现
    • 1.栈的初始化
    • 2.检查栈的容量
    • 3.入栈
    • 4.出栈
    • 5.获取栈顶元素
    • 6.栈的大小
    • 7.栈的判空
    • 8.栈的清空
    • 9.栈的销毁
  • 四.模块化源代码
    • 1.Stack.h
    • 2.Stack.c
    • 3.test.c

一.栈的概念及结构

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

二.顺序栈与链栈

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上
插入数据的代价比较小。那是为什么？且听下文分解。

1.顺序栈

在这里插入图片描述

2.链栈

1.单链表栈

在这里插入图片描述

将栈顶与栈低换个位置可以解决该问题，如下图：

在这里插入图片描述

2.双链表栈

在这里插入图片描述

  1. 由于双向链表比单链表多一个指针，基于节省内存的原由单链表优于双向链表。
  2. 数组的效率更优于单链表，原因：链表每一次插入一个数据都要申请一个节点，每次删除一个数据都要释放一个节点，且顺序栈包含数据+容量+栈顶，而链栈包含数据+指针，每个数据都要包含指针，顺序栈较于连栈会省一些内存。

接下来我将实现最优的——>顺序栈

三.顺序栈的实现

会写顺序表，那么实现顺序栈会非常轻松，这里就不一一介绍了，直接上代码。

1.栈的初始化

void StackInit(ST* ps)
{
	assert(ps);//断言

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

2.检查栈的容量

void CheckCapacity(ST* ps)
{
	assert(ps);
	//栈满
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)//空间开辟失败
		{
			perror("realloc fail!");
			exit(-1);//退出程序
		}
		//空间开辟成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

3.入栈

void StackPush(ST* ps, STDataType x)
{
	assert(ps);

	CheckCapacity(ps);
	ps->arr[ps->top] = x;
	ps->top++;
}

4.出栈

void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);//栈空，无法出栈，否则下标越界

	ps->top--;
}

5.获取栈顶元素

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

	return ps->arr[ps->top - 1];
}

6.栈的大小

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

7.栈的判空

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

8.栈的清空

void StackClear(ST* ps)
{
	assert(ps);

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

9.栈的销毁

void StackDestory(ST* ps)
{
	assert(ps);

	StackClear(ps);
	free(ps->arr);
	ps->arr = NULL;
}

四.模块化源代码

1.Stack.h

//#pragma once 防止头文件被重复包含
#ifndef __STACK_H__
#define __STACK_H__

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

typedef int STDataType;

typedef struct Stack
{
	STDataType* arr; //栈空间的首地址
	int top;         //栈顶
	int capacity;    //容量
}ST;

void StackInit(ST* ps);//栈的初始化

void CheckCapacity(ST* ps);//检查栈的容量

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

void StackPop(ST* ps);//出栈

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

int StackSize(ST* ps);//获取栈的长度

bool StackEmpty(ST* ps);//栈的判空

void StackClear(ST* ps);//栈的清空

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

#endif

2.Stack.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Stack.h"

void StackInit(ST* ps)
{
	assert(ps);//断言

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

void CheckCapacity(ST* ps)
{
	assert(ps);
	//栈满
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)//空间开辟失败
		{
			perror("realloc fail!");
			exit(-1);//退出程序
		}
		//空间开辟成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

void StackPush(ST* ps, STDataType x)
{
	assert(ps);

	CheckCapacity(ps);
	ps->arr[ps->top] = x;
	ps->top++;
}

void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);//栈空，无法出栈，否则下标越界

	ps->top--;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

	return ps->arr[ps->top - 1];
}

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

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

void StackClear(ST* ps)
{
	assert(ps);

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

void StackDestory(ST* ps)
{
	assert(ps);

	StackClear(ps);
	free(ps->arr);
	ps->arr = NULL;
}

3.test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Stack.h"

enum
{
	EXIT,
	PUSH,
	POP,
	TOP,
	SIZE,
	EMPTY,
	CLEAR
};

void Menu()
{
	printf("***************栈**************\n");
	printf("****1.入栈           2.出栈****\n");
	printf("****3.栈顶           4.大小****\n");
	printf("****5.判空           6.清空****\n");
	printf("****0.退出               ******\n");
	printf("*******************************\n");
}

int main()
{
	ST st;
	StackInit(&st);
	int select = 0;
	STDataType value;
	bool flag;
	do
	{
		Menu();
		printf("请选择您的操作：");
		scanf("%d", &select);
		switch (select)
		{
		case EXIT:
			printf("退出栈!\n");
			break;
		case PUSH:
			printf("请输入您要入栈的值：");
			scanf("%d", &value);
			StackPush(&st, value);
			break;
		case POP:
			StackPop(&st);
			break;
		case TOP:
			value = StackTop(&st);
			printf("栈顶元素：%d\n", value);
			break;
		case SIZE:
			printf("栈的大小为：%d\n", StackSize(&st));
			break;
		case EMPTY:
			flag = StackEmpty(&st);
			if (flag)
			{
				printf("栈为空!\n");
			}
			else
			{
				printf("栈不为空!\n");
			}
			break;
		case CLEAR:
			StackClear(&st);
			break;
		default:
			printf("输入错误，请重新输入！\n");
			break;
		}
	} while (select);
	StackDestory(&st);
	return 0;
}

创作不易，如果能帮到你的话能赏个三连吗？感谢啦！！！

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

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

相关文章

Azure vs. AssemblyAI：深度解析语音转文本服务的对决

Azure vs. AssemblyAI：深度解析语音转文本服务的对决

在技术飞速发展的今天&#xff0c;API已成为连接不同软件和服务的关键桥梁。对于需要语音转文本功能的应用&#xff0c;我们对比了两个广受欢迎的API接口&#xff1a;Azure 语音转文本和AssemblyAI AI语音转文本。 Azure 语音转文本 Azure 语音转文本提供快速、准确的语音转文本…
阅读更多...
ArrayList知识点(面试)

ArrayList知识点(面试)

上一篇我们说了hashmap的相关知识点&#xff0c;这一篇我们再说一些ArrayList的相关知识&#xff0c;因为ArrayList也是我们项目中比较常用的。 ArrayList(底层是数组) 底层工作原理 首先&#xff0c;在构造ArrayList的时候会先看有没有指定容量&#xff0c;如果没有&#xf…
阅读更多...
音视频开发29 FFmpeg 音频编码- 流程以及重要API,该章节使用AAC编码说明

音视频开发29 FFmpeg 音频编码- 流程以及重要API,该章节使用AAC编码说明

此章节的一些参数&#xff0c;需要先掌握aac的一些基本知识&#xff1a;​​​​​​aac音视频开发13 FFmpeg 音频 --- 常用音频格式AAC&#xff0c;AAC编码器&#xff0c; AAC ADTS格式 。_ffmpeg aac data数据格式-CSDN博客 目的&#xff1a; 从本地⽂件读取PCM数据进⾏AAC格…
阅读更多...
FL论文专栏｜设备异构、异步联邦

FL论文专栏｜设备异构、异步联邦

论文&#xff1a;Asynchronous Federated Optimization&#xff08;12th Annual Workshop on Optimization for Machine Learning&#xff09; 链接 实现Server的异步更新。每次Server广播全局Model的时候附带一个时间戳&#xff0c;Client跑完之后上传将时间戳和Model同时带回…
阅读更多...
【办公类-50-01】20240620自主游戏观察记录表19周内容打乱

【办公类-50-01】20240620自主游戏观察记录表19周内容打乱

背景需求&#xff1a; 又到了期末&#xff0c;各种班级资料需要提交。 有一份自主游戏观察记录需要写19周&#xff08;每周2次&#xff09;的观察记录&#xff0c;并根据参考书填写一级、三级、五级的评价指标。 去年中六班的时候&#xff0c;我很认真的手写了21周的户外游戏…
阅读更多...
基于CST的连续域束缚态（BIC）设计与机制研究

基于CST的连续域束缚态（BIC）设计与机制研究

关键词&#xff1a;太赫兹&#xff0c;超表面&#xff0c;连续域束缚态&#xff0c;CST&#xff0c;高Q 束缚态的概念最先出现于量子力学中&#xff0c;当粒子被势场约束在特定的区域内运动&#xff0c;即在无限远处波函数等于零的态叫束缚态&#xff0c;例如势阱中的粒子就处…
阅读更多...
Map集合之HashMap细说

Map集合之HashMap细说

最近在看面试题&#xff0c;看到了hashmap相关的知识&#xff0c;面试中问的也挺多的&#xff0c;然后我这里记录下来&#xff0c;供大家学习。 Hashmap为什么线程不安全 jdk 1.7中&#xff0c;在扩容的时候因为使用头插法导致链表需要倒转&#xff0c;从而可能出现循环链表问…
阅读更多...
百度ai人脸识别项目C#

百度ai人脸识别项目C#

一、项目描述 本项目通过集成百度AI人脸识别API&#xff0c;实现了人脸检测和识别功能。用户可以上传图片&#xff0c;系统将自动识别人脸并返回识别结果。 二、开发环境 Visual Studio 2019或更高版本.NET Framework 4.7.2或更高版本AForge.NET库百度AI平台人脸识别API 三、…
阅读更多...
Django 模版变量

Django 模版变量

1&#xff0c;模版变量作用 模板变量使用“{{ 变量名 }}” 来表示模板变量前后可以有空格&#xff0c;模板变量名称&#xff0c;可以由数字&#xff0c;字母&#xff0c;下划线组成&#xff0c;不能包含空格模板变量还支持列表&#xff0c;字典&#xff0c;对象 2&#xff0c;…
阅读更多...
一文搞懂Linux信号【下】

一文搞懂Linux信号【下】

目录 &#x1f6a9;引言 &#x1f6a9;阻塞信号 &#x1f6a9;信号保存 &#x1f6a9;信号捕捉 &#x1f6a9;操作信号集 1.信号集操作函数 2.其它操作函数 &#x1f6a9;总结&#xff1a; &#x1f6a9;引言 在观看本博客之前&#xff0c;建议大家先看一文搞懂Linux信…
阅读更多...
React hydrateRoot如何实现

React hydrateRoot如何实现

React 服务器渲染中&#xff0c;hydrateRoot 是核心&#xff0c;它将服务器段的渲染与客户端的交互绑定在一起&#xff0c;我们知道 React 中 Fiber Tree 是渲染的的核心&#xff0c;那么 React 是怎么实现 hydrateRoot 的呢&#xff1f;首先我们验证一下&#xff0c;hydrateRo…
阅读更多...
期货交易豆粕品种详细分析

期货交易豆粕品种详细分析

文章目录 1、豆粕期货标准&#xff08;2024年6月22号数据&#xff09;2、豆粕是什么3、豆粕1、5、9合约区别4、影响豆粕的价格因素1、大豆的供应情况。2、豆粕的季节性3、油粕比&#xff08;豆油和豆粕的价格关系 &#xff09; 5、美国大豆的生产/库存炒作6、豆粕双方&#xff…
阅读更多...
uniapp实现路由拦截——遇到问题（三）

uniapp实现路由拦截——遇到问题（三）

uniapp路由拦截开发过程中遇到问题 文章目录 uniapp路由拦截开发过程中遇到问题App 无法退出应用监听返回数据结构解决方式模拟原生物理返回键提示不提示&#xff0c;直接退出应用 微信小程序 登录成功返回页面报错效果图不同平台来源页面数据结构解决方式 App 无法退出应用 安…
阅读更多...
2005年上半年软件设计师【上午题】试题及答案

2005年上半年软件设计师【上午题】试题及答案

文章目录 2005年上半年软件设计师上午题--试题2005年上半年软件设计师上午题--答案2005年上半年软件设计师上午题–试题
阅读更多...
C++/Qt 小知识记录7

C++/Qt 小知识记录7

工作中遇到的一些小问题&#xff0c;总结的小知识记录&#xff1a;C/Qt 小知识7 编译FFMPEG遇到的问题CMakeLists.txt配置FFMPEG的依赖方式&#xff1a; x264在Windows下编译生成*.libVS编译Qt工程时&#xff0c;遇到提示Change Qt Version的情况在QtOsg的窗口上嵌入子窗口&…
阅读更多...
面试官：请你实现三栏布局并且优先加载中间内容 我：稳啦- ̗̀(๑ᵔ⌔ᵔ๑)

面试官：请你实现三栏布局并且优先加载中间内容 我：稳啦- ̗̀(๑ᵔ⌔ᵔ๑)

前言 三栏布局是网页设计中一种经典布局方式&#xff0c;它将页面分为三个垂直部分&#xff1a;左栏、中栏和右栏&#xff0c;三栏在同一行显示。 这种布局模式在很多网站的首页或内容密集型页面中非常常见&#xff0c;因为它能够有效地组织信息&#xff0c;提供良好的用户体…
阅读更多...
【产品应用】一体化步进伺服电机在吊装机器人中的应用

【产品应用】一体化步进伺服电机在吊装机器人中的应用

随着工业自动化和智能制造的发展&#xff0c;吊挂式智能巡检机器人逐渐成为许多工业场景中的重要角色。这类机器人不仅能够提升工作效率&#xff0c;减少人工干预&#xff0c;还能在复杂或危险环境中完成巡检任务。在这些机器人的设计与制造中&#xff0c;一体化步进伺服电机扮…
阅读更多...
jrebel安装使用教程（2022.4.1版本）

jrebel安装使用教程（2022.4.1版本）

本方法适用于jrebel2022.4.1版本&#xff0c;之后的版本不再适用。 1.下载插件 下载地址 2.安装插件 可以通过idea内部安装 也可以将插件解压进idea的安装目录下的plugins。 3.激活 Team URL中填入 https://jrebel.qekang.com/{guid}这里提供两个guid生成地址&#xf…
阅读更多...
Redis学习|Redis基础知识、Redis五大数据类型、Redis三种特殊数据类型、Redis事务

Redis学习|Redis基础知识、Redis五大数据类型、Redis三种特殊数据类型、Redis事务

Redis基础知识 redis默认有16个数据库&#xff0c;并且这个数量可以在conf配置文件中更改 默认使用的是第0个 可以使用 select 进行切换数据库! key *查看数据库所有的key 清除当前数据库 flushdb 清除全部数据库的内容FLUSHALL 为什么redis是6379!(了解一下即可!) Redis 是…
阅读更多...
Elasticsearch如何聚合查询多个统计值，如何嵌套聚合？并相互引用，统计索引中某一个字段的空值率？语法是怎么样的

Elasticsearch如何聚合查询多个统计值，如何嵌套聚合？并相互引用，统计索引中某一个字段的空值率？语法是怎么样的

文章目录 Elasticsearch聚合查询说明空值率查询DSL Elasticsearch聚合基础知识扩展Elasticsearch聚合概念Script 用法Elasticsearch聚合查询语法指标聚合&#xff08;Metric Aggregations&#xff09;桶聚合&#xff08;Bucket Aggregations&#xff09;矩阵聚合&#xff08;Ma…
阅读更多...
最新文章

Copyright @ 2022~2023