3.C_数据结构_栈

news/2024/9/16 13:37:33/ 标签: 数据结构

概述

什么是栈：

栈又称堆栈，是限定在一段进行插入和删除操作的线性表。具有后进先出(LIFO)的特点。

相关名词：

  • 栈顶：允许操作的一端
  • 栈底：不允许操作的一端
  • 空栈：没有元素的栈

栈的作用：

  • 可以检测逻辑图中是否有回路
  • 可以将非线性问题线性化 

入栈与出栈示意图：

入栈：先指针+1，再入栈数据。出栈：先出栈数据，再指针+1

顺序栈

1、基本内容

顺序栈就是以数组形式进行存储的栈数据结构。

顺序栈结构体如下：

typedef int data_t;
typedef struct{data_t* pData;//数据int max_len;  //最大数据长度int top;      //栈顶位置
}sqstack,*stacklink;

顺序栈代码的文件构成：

  • sqstack.h：数据结构的定义、运算函数接口
  • sqstack.c：运算函数接口的实现
  • test.c：使用数据结构实现的应用功能代码

顺序栈相关函数：

1、整个栈的创建和删除

  • 创建：stacklink stack_create(int len);
  • 删除：int stack_delete(stacklink pStack);

2、入栈、出栈

  • 入栈：int stack_push(stacklink pStack,data_t data);
  • 出栈：int stack_pop(stacklink pStack,data_t* data);

3、其他

  • 栈清空：int stack_clean(stacklink pStack);
  • 判断栈是否为空：int stack_isempty(stacklink pStack);

2、功能实现  

2.1 创建/删除栈

2.1.1 创建 

创建栈与创建线性表一样，都是先申请空间，之后赋值初始值

注意：在申请栈成功后，如果申请数据空间失败，需要释放申请的栈空间 

具体代码实现如下：

/** stack_create:创建一个栈* param len:栈的长度* @ret NULL--err  other--栈的地址* */
stacklink stack_create(int len){stacklink pStack = NULL;//1.申请空间//1.1 栈的空间pStack = (stacklink)malloc(sizeof(sqstack));if(pStack == NULL){printf("stack malloc err\n");return NULL;}//1.2 数据的空间pStack->pData = (data_t*)malloc(sizeof(data_t)*len);if(pStack->pData == NULL){printf("data malloc err\n");free(pStack);//此时pStack已经申请成功，应该释放空间return NULL;}//2.初始化memset(pStack->pData,0,sizeof(data_t)*len);pStack->max_len = len;pStack->top = -1;//-1代表空栈return  pStack;
}
2.1.2 删除

 删除栈就是释放所申请的空间。

注意：这里申请的空间是栈空间和数据空间，所以要释放两次

具体代码实现如下： 

/** stack_delete:栈的释放* param pStack:要进行释放的栈* @ret  -1--err 0--success* */
int stack_delete(stacklink pStack){//1.判断栈空间是否为空if(pStack == NULL){printf("pStack is NULL\n");return -1;}//2.释放空间free(pStack->pData);//释放数据空间free(pStack);       //释放栈空间pStack = NULL;return 0;
}

2.2 入栈与出栈

2.2.1 入栈

入栈就是先将指针+1，再将数据入栈。

具体代码实现如下：

/** stack_push:入栈* param pStack:所需入栈的栈的位置* param data:所需入栈的数据* @ret  -1--err  0--success* */
int stack_push(stacklink pStack,data_t data){//1.判断栈空间是否为空if(pStack == NULL){printf("pStack is NULL\n");return -1;}//2.判断栈空间是否已满if(pStack->top == (pStack->max_len-1)){printf("stack is full\n");return -1;}//3.入栈pStack->top++; 					    	//栈顶移动*(pStack->pData + pStack->top) = data;  //数据入栈return 0;
}
2.2.2 出栈

入栈就是先将数据出栈，再将指针-1。

具体代码实现如下：

/** stack_pop:出栈* param pStack:要进行出战的栈的位置* param data:出栈数据存储的位置* @ret  -1--err  0--success* */
int stack_pop(stacklink pStack,data_t* data){//1.判断栈空间是否为空if(pStack == NULL || data == NULL){printf("pStack is NULL\n");return -1;}//2.判断栈是否为空栈if(pStack->top == -1){printf("stack is empty\n");return -1;}//3.出栈*data = *(pStack->pData + pStack->top);//数据出栈pStack->top--; 						 //顶部移动return 0;
}

2.3 其他

2.3.1 栈清空

栈清空就是让栈的指针指向-1。

栈情况并不需要清空数组中的数据，因为之后写入新数据会自动覆盖旧数据

具体代码实现如下：

/** stack_clean:清空栈* param pStack:要进行清空的栈* @ret  -1--err  0--success* */
int stack_clean(stacklink pStack){//1.判断栈空间是否为空if(pStack == NULL){printf("pStack is NULL\n");return -1;}//2.清空栈pStack->top = -1;//设为空栈不需要清空return 0;
}
2.3.2 判断栈是否为空

空栈就是指针指向-1。

具体代码实现如下：

/** stack_isempty:判断栈是否为空栈* param pStack:需要进行判断的栈* @ret  -1--err  1--空栈  0--非空栈* */
int stack_isempty(stacklink pStack){//1.判断栈空间是否为空if(pStack == NULL){printf("pStack is NULL\n");return -1;}if(pStack->top == -1){return 1;}else{return 0;}
}

链式栈

1、基本内容

链式栈就是以链表形式进行存储的栈数据结构。

链式栈结构体如下：

typedef int data_t;
typedef struct node{data_t data;  		//数据struct node* pNext;  //链表指针
}listnode,*stacklink;

链式栈代码的文件构成：

  • linkstack.h：数据结构的定义、运算函数接口
  • linkstack.c：运算函数接口的实现
  • test.c：使用数据结构实现的应用功能代码

链式栈相关函数：

1、整个栈的创建和删除

  • 栈结点创建：stacklink stacknode_create(void);
  • 删除：int stack_delete(stacklink* pStack);

2、入栈、出栈

  • 入栈：int stack_push(stacklink* pStack,data_t data);
  • 出栈：int stack_pop(stacklink* pStack,data_t* data);

2、功能实现  

2.1 创建/删除栈

2.1.1 栈结点创建

使用链式栈时，不是一次性创建一整个栈，而是有一个数据入栈就创建一个栈的结点。

具体代码实现如下：

/** stacknode_create:创建栈结点* @ret  NULL--err  other--栈的地址* */
stacklink stacknode_create(void){stacklink pStack = NULL;//1.申请空间pStack = (stacklink)malloc(sizeof(listnode));if(pStack == NULL){printf("malloc err\n");return NULL;}//2.初始化memset(pStack,0,sizeof(listnode));pStack->pNext = NULL;return pStack;
}
2.1.1 删除整个栈

删除整个栈就是释放全部的申请空间。

具体代码实现如下：

/** stack_delete:释放整个栈* param pStack:要进行删除的栈* @ret  -1--err  0--success* */
int stack_delete(stacklink* pStack){stacklink point = *pStack;//1.栈空间判断if(*pStack == NULL){printf("pStack is NULL\n");return -1;}//2.释放空间while(point != NULL){point = point->pNext;free(*pStack);*pStack = point;}*pStack = NULL;return 0;
}

2.2 入栈与出栈

2.2.1 入栈

链式栈的入栈就是创建一个新结点，并把这个结点进行头插，这样出栈时每次访问头就可以实现后进先出的特点。

具体代码实现如下：

/** stack_push:入栈,头插法* param pStack:要进行插入的栈* param data:要入栈的数据* @ret  -1--err  0--success* */
int stack_push(stacklink* pStack,data_t data){stacklink pTmp = NULL;//1. 开辟新的结点pTmp = stacknode_create();if(pTmp == NULL){return -1;}pTmp->data = data;//2.开始入栈,//2.1 有栈空间,进行头插if(*pStack != NULL){pTmp->pNext = *pStack;}//2.2 没有栈空间,当前结点就是头*pStack = pTmp;//最终都要把头指向最新的结点return 0;
}
2.2.2 出栈

链式栈的出栈就访问链表的头，访问之后将头部结点进行删除。

具体代码实现如下：

/** stack_pop:出栈,取出链表头并释放空间* param pStack:要进行出栈的栈* param data:出栈的数据存放的位置* @ret  -1--err  0--success* */
int stack_pop(stacklink* pStack,data_t* data){stacklink pTmp = NULL;//1.栈空间判断if(*pStack == NULL){printf("pStack is NULL\n");return -1;}//2.开始出栈*data = (*pStack)->data;//出栈数据pTmp = (*pStack)->pNext;free(*pStack);//释放空间*pStack = pTmp;//改变链表头return 0;
}


http://www.ppmy.cn/news/1522899.html

相关文章

如何在 Linux 系统中禁用用户登录 ？

如何在 Linux 系统中禁用用户登录 ？

管理 Linux 系统上的帐户是系统管理员的一项重要任务。一个常见的任务是禁用帐户，由于各种原因可能需要禁用帐户，例如当员工离开公司或出于安全目的需要临时禁用访问时。 本指南将以简单易懂的步骤引导您完成在 Linux 系统上禁用帐户的过程。 Step 1: …
阅读更多...
2024.9.8

2024.9.8

打了一上午又一下午的比赛 DABOI Round 1 【MX-X3】梦熊周赛 未来组 3 & RiOI Round 4 第一场还好，共得180pts 难度比较合理，偏向正常noip 然后就发现自己计数问题很难做到推广思路，只会部分分 梦熊的模拟赛就抽象了 题目难度夸大…
阅读更多...
IDEA安装教程配置java环境（超详细）

IDEA安装教程配置java环境（超详细）

引言 IntelliJ IDEA 是一款功能强大的集成开发环境（IDE），广泛用于 Java 开发，但也支持多种编程语言，如 Kotlin、Groovy 和 Scala。本文将为你提供一步一步的指南，帮助你在 Windows 系统上顺利安装 Intelli…
阅读更多...
Qt：解决player-＞duration()第一次获取媒体时长为0的问题

Qt：解决player-＞duration()第一次获取媒体时长为0的问题

前言 最近想做一个白噪声播放器，中间就用到了QMediaplayer这个类，其中遇到两个问题，一个是未初始化好就调用player->state()导致程序异常崩溃的问题(这个问题留到下一个文章去说)；还有一个就是调用player->duration()第一次…
阅读更多...
Mendix 创客访谈录｜Mendix赋能汽车零部件行业：重塑架构，加速实践与数字化转型

Mendix 创客访谈录｜Mendix赋能汽车零部件行业：重塑架构，加速实践与数字化转型

在当前快速发展的技术时代，汽车行业正经历着前所未有的数字化转型。全球领先的汽车零配件制造商面临着如何利用最新的数字技术优化其制造车间管理的挑战。从设备主数据管理到生产执行工单管理，再到实时监控产量及能耗，需要一个灵活、快速且高…
阅读更多...
基于单片机智能电源插座设计

基于单片机智能电源插座设计

本设计基于单片机智能电源插座设计，该系统主要包括：单片机、WIFI模块、显示模块、继电器模块、按键输入模块、功率检测模块及手机APP，实现对用电量的实时监测的功能。功率检测模块实时测量用电器的供电电压、电流、功率；按键输入模…
阅读更多...
微信小程序：navigateTo跳转无效

微信小程序：navigateTo跳转无效

关于 navigateTo 跳转无效问题，在IOS、模拟器上面都能正常跳转，但是在安卓上面不能跳转，过了一段时间IOS也不能跳转了。仔细找了下问题结果是要跳转的页面是tab，不能使用navigateTo 取跳转修改为： wx.switchTab({url:…
阅读更多...
经验笔记：跨站脚本攻击（Cross-Site Scripting，简称XSS）

经验笔记：跨站脚本攻击（Cross-Site Scripting，简称XSS）

跨站脚本攻击（Cross-Site Scripting，简称XSS）经验笔记 跨站脚本攻击（XSS：Cross-Site Scripting）是一种常见的Web应用程序安全漏洞，它允许攻击者将恶意脚本注入到看起来来自可信网站的网页上。当…
阅读更多...
Spring Boot集成PDFBox实现电子签章

Spring Boot集成PDFBox实现电子签章

概述 随着无纸化办公的普及，电子文档的使用越来越广泛。电子签章作为一种有效的身份验证方式，在很多场景下替代了传统的纸质文件签名。Apache PDFBox 是一个开源的Java库，可以用来渲染、生成、填写PDF文档等操作。本文将介绍如何使用Spring …
阅读更多...
Socket编程 (连接,发送消息) (Tcp、Udp) - Part1

Socket编程 (连接,发送消息) (Tcp、Udp) - Part1

Socket编程 (连接,发送消息) (Tcp、Udp) 本篇文章主要实现Socket在Tcp\Udp协议下相互通讯的方式。(服务器端与客户端的通讯) 1.基于Tcp协议的Socket通讯类似于B/S架构，面向连接，但不同的是服务器端可以向客户端主动推送消息。 使用Tcp协议通讯需要具备…
阅读更多...
HiveServer2 启动时 datanucleus.schema.autoCreateTables 不生效的问题

HiveServer2 启动时 datanucleus.schema.autoCreateTables 不生效的问题

HiveServer2 启动时出 "Either your MetaData is incorrect, or you need to enable "datanucleus.schema.autoCreateTables"问题 Required table missing : "FUNCS" in Catalog "" Schema "". DataNucleus requires this table…
阅读更多...
深入探索Go语言中的指针：内存操作的艺术

深入探索Go语言中的指针：内存操作的艺术

首先，尽管指针（pointer）和switch语句在概念上并无直接联系，但本文将它们并置讨论的原因在于：这两个编程概念在实际学习和应用过程中常被编程人员所忽视。 对于指针的使用，初学者往往因其概念的抽象性和操作…
阅读更多...
探索Oracle数据库的多租户特性：架构、优势与实践

探索Oracle数据库的多租户特性：架构、优势与实践

在云计算和大数据时代，多租户架构成为数据库设计中的一个重要趋势。Oracle数据库的多租户选项（Multitenant）允许单个数据库实例支持多个独立数据库（称为容器数据库和可插拔数据库），每个数据库都有自己的数据…
阅读更多...
Vue3：＜Teleport＞传送门组件的使用和注意事项

Vue3：＜Teleport＞传送门组件的使用和注意事项

你好&#xff0c;我是沐爸&#xff0c;欢迎点赞、收藏、评论和关注。 Vue3 引入了一个新的内置组件 <Teleport>&#xff0c;它允许你将子组件树渲染到 DOM 中的另一个位置&#xff0c;而不是在父组件的模板中直接渲染。这对于需要跳出当前组件的 DOM 层级结构进行渲染的…
阅读更多...
算法：判断一个整数是不是2的阶次方

算法：判断一个整数是不是2的阶次方

一、思路 核心&#xff1a;不断除以2&#xff0c;缩小判断的范围 判断整数除以2的余数是否为0&#xff0c;如果不为0&#xff0c;则直接返回false&#xff1b;如果为0&#xff0c;则将将整数除以2后重复本步骤。 注意&#xff1a; 1为2的0次幂。 二、代码 public class Numb…
阅读更多...
第十章 【后端】环境准备（10.2）——Maven

第十章 【后端】环境准备（10.2）——Maven

10.2 Maven Maven 官网：https://maven.apache.org/ Maven 仓库：https://mvnrepository.com/ 下载 解压 在非系统盘上创建仓库目录 如：E:\maven-repository 修改配置 配置文件为 Maven 目录的 conf\settings.xml，修改为: <?xml version="1.0" encoding=&qu…
阅读更多...
25版王道数据结构课后习题详细分析 第八章 8.5 归并排序、基数排序和计数排序

25版王道数据结构课后习题详细分析 第八章 8.5 归并排序、基数排序和计数排序

一、单项选择题 ———————————————————— ———————————————————— 解析&#xff1a;我们知道插入排序不能保证在一趟排序结束后一定有元素放在最终位置上。事实上&#xff0c;归并排序也不能保证。例如&#xff0c;序列{6,5,7,8,2,1,4,3}…
阅读更多...
【Linux 从基础到进阶】Redis缓存服务安装与调优

【Linux 从基础到进阶】Redis缓存服务安装与调优

Redis缓存服务安装与调优 引言 Redis 是一个开源的内存数据结构存储系统，广泛应用于缓存、会话管理和实时分析等场景。它支持多种数据结构，如字符串、哈希、列表、集合和有序集合，因其高性能和灵活性，成为开发者的首选缓存解决方案。本文将介绍如何在 CentOS 和 Ubuntu 系…
阅读更多...
Python | Leetcode Python题解之第387题字符串中的第一个唯一字符

Python | Leetcode Python题解之第387题字符串中的第一个唯一字符

题目&#xff1a; 题解&#xff1a; class Solution:def firstUniqChar(self, s: str) -> int:position dict()q collections.deque()n len(s)for i, ch in enumerate(s):if ch not in position:position[ch] iq.append((s[i], i))else:position[ch] -1while q and po…
阅读更多...
Kubernetes学习指南：保姆级实操手册05——配置集群HA负载均衡

Kubernetes学习指南：保姆级实操手册05——配置集群HA负载均衡

五、Kubernetes学习指南&#xff1a;保姆级实操手册05——配置集群HA负载均衡 简介&#xff1a; Keepalived 提供 VRRP 实现&#xff0c;并允许您配置 Linux 机器使负载均衡&#xff0c;预防单点故障。HAProxy 提供可靠、高性能的负载均衡&#xff0c;能与 Keepalived 完美配合…
阅读更多...
最新文章

Copyright @ 2022~2023

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