一文了解栈

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

  • 前言
  • 一、栈是什么？
  • 二、栈的实现思路
    • 1.顺序表实现
    • 2.单链表实现
    • 3.双向链表实现
  • 三、接口函数的实现
    • 1.栈的定义
    • 2.栈的初始化
    • 3.栈的销毁
    • 4.入栈
    • 5.出栈
    • 6.返回栈顶元素
    • 7.判空
    • 8.返回栈中数据个数
  • 四、文件总览
    • 1.头文件
    • 2.功能函数
    • 3.测试文件
  • 总结

在这里插入图片描述

前言

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

一、栈是什么？

堆栈又名栈（stack），它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
在这里插入图片描述
在这里插入图片描述

二、栈的实现思路

1.顺序表实现

代码如下（示例）：

typedef struct StackList
{
    STDataType* a; //指向动态开辟的空间
    int top; //栈顶所在下标的下一位（也可以指向栈顶）
    int capacity;//栈容量
}ST;

在这里插入图片描述

2.单链表实现

代码如下（示例）：

typedef struct StackNode
{
    STDataType x;//数据
    StackNode* next;//指针域，指向下一结点
}ST;
struct Stack
{
    ST* phead;//指向第一个结点
    ST* ptail;//指向尾结点
}

在这里插入图片描述

3.双向链表实现

typedef struct StackNode
{
    STDataType x;//数据
    StackNode* next;//指向下一结点
    StackNode* prev;//指向上一结点
}ST;
struct Stack
{
    ST* phead;//指向第一个结点
    ST* ptail;//指向尾结点
}

在这里插入图片描述
在这里我们推荐采用顺序表来实现对栈的操作，原因如下：

  1. 栈的特性利用了顺序表尾插尾删效率高的特性，虽然有时需要扩容，但是链表创建结点也同样需要成本，而顺序表扩容频率不像链表一样如此频繁。链表频繁开辟节点也是很耗时的。
  2. 我们知道CPU与主存速度上存在巨大差距，为了提高效率，CPU和主存之间还存在着高速缓存。 CPU访问缓存的速度是快于主存。每次CPU取数据时会访问缓存看看存不存在所需的数据，如果不存在才会访问主存，然后将数据所在的内存块加载到缓存中。由于顺序表空间是连续的，根据缓存的空间局部性原理，采用顺序表命中率会高于链表，所以效率高。

三、接口函数的实现

1.栈的定义

typedef int STDataType;
typedef struct Stack 
{
	STDataType* a;//动态开辟内存
	int top;//栈顶的下一位
	int capacity;栈的容量
}ST;

这里top定义为栈顶下一位是为了下面下表访问方便，也可以定义为指向栈顶的top可以根据个人需要决定。

2.栈的初始化

void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->capacity = 0;
	pst->top = 0;
}

初始化时，空间a先置空指针，capacity和top置零，这是栈没有数据，top指向0，也确实是栈顶的下一位。

3.栈的销毁

void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}

先对pst进行assert断言，再对开辟的空间进行释放，将指针置零，capacity和top置零即可。

4.入栈

void STPush(ST* pst, STDataType x)
{
	assert(pst);
	if (pst->capacity == pst->top)
	{
		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		STDataType*tmp=(STDataType*)realloc(pst->a, newcapacity*sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}

入栈需要注意的点是判断是否容量够用，当capacity和top相等时存满，需要扩充。在扩充时需要判断原容量是不是0，这里进行一个三目操作符判断。之后就是realloc扩容，最后将相应的capacity和top修改就行。

5.出栈

void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}

出栈时应判断栈是否为空，所以这里除了判断pst的有效性，还要判断top的位置。最后让top向前移一位就进行了出栈。

6.返回栈顶元素

STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top-1];
}

判断pst有效性和栈是否为空，再将栈顶的元素返回即可。

7.判空

bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}

这里需要返回bool类型，需要加<stdbool.h>头文件。当top为零时栈为空，返回true，否则返回false。

8.返回栈中数据个数

int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

这里因为我们的top指向栈顶数据的下一位，所以top即为数据个数。返回即可。

四、文件总览

1.头文件

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

typedef int STDataType;
typedef struct Stack 
{
	STDataType* a;
	int top;
	int capacity;
}ST;

// 初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);

// 入栈  出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);

// 取栈顶数据
STDataType STTop(ST* pst);

// 判空
bool STEmpty(ST* pst);
// 获取数据个数
int STSize(ST* pst);

2.功能函数

#include"Stack.h"

void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->capacity = 0;
	pst->top = 0;
}

void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}

void STPush(ST* pst, STDataType x)
{
	assert(pst);
	if (pst->capacity == pst->top)
	{
		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		STDataType*tmp=(STDataType*)realloc(pst->a, newcapacity*sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}

void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}

STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top-1];
}

bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}

int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

3.测试文件

int main()
{
	// 入栈：1 2 3 4
	// 出栈：4 3 2 1  /  2 4 3 1
	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);

	printf("%d ", STTop(&s));
	STPop(&s);

	STPush(&s, 3);
	STPush(&s, 4);

	while (!STEmpty(&s))
	{
		printf("%d ", STTop(&s));
		STPop(&s);
	}

	STDestroy(&s);
}

在这里插入图片描述

总结

这就是本期文章的全部内容，期待你的一键三连和评论。

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

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

相关文章

MFC列表控件用ADO添加数据实例

MFC列表控件用ADO添加数据实例

1、本程序基于前期我的博客文章《MFC用ADO连接ACESS数据库实例(免费源码下载)》 程序功能通过编辑框、组合框实时将数据写入ACESS数据库并在列表控件上显示。 2、在主界面资源视图上加上一个按钮控件、两个静态文本、一个编辑框IDC_EDIT1变量名name、一个组合框IDC_COMBO1变量名…
阅读更多...
【从零开始学习Minio | 第一篇】快速介绍什么是Minio

【从零开始学习Minio | 第一篇】快速介绍什么是Minio

前言&#xff1a; 在当今数字化时代&#xff0c;数据的存储和管理已经成为了企业发展中的关键一环。随着数据量的不断增长和数据安全性的日益受到重视&#xff0c;传统的数据存储解决方案往往面临着诸多挑战。为了应对这些挑战&#xff0c;云存储技术应运而生&#xff0c;并在…
阅读更多...
VMware下Ubuntu的安装教程

VMware下Ubuntu的安装教程

文章目录 一、Ubuntu如何下载1.下载官方地址https://ubuntu.com/2.点选Ubuntu服务器版本3.点击下载Ubuntu服务器版本iso镜像二、VMware安装Ubuntu服务器系统1.创建虚拟机2.选择下载好的Ubuntu服务器镜像3.创建安装完成三、Ubuntu Server如何设置1.Ubuntu Server没有中文所以全都…
阅读更多...
Skywalking数据持久化与自定义链路追踪

Skywalking数据持久化与自定义链路追踪

学习本篇文章之前首先要了解一下Sky walking的基础知识 分布式链路追踪工具Skywalking详解 一&#xff0c;Sky walking数据持久化 Sky walking提供了es&#xff0c;MySQL等数据持久化方案&#xff0c;默认使用h2基于内存的数据库&#xff0c;重启之后数据即会丢失。 在实际工…
阅读更多...
asp.net成绩查询系统

asp.net成绩查询系统

说明文档 运行前附加数据库.mdf&#xff08;或sql生成数据库&#xff09; 主要技术&#xff1a; 基于asp.net架构和sql server数据库 功能模块&#xff1a; asp.net成绩查询系统 学生功能有查看成绩和修改账号密码等 后台管理员可以进行用户管理 管理员添加管理员查询注…
阅读更多...
element-plus el-time-picker 时间段选择（可多选）

element-plus el-time-picker 时间段选择（可多选）

实现一个如图的时间段选择器 处理好时间回显逻辑&#xff0c;组件内[‘’,‘’],后端数据[{startTime:‘’,endTime:‘’}]处理好加和减的显示逻辑 <template><div><div v-for"(item, index) in currentChoose" :key"index" class"fl…
阅读更多...
[Java EE] 多线程(九):ReentrantLock,Semaphore,CountDownLatch与线程安全的集合类(多线程完结)

[Java EE] 多线程(九):ReentrantLock,Semaphore,CountDownLatch与线程安全的集合类(多线程完结)

&#x1f338;个人主页:https://blog.csdn.net/2301_80050796?spm1000.2115.3001.5343 &#x1f3f5;️热门专栏:&#x1f355; Collection与数据结构 (91平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm1001.2014.3001.5482 &#x1f9c0;Java …
阅读更多...
C++之类与对象

C++之类与对象

1、类声明 2、共有、私有、保护成员。&#xff08;就比如说你一个变量是private的&#xff0c;然后在main函数中&#xff0c;就调用不了&#xff0c;只能在这个类.cpp中调用&#xff09; 3、数据抽象和封装 4、内联函数 内存体积会增大&#xff0c;以空间换时间&#xff1a;编…
阅读更多...
php使用服务器端和客户端加密狗环境部署及使用记录（服务器端windows环境下部署、linux环境宝塔面板部署、客户端部署加密狗）

php使用服务器端和客户端加密狗环境部署及使用记录（服务器端windows环境下部署、linux环境宝塔面板部署、客户端部署加密狗）

php使用服务器端和客户端加密狗环境部署及使用记录 ViKey加密狗环境部署1.windows环境下部署开发文档验证代码提示Fatal error: Class COM not found in 2.linux环境下部署&#xff08;宝塔面板&#xff09;开发文档验证代码提示Fatal error: Uncaught Error: Call to undefine…
阅读更多...
【软测学习笔记】Python入门Day02

【软测学习笔记】Python入门Day02

&#x1f31f;博主主页&#xff1a;我是一只海绵派大星 &#x1f4da;专栏分类&#xff1a;软件测试笔记 &#x1f4da;参考教程&#xff1a;黑马教程❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ python安装 1、进入Python的官方下载页面&#xff1a; Download Python | Py…
阅读更多...
Java+SpringBoot+JSP实现在线心理评测与咨询系统

Java+SpringBoot+JSP实现在线心理评测与咨询系统

前言介绍 随着互联网技术的高速发展&#xff0c;人们生活的各方面都受到互联网技术的影响。现在人们可以通过互联网技术就能实现不出家门就可以通过网络进行系统管理&#xff0c;交易等&#xff0c;而且过程简单、快捷。同样的&#xff0c;在人们的工作生活中&#xff0c;也就…
阅读更多...
用PowerPoint创建毛笔字书写动画

用PowerPoint创建毛笔字书写动画

先看看下面这个毛笔字书写动画&#xff1a; 这个动画是用PowerPoint创建的。下面介绍创建过程。 1、在任何一款矢量图片编辑软件中创建一个图片&#xff0c;用文字工具输入文字内容。我用的是InkScape。排好版后将图片保存为.svg格式的矢量图片文件。 2、打开PowerPoint&…
阅读更多...
RTT潘多拉开发板上实现电源管理

RTT潘多拉开发板上实现电源管理

简介 随着物联网(IoT)的兴起&#xff0c;产品对功耗的需求越来越强烈。作为数据采集的传感器节点通常需要在电池供电时长期工作&#xff0c;而作为联网的SOC也需要有快速的响应功能和较低的功耗。 在产品开发的起始阶段&#xff0c;首先考虑是尽快完成产品的功能开发。在产品…
阅读更多...
C++变量的作用域与存储类型

C++变量的作用域与存储类型

一 变量的作用域和存储类型 1 变量的作用域(Scope) 指在源程序中定义变量的位置及其能被读写访问的范围分为局部变量(Local Variable)和全局变量(Global Variable) 1&#xff09;局部变量(Local Variable) 在语句块内定义的变量 形参也是局部变量 特点&#xff1a; 生存期是…
阅读更多...
web 基础之 HTTP 请求

web 基础之 HTTP 请求

web 基础 网上冲浪 就是在互联网(internet)上获取各种信息&#xff0c;进行工作&#xff0c;或者娱乐&#xff0c;他的英文表示surfing the Internet&#xff0c;因 “surfing”d的意思是冲浪&#xff0c;即成为网上冲浪&#xff0c;这是一种形象说法&#xff0c; 也是一个非…
阅读更多...
交易复盘-20240507

交易复盘-20240507

仅用于记录当天的市场情况&#xff0c;用于统计交易策略的适用情况&#xff0c;以便程序回测 短线核心&#xff1a;不参与任何级别的调整&#xff0c;采用龙空龙模式 一支股票 10%的时候可以操作&#xff0c; 90%的时间适合空仓等待 蔚蓝生物 (5)|[9:25]|[36187万]|4.86 百合花…
阅读更多...
SpringBootWeb入门

SpringBootWeb入门

SpringBoot可以帮助我们快速的构建应用程序、简化开发、提高效率 创建SpringBoot工程&#xff0c;并勾选web开发相关依赖 定义HelloController类&#xff0c;添加方法&#xff0c;并添加注解 运行测试 创建SpringBoot工程(联网下载) 在File里面点击new Module 点击next 修…
阅读更多...
Linux\_c输出

Linux\_c输出

第一条Linux_c输出 初界面 : ls # 显示目录下的文件cd # 进入到某个目录 # 比如 我进入了Codels # 发现没有显示, 说明为文件下为空vim cpucdoe.c # 创建一个 .c的源码文件进入到了vim的编辑界面: i # 按i 就可以进行编辑 , 下面显示插入标识在编辑模式下, 可以通…
阅读更多...
计算图：深度学习中的链式求导与反向传播引擎

计算图：深度学习中的链式求导与反向传播引擎

在深度学习的世界中&#xff0c;计算图扮演着至关重要的角色。它不仅是数学计算的图形化表示&#xff0c;更是链式求导与反向传播算法的核心。本文将深入探讨计算图的基本概念、与链式求导的紧密关系及其在反向传播中的应用&#xff0c;旨在为读者提供一个全面而深入的理解。 计…
阅读更多...
练习项目后端代码解析切面篇（Aspect）

练习项目后端代码解析切面篇（Aspect）

前言 之前注解篇时我说&#xff0c;通常情况下一个自定义注解一般对应一个切面&#xff0c;虽然项目里的切面和注解个数相同&#xff0c;但是好像有一个名字看起来并不对应&#xff0c;无所谓&#xff0c;先看了再说。 ExceptionLogAspect切面 我在里面做了具体注释&#x…
阅读更多...
最新文章

Copyright @ 2022~2023

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