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

【C】初阶数据结构5 -- 栈

  前面学习了两种最基本的数据结构 -- 顺序表和链表,接下来就可以基于这两种数据结构来实现其他数据结构了。其实,其他的数据结构的物理结构要么是数组,要么就是链表,所以学好顺序表和链表是学好其他数据结构的基础。接下里,我们就来看一个新的数据结构 -- 栈。


目录

1  栈的概念与特点

2  栈的结构 

1) 逻辑结构

2) 物理结构 

 3  栈的基本操作的实现

1) 初始化和销毁

2) 入栈与出栈、

(1) 入栈

(2) 出栈

3)  取栈顶元素、判空、获取有效元素个数

4  代码


重点一  栈的特点

1  栈的概念与特点

  栈:一种特殊的线性表,其只允许在一端进行插入和删除数据。插入和删除数据的一端叫做栈顶,另一端叫做栈底。

  入栈(压栈):往栈中插入数据的操作叫做入栈。

  出栈:栈中删除数据的操作叫做出栈。

  特点:栈中的数据遵循LIFO原则(last in first out),也就是后进先出原则。

  栈的特点特别重要,一般使用栈都是因为其后进先出的特点,下面来做一个题来理解一下其后进先出的特点:

假设有一个栈,数据入栈的先后顺序为 a b c d e ,请在以下选项中选出错误的出栈顺序()A. a b c d e                    B. c b d a eC. d b c a e                    D. e d c b a

 该题的正确答案为 C,因为如果 d 先出栈的话,说明 a,b,c 均以入栈,如何要接着出栈的话,应是 c 先出栈,而不是 b 先出栈。

  需要注意的一点就是,出栈顺序并不是等数据全部入栈之后才能出栈。比如 A 选项,就是入栈一个数据,然后出栈一个数据。


重点二  栈的结构

2  栈的结构 

1) 逻辑结构

  我们可以把栈想象成以下的一个结构:

2) 物理结构 

  栈的物理结构既可以选择用链式结构来实现,也可以选择用数组,也就是顺序表来实现。这里选择使用数组来实现,因为栈后进先出的特性,规定了其只能在尾部进行插入和删除数据,而对于顺序表来说,在尾部插入和删除数据又十分方便,所以这里选择使用顺序表来实现栈。

  既然是使用顺序表来实现栈,所以栈的结构和顺序表十分相似,只不过就是把 size 变为了 top,用来表示栈的顶部元素的位置:

//将int定义为栈里面的数据类型
typedef int STDataType;
//栈的结构
typedef struct Stack
{STDataType* arr;//栈中的存放数据的数组int capacity;//栈的容量大小int top;//栈顶
}ST;

重点三  实现栈

 3  栈的基本操作的实现

  对于一个栈来说,其主要操作只有入栈、出栈、取栈顶元素、初始化、销毁、判空、获取有效元素个数。

1) 初始化和销毁

    栈的初始化和销毁与顺序表可以说是一模一样,这里就不做多余讲解,可以去回顾一下顺序表(也可以看下面代码理解一下)。


2) 入栈与出栈、

(1) 入栈

  入栈的操作就相当于顺序表中的尾差,其基本过程如图所示:

可以看到,就是顺序表的尾插操作,只不过就是把 size 变成了 capacity 而已。

(2) 出栈

  出栈就是顺序表的尾删,所以只需要让 --top 就可以了。


3)  取栈顶元素、判空、获取有效元素个数

  这3个操作的实现都很简单。取栈顶元素就是返回 arr 数组中 top - 1 下标的数据,但要注意栈要非空,才能返回栈顶元素,所以要先对栈是否为空断言;判空就是判断 top 是否等于0;获取有效元素个数就是返回 top 。


4  代码

Stack.h文件:

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;
typedef struct Stack
{STDataType* arr;int capacity;int top;
}ST;//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//栈是否为空
bool STEmpty(ST* ps);

Stack.c文件:

#include"Stack.h"//初始化
void STInit(ST* ps)
{assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}//入栈
void STPush(ST* ps, STDataType x)
{//相当于顺序表的尾插assert(ps);//如果数组满了。需要增容if (ps->capacity == ps->top){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc fail!\n");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//不要忘记让top++ps->arr[ps->top++] = x;
}
//栈是否为空
bool STEmpty(ST* ps)
{assert(ps);//判断top是否为0就可以了return ps->top == 0;
}
//出栈
void STPop(ST* ps)
{//相当于顺序表的尾删assert(!STEmpty(ps));--ps->top;
}//取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);//栈不能为空assert(!STEmpty(ps));//只取栈顶元素,不删除数据int pos = ps->top - 1;return ps->arr[pos];
}//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}

test.c文件:

#include"Stack.h"
void Test4()
{ST st;STInit(&st);//测试入栈STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);for (int i = 0; i < st.top; i++){printf("%d ", st.arr[i]);}printf("\n");//测试出栈与取栈顶元素STPop(&st);STPop(&st);STPop(&st);STPop(&st);//STPop(&st);/*int ret = STTop(&st);printf("%d ", ret);printf("\n");for (int i = 0; i < st.top; i++){printf("%d ", st.arr[i]);}printf("\n");*/bool ret1 = STEmpty(&st);if (ret1){printf("栈为空!\n");}else{printf("栈不为空!\n");}int ret = STSize(&st);printf("%d ", ret);STDestroy(&st);
}
int main()
{Test4();return 0;
}

   可以看到实现栈,其实就是实现顺序表的部分接口,学好顺序表和链表是实现其他数据结构的基础。所以一定要把基础学扎实,才能越学越好。

相关文章:

【C】初阶数据结构5 -- 栈

前面学习了两种最基本的数据结构 -- 顺序表和链表&#xff0c;接下来就可以基于这两种数据结构来实现其他数据结构了。其实&#xff0c;其他的数据结构的物理结构要么是数组&#xff0c;要么就是链表&#xff0c;所以学好顺序表和链表是学好其他数据结构的基础。接下里&#xf…...

闭源大语言模型的怎么增强:提示工程 检索增强生成 智能体

闭源大语言模型的怎么增强 提示工程 检索增强生成 智能体 核心原理 提示工程:通过设计和优化提示词,引导大语言模型进行上下文学习和分解式思考,激发模型自身的思维和推理能力,使模型更好地理解和生成文本,增强其泛用性和解决问题的能力。检索增强生成:结合检索的准确…...

C语言-------结构体(1)

数据类型 &#xff08;1&#xff09;基本数据类型 整型 浮点型 字符型 &#xff08;2&#xff09;构造类型 数组 结构体 结构体: 用来处理&#xff0c;现实生活中&#xff0c;更复杂的数据的描述 用来 描述复杂数据的 一种用户自定义的数…...

org.apache.kafka.common.errors.TimeoutException

个人博客地址&#xff1a;org.apache.kafka.common.errors.TimeoutException | 一张假钞的真实世界 使用kafka-console-producer.sh向远端Kafka写入数据时遇到以下错误&#xff1a; $ bin/kafka-console-producer.sh --broker-list 172.16.72.202:9092 --topic test This is …...

Ceph集群搭建2025(squid版)

squid版本维护年限 apt install -y cephadmecho >> "deb http://mirrors.163.com/ceph/debian-squid/ bookworm main" echo >> "deb-src http://mirrors.163.com/ceph/debian-squid/ bookworm main"#安装源 cephadm install #开始初始化一个最…...

DeepSeek从入门到精通:提示词设计的系统化指南

目录 引言&#xff1a;AIGC时代的核心竞争力 第一部分 基础篇&#xff1a;提示词的本质与核心结构 1.1 什么是提示词&#xff1f; 1.2 提示词的黄金三角结构 第二部分 类型篇&#xff1a;提示词的六大范式 2.1 提示语的本质特征 2.2 提示语的类型 2.2.1 指令型提示词 …...

python后端调用Deep Seek API

python后端调用Deep Seek API 需要依次下载 ●Ollama ●Deepseek R1 LLM模型 ●嵌入模型nomic-embed-text / bge-m3 ●AnythingLLM 参考教程&#xff1a; Deepseek R1打造本地化RAG知识库:安装部署使用详细教程 手把手教你&#xff1a;deepseek R1基于 AnythingLLM API 调用本地…...

自有证书的rancher集群使用rke部署k8s集群异常

rancher使用自签域名&#xff0c;或者商业证书容易踩到的坑。 最开始的报错&#xff1a; docker logs kubelet‘s id E0214 13:04:14.590268 9614 pod_workers.go:1300] "Error syncing pod, skipping" err"failed to \"StartContainer\" for …...

【线性代数】1行列式

1. 行列式的概念 行列式的符号表示: 行列式的计算结果:一个数 计算模型1:二阶行列式 二阶行列式: 三阶行列式: n阶行列式: 🍎计算行列式 计算模型2:上三角形行列式 上三角形行列式特征:主对角线下皆为0。 上三角形行列式: 化上三角形通用方法:主对角线下,…...

DeepSeek免费部署到WPS或Office

部署到WPS - 通过OfficeAI插件接入&#xff1a; - 准备工作&#xff1a;安装最新版本的WPS Office软件&#xff1b;访问DeepSeek官网&#xff0c;点击右上角的“API开放平台”&#xff0c;登录账号&#xff08;若无账号需先注册&#xff09;&#xff0c;登录成功后&#xff0c;…...

数据结构 二叉树

一、⼆叉树的定义 ⼆叉树是⼀种特殊的树型结构&#xff0c;它的特点是每个结点⾄多只有2棵⼦树&#xff08;即⼆叉树中不存在度⼤于2的结点&#xff09;&#xff0c;并且⼆叉树的⼦树有左右之分&#xff0c;其次序不能任意颠倒。 ⼆叉的意思是这种树的每⼀个结点最多只有两个孩…...

鸿蒙开发:熟知@BuilderParam装饰器

前言 本文代码案例基于Api13。 在实际的开发中&#xff0c;我们经常会遇到自定义组件的情况&#xff0c;比如通用的列表组件&#xff0c;选项卡组件等等&#xff0c;由于使用方的样式不一&#xff0c;子组件是动态变化的&#xff0c;针对这一情况&#xff0c;就不得不让使用方把…...

光谱相机在天文学领域的应用

天体成分分析 恒星成分研究&#xff1a;恒星的光谱包含了其大气中各种元素的吸收和发射线特征。通过光谱相机精确测量这些谱线&#xff0c;天文学家能确定恒星大气中氢、氦、碳、氮、氧等元素的含量。如对太阳的光谱分析发现&#xff0c;太阳大气中氢元素占比约 71%&#xff0…...

不到1M的工具,使用起来非常丝滑!

今天给大家推荐两款电脑上超实用的小软件&#xff0c;分别是倒计时工具和关机助手&#xff0c;用起来特别顺手&#xff0c;希望能帮到大家。 关机助手 帮你自动关机 先说说关机助手。这款软件简直太方便了&#xff01;它是一款免安装的小工具&#xff0c;体积超小&#xff0c;…...

软考高级《系统架构设计师》知识点(二)

操作系统知识 操作系统概述 操作系统定义&#xff1a;能有效地组织和管理系统中的各种软/硬件资源&#xff0c;合理地组织计算机系统工作流程&#xff0c;控制程序的执行&#xff0c;并且向用户提供一个良好的工作环境和友好的接口。操作系统有三个重要的作用&#xff1a; 管理…...

深入解析操作系统控制台:阿里云Alibaba Cloud Linux(Alinux)的运维利器

作为一位个人开发者兼产品经理&#xff0c;我的工作日常紧密围绕着云资源的运维和管理。在这个过程中&#xff0c;操作系统扮演了至关重要的角色&#xff0c;而操作系统控制台则成为了我们进行系统管理的得力助手。本文将详细介绍阿里云的Alibaba Cloud Linux操作系统控制台的功…...

云原生AI Agent应用安全防护方案最佳实践(上)

当下&#xff0c;AI Agent代理是一种全新的构建动态和复杂业务场景工作流的方式&#xff0c;利用大语言模型&#xff08;LLM&#xff09;作为推理引擎。这些Agent代理应用能够将复杂的自然语言查询任务分解为多个可执行步骤&#xff0c;并结合迭代反馈循环和自省机制&#xff0…...

Java Virtual Machine(JVM)

JVM跨平台原理 跨平台&#xff1a;一次编译&#xff0c;到处运行 本质&#xff1a;不同操作系统上运行的JVM不一样&#xff0c;只需要把java程序编译成一份字节码文件&#xff0c;JVM执行不同的字节码文件。 Java是高级语言&#xff0c;提前编译一下&#xff08;变成字节码文件…...

vue前端可视化大屏页面适配方案

参考了其他博主的代码&#xff0c;但发现会有滚动条&#xff0c;并且居中的位置不太对&#xff0c;所以改了一下css&#xff0c;修复了这些问题&#xff0c;直接上代码 <template> <div class"ScaleBoxA"><divclass"ScaleBox"ref"Sca…...

Docker中安装MySql方法

使用Docker安装MySQL的详细步骤,涵盖单机部署、数据持久化、网络配置等内容: 1. 安装Docker 如果尚未安装Docker,请先安装: Windows/macOS:下载 Docker Desktop 并安装。 Linux: curl -fsSL https://get.docker.com | bash sudo systemctl start docker sudo system…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...