当前位置: 首页 > news >正文

数据结构之栈详解

1. 栈的概念以及结构

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

压栈:栈的插入操作叫做进栈/插栈/入栈,入数据在栈顶。

出栈:栈的删除操作叫做出栈。出数据也在栈顶。

2.栈的功能以及实现

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

这里定长的静态栈的结构,实现中一般不实用

//静态栈
typedef int STDataType;#define N 10
typedef struct Stack
{STDataType a[N];int top;
}Stack; 

所以我们主要实现下面的支持动态增长的栈

//支持动态增长的栈
typedef int STDataType;typedef struct Stack
{STDataType* a; int top;         //栈顶int capacity;    //容量
}Stack;

栈所需要实现的一些功能

//栈初始化
void STInit(ST* ps);
//清空栈
void STDestroy(ST* ps);//插入栈
void STPush(ST* ps);
//删除栈元素
void STPop(ST* ps);
//查看栈的大小
int STSize(ST* ps);
//查看栈中有没有元素
bool STEmpty(ST* ps);
//输出栈顶元素
STDataType STTop(ST* ps);

->1. 栈初始化

void STInit(ST* ps)
{assert(ps);ps->a = (ST*)malloc(sizeof(ST) * CAPACITY__SIZE);if (NULL == ps->a){perror("STInit::malloc");return;}//压栈元素的下一个位置ps->top = 0;ps->capacity = CAPACITY__SIZE;
}

->2. 清空栈

//清空栈
void STDestroy(ST* ps)
{free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}

->3. 插入栈

//插入栈
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){ST* Expand = (ST*)realloc(ps->a,sizeof(ST) * ps->capacity * CAPACITY__SIZE);if (NULL == Expand){perror("STPop::malloc");exit(-1);}ps->a = Expand;ps->capacity *= CAPACITY__SIZE;}ps->a[ps->top++] = x;
}

->4. 删除栈元素

//删除栈元素
void STPop(ST* ps)
{assert(ps);assert(!STEmpty);ps->top--;
}

->5. 查看栈的大小

//查看栈的大小
int STSize(ST* ps)
{return ps->top;
}

->6. 查看栈中有没有元素

//查看栈中有没有元素
bool STEmpty(ST* ps)
{return  ps->top == 0;
}

->7.输出栈顶元素

//输出栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty);return ps->a[ps->top - 1];
}

整合以上我们来实现栈,下面是实现栈的完整代码

Stack.h

#define _CRT_SECURE_NO_WARNINGS 1 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>//动态栈
#define CAPACITY__SIZE 4
typedef int STDataType;typedef struct Stack
{int* a;int top;int capacity;
}ST;//栈初始化
void STInit(ST* ps);
//清空栈
void STDestroy(ST* ps);//插入栈
void STPush(ST* ps, STDataType x);
//删除栈元素
void STPop(ST* ps);
//查看栈的大小
int STSize(ST* ps);
//查看栈中有没有元素
bool STEmpty(ST* ps);
//输出栈顶元素
STDataType STTop(ST* ps);

Stack.c

#include "Stack.h"void STInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * CAPACITY__SIZE);if (NULL == ps->a){perror("STInit::malloc");return;}//压栈元素的下一个位置ps->top = 0;ps->capacity = CAPACITY__SIZE;
}//清空栈
void STDestroy(ST* ps)
{free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}//插入栈
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){STDataType* Expand = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity * CAPACITY__SIZE);if (NULL == Expand){perror("STPop::malloc");exit(-1);}ps->a = Expand;ps->capacity *= CAPACITY__SIZE;}ps->a[ps->top++] = x;
}//删除栈元素
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}
//查看栈的大小
int STSize(ST* ps)
{return ps->top;
}//查看栈中有没有元素
bool STEmpty(ST* ps)
{return  ps->top == 0;
}//输出栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}

test.c

#include "Stack.h"int main()
{ST Stack;STInit(&Stack);STPush(&Stack, 1);STPush(&Stack, 2);STPush(&Stack, 3);STPush(&Stack, 4);STPush(&Stack, 5);/*while (!STEmpty(&Stack)){printf("%d->", Stack.a[--Stack.top]);}printf("NULL\n");*/while (!STEmpty(&Stack)){printf("%d ", STTop(&Stack));STPop(&Stack);}printf("\n");STDestroy(&Stack);return 0;
}

测试结果:

相关文章:

数据结构之栈详解

1. 栈的概念以及结构 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶&#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO&#xff08;Last In First Out&#xff09;的原则。 压栈…...

算法:BFS解决 FloodFill 算法

目录 FloodFill 算法 题目一&#xff1a;图像渲染 题目二&#xff1a;岛屿数量 题目三&#xff1a;岛屿的最大面积 题目四&#xff1a;被围绕的区域 FloodFill 算法 在递归搜索回溯中已经说到过 FloodFill 算法了&#xff0c;但是那里是用 dfs 解决的&#xff0c;这里会使…...

Python 中文双引号 “”

Python 中文双引号 “” 1. SyntaxError: invalid character in identifier2. CorrectionReferences 1. SyntaxError: invalid character in identifier print(Albert Einstein once said, “A person who never made a mistake never tried anything new.”) print(Albert Ei…...

以太网(Ethernet)

目录 1. What is Internet?1.1. What is Ethernet?2. TCP/IP3. Physical Layer(PHY)4. Data Link Layer4.1. MAC Sublayer5. Network Layer5.1. IP5.2. ARP6. Transport Layer6.1. UDP6.2. TCP7. Application LayerFPGA实现以太网(一)——以太网简介 网络与路由交换 菜鸟FP…...

Scrcpy adb server version (41) doesn‘t match this client (39); killing...

通过Snap 在Ubuntu上安装 scrcpy之后&#xff0c;启动会导致无法同时 scrcpy和adb logcat 过滤日志 目前最新的安装的platforms-tools下面的adb 版本最新都是 adb 41版本 解决办法&#xff1a; 在这里链接里面 下载 adb 1.0.39 版本&#xff0c;替换 /home/host/Android/Sdk/…...

微服务实战系列之玩转Docker(四)

前言 幸福&#xff0c;就是继续追寻已经拥有的东西。 ——圣奥古斯丁 什么算已经拥有的&#xff1f;比如爱你的人在等你&#xff0c;比如每日热腾腾的三餐&#xff0c;比如身边可爱的同事&#xff0c;又比如此刻的你&#xff0c;看见了这篇博文&#xff08;&#x1f601;&#…...

微信小程序-自定义组件生命周期

一.created 组件实例创建完毕调用。定义在lifetimes对象里。 不能在方法里面更改data对象里面的值&#xff0c;但是可以定义属性值。 lifetimes:{//不能给data设置值created(){this.testaaconsole.log("created") }}二. attached 模板解析完成挂载到页面。 可以更…...

2024年7月23日(samba DNS)

​ 回顾 1、关闭防火墙&#xff0c;关闭selinux systemctl stop firewalld systemctl disable firewalld setenforce 0 2、修改静态IP地址 vim /etc/sysconfig/network-scripts/ifcfg-ens33 #修改uuid的目的是为了保证网络的唯一性 3、重启网络服务 systemctl restart netwo…...

Hyperledger顶级项目特点和介绍

Hyperledger的顶级项目 Hyperledger是Linux基金会主持的开源区块链项目&#xff0c;其目的是推动跨行业的区块链技术的开发和应用。以下是Hyperledger的顶级项目&#xff1a; 1. Hyperledger Fabric 描述&#xff1a;Hyperledger Fabric是一个可扩展的企业级区块链平台&…...

操作系统——笔记(1)

操作系统是管理计算机硬件资源&#xff0c;控制其他程序运行并为用户提供交互操作界面的系统软件的集合&#xff0c;控制和管理着整个计算机系统的硬件和软件资源&#xff0c;是最基本的系统软件。 常见的操作系统&#xff1a;ios、windows、Linux。 计算机系统的结构层次&am…...

isEmpty() 和 isBlank()的区别

isEmpty() 和 isBlank()的区别 平时自己开发的时候没有注意到这个地方,直到实习的时候代码审查的时候发现其用法上两者的不同. isEmpty() public static boolean isEmpty(String str) {return str null || str.length() 0; }isBlank() public static boolean isBlank(Strin…...

scrapy生成爬虫数据为excel

scrapy生成爬虫数据为excel 使用openpyxl&#xff08;推荐&#xff09;安装openpyxl库建一个新的Item Pipeline类在settings.py中启用ExcelPipeline说明 使用scrapy-xlsx首先&#xff0c;安装scrapy-xlsx&#xff1a;然后在Scrapy爬虫中使用管道&#xff1a;说明 要使用Scrapy生…...

vscode debug C++无法输入问题

研究了半天vscode debug c无法输入的问题&#xff0c;原来vscode的文档里面已经记录了。issue都是2020年提的了&#xff0c;还没解决。。。 不过人家也确实给了一个解法&#xff1a;用外部的terminal。 不过怎么看都还不是很方便&#xff0c;所以还是推荐直接使用CodeLLDB插件来…...

MODBUS tcp学习总结

MODBUS TCP协议实例数据帧详细分析_modbus 帧结构-CSDN博客...

【第一天】计算机网络 TCP/IP模型和OSI模型,从输入URL到页面显示发生了什么

TCP/IP模型和OSI模型 这两个模型属于计算机网络的体系结构。 OSI模型是七层模型&#xff0c;从上到下包括&#xff1a; 应用层&#xff0c;表示层&#xff0c;会话层&#xff0c;传输层&#xff0c;网络层&#xff0c;数据链路层&#xff0c;物理层 TCP/IP模型是四层模型&…...

发现FionaAI:免费体验最新的GPT-4o Mini模型!

你现在可以在FionaAI上免费体验OpenAI刚刚发布的GPT-4o Mini模型&#xff01;作为您在Google Chrome中的ChatGPT驱动助手&#xff0c;FionaAI可以随时随地与您对话&#xff0c;帮助您轻松创作和处理文本。 为什么选择GPT-4o Mini&#xff1f; 最新技术&#xff1a;GPT-4o Mini是…...

Linux Gui 窗口对话和窗口操作

zenity 可以实现窗口对话 eg: zenity --error --width 300 --text "Permission denied. Cannot write to the file." ChosenDate$(zenity --calendar --text "Choose a date" --title "How-To Geek Rota" --day 1 --month 9 --year 2019); …...

人工智能驾驶技术:引领未来道路

随着科技的不断进步&#xff0c;人工智能驾驶技术正以惊人的速度改变着我们的交通方式和生活方式。这项技术不仅令人兴奋&#xff0c;还引发了许多关于安全性、道德和法律等方面的深思。本文将探讨人工智能自动驾驶技术的发展现状、应用前景以及对社会的影响。 技术背景与发展…...

管理的核心是管人,管人的核心就是这3条,看懂的是高手

管理的核心是管人&#xff0c;管人的核心就是这3条&#xff0c;看懂的是高手 一&#xff1a;管欲 每个人都有欲望&#xff0c;无可厚非。管理者的任务就是利用欲望&#xff0c;管理欲望&#xff0c;通过欲望来达到管人的目的。 最需要管理的就是以下两种&#xff1a; 1、金…...

代码解读:Diffusion Models中的长宽桶技术(Aspect Ratio Bucketing)

Diffusion Models专栏文章汇总&#xff1a;入门与实战 前言&#xff1a;自从SDXL提出了长宽桶技术之后&#xff0c;彻底解决了不同长宽比的图像输入问题&#xff0c;现在已经成为训练扩散模型必选的方案。这篇博客从代码详细解读如何在模型训练的时候运用长宽桶技术(Aspect Rat…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...