数据结构之栈详解
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. 栈的概念以及结构 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。 压栈…...
算法:BFS解决 FloodFill 算法
目录 FloodFill 算法 题目一:图像渲染 题目二:岛屿数量 题目三:岛屿的最大面积 题目四:被围绕的区域 FloodFill 算法 在递归搜索回溯中已经说到过 FloodFill 算法了,但是那里是用 dfs 解决的,这里会使…...
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之后,启动会导致无法同时 scrcpy和adb logcat 过滤日志 目前最新的安装的platforms-tools下面的adb 版本最新都是 adb 41版本 解决办法: 在这里链接里面 下载 adb 1.0.39 版本,替换 /home/host/Android/Sdk/…...
微服务实战系列之玩转Docker(四)
前言 幸福,就是继续追寻已经拥有的东西。 ——圣奥古斯丁 什么算已经拥有的?比如爱你的人在等你,比如每日热腾腾的三餐,比如身边可爱的同事,又比如此刻的你,看见了这篇博文(😁&#…...
微信小程序-自定义组件生命周期
一.created 组件实例创建完毕调用。定义在lifetimes对象里。 不能在方法里面更改data对象里面的值,但是可以定义属性值。 lifetimes:{//不能给data设置值created(){this.testaaconsole.log("created") }}二. attached 模板解析完成挂载到页面。 可以更…...
2024年7月23日(samba DNS)
回顾 1、关闭防火墙,关闭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基金会主持的开源区块链项目,其目的是推动跨行业的区块链技术的开发和应用。以下是Hyperledger的顶级项目: 1. Hyperledger Fabric 描述:Hyperledger Fabric是一个可扩展的企业级区块链平台&…...
操作系统——笔记(1)
操作系统是管理计算机硬件资源,控制其他程序运行并为用户提供交互操作界面的系统软件的集合,控制和管理着整个计算机系统的硬件和软件资源,是最基本的系统软件。 常见的操作系统: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(推荐)安装openpyxl库建一个新的Item Pipeline类在settings.py中启用ExcelPipeline说明 使用scrapy-xlsx首先,安装scrapy-xlsx:然后在Scrapy爬虫中使用管道:说明 要使用Scrapy生…...
vscode debug C++无法输入问题
研究了半天vscode debug c无法输入的问题,原来vscode的文档里面已经记录了。issue都是2020年提的了,还没解决。。。 不过人家也确实给了一个解法:用外部的terminal。 不过怎么看都还不是很方便,所以还是推荐直接使用CodeLLDB插件来…...
MODBUS tcp学习总结
MODBUS TCP协议实例数据帧详细分析_modbus 帧结构-CSDN博客...
【第一天】计算机网络 TCP/IP模型和OSI模型,从输入URL到页面显示发生了什么
TCP/IP模型和OSI模型 这两个模型属于计算机网络的体系结构。 OSI模型是七层模型,从上到下包括: 应用层,表示层,会话层,传输层,网络层,数据链路层,物理层 TCP/IP模型是四层模型&…...
发现FionaAI:免费体验最新的GPT-4o Mini模型!
你现在可以在FionaAI上免费体验OpenAI刚刚发布的GPT-4o Mini模型!作为您在Google Chrome中的ChatGPT驱动助手,FionaAI可以随时随地与您对话,帮助您轻松创作和处理文本。 为什么选择GPT-4o Mini? 最新技术: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); …...
人工智能驾驶技术:引领未来道路
随着科技的不断进步,人工智能驾驶技术正以惊人的速度改变着我们的交通方式和生活方式。这项技术不仅令人兴奋,还引发了许多关于安全性、道德和法律等方面的深思。本文将探讨人工智能自动驾驶技术的发展现状、应用前景以及对社会的影响。 技术背景与发展…...
管理的核心是管人,管人的核心就是这3条,看懂的是高手
管理的核心是管人,管人的核心就是这3条,看懂的是高手 一:管欲 每个人都有欲望,无可厚非。管理者的任务就是利用欲望,管理欲望,通过欲望来达到管人的目的。 最需要管理的就是以下两种: 1、金…...
代码解读:Diffusion Models中的长宽桶技术(Aspect Ratio Bucketing)
Diffusion Models专栏文章汇总:入门与实战 前言:自从SDXL提出了长宽桶技术之后,彻底解决了不同长宽比的图像输入问题,现在已经成为训练扩散模型必选的方案。这篇博客从代码详细解读如何在模型训练的时候运用长宽桶技术(Aspect Rat…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
Spring Boot + MyBatis 集成支付宝支付流程
Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例(电脑网站支付) 1. 添加依赖 <!…...
leetcode_69.x的平方根
题目如下 : 看到题 ,我们最原始的想法就是暴力解决: for(long long i 0;i<INT_MAX;i){if(i*ix){return i;}else if((i*i>x)&&((i-1)*(i-1)<x)){return i-1;}}我们直接开始遍历,我们是整数的平方根,所以我们分两…...
