数据结构:栈的实现

1. 栈(Stack)

1.1 栈的概念

  • 栈(Stack)是只允许在一端进行插入或删除操作的线性表.首先栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作.
  • 进行数据插入和删除操作的一端栈顶,另一端称为栈底.
  • 栈中的元素遵循后进先出LIFO(Last In First Out)的原则

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶.
出栈:栈的删除操作叫做出栈,出数据也在栈顶.

1.2 栈的结构

在这里插入图片描述

栈的元素,遵循后进先出原则


栈采用什么逻辑结构呢?
通常栈可以用链表和数组实现.
当然我们调用的时候不需要知道,使用的是什么方法实现.

链表栈

通过在表前端插入来实现 push ,通过删除表前端元素实现 pop.
可以使用之前实现的单链表来实现栈,单链表实现详见.只用注意,栈只有插入删除操作,需要头删和头插.

虽然操作都是花费常数时间,但是对mallocfree的调用是十分昂贵的.

数组栈

更为流行的是使用数组来实现栈.虽然数组的大小需要提前说明或者临时开辟,但是,在典型的应用程序中,栈元素的实际个数一般不会太大,使用数组是更加高效的方法.


总结:

  • 推荐使用数组结构实现栈
  • 若使用链表实现栈
    用尾做栈顶,尾删尾插,要设计成双向链表
    用头做栈顶,头删头插,要设计成单链表

2. 栈的定义

一般来说,使用动态栈而非静态栈,需要扩容的时候,可以进行适当扩容,增加了程序的适用性.

动态栈实现的数据结构

typedef int STDataType;typedef struct Stack
{STDataType* a;  //指向栈空间int top;        //栈顶int capacity;   //容量
}Stack;

接口函数

// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空, 如果为空返回非零结果, 如果不为空返回 0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);

3. 栈的实现

3.1 初始化栈 (StackInit)

// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps->a = NULL;     ps->top = 0;ps->capacity = 0;
}
  1. 和创建顺序表的操作是一致的,通过结构体指针ps修改主函数中的结构体的成员变量,将ps指向的数组指针指向NULL,同时将容量capacity和栈顶元素top置为 0.
  1. 注意,在这里,top所指向的是栈顶元素后一个空间,此时没有元素,自然就指向了数组的第一个空间

3.2 入栈 (StackPush)

//入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);       //确保ps合法//如果容量不够则扩容if (ps->capacity == ps->top){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;   //定义新的容量STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);  //开辟新的空间if (tmp == NULL){perror("malloc error");exit(-1);}else {ps->a = tmp;ps->capacity = newCapacity;}}//将数据入栈ps->a[ps->top] = data;ps->top++;
}
  1. 首先确保ps合法
  2. 因为是动态栈,会出现空间不够的情况,在入栈之前首先确保容量充足,如果容量不够,则进行扩容
  3. 将数据入栈,同时top++

3.3 出栈 (StackPop)

// 出栈
void StackPop(Stack* ps)
{assert(ps); //确保ps合法assert(!StackEmpty(ps));  //确保栈不为空ps->top--;}
  1. 确保 ps 合法
  2. 确保栈不为空
  3. 直接将top--即可

3.4 检测栈是否为空 (StackEmpty)

// 检测栈是否为空, 如果为空返回非零结果, 如果不为空返回 0
int StackEmpty(Stack* ps)
{assert(ps); //确保ps合法if (ps->top > 0){return 0;}else {return 1;}
}
  1. 确保ps合法
  2. 如果top大于0,说明栈不为空,反之则为空

3.5 获取栈顶元素 (StackTop)

// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);   //确保ps合法assert(!StackEmpty(ps));  //确保栈不为空return ps->a[ps->top - 1];
}
  1. 确保ps合法
  2. 确保栈不为空
  3. 直接返回top - 1位置的元素

3.6 获取栈中有效元素个数 (StackSize)

// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);   //确保ps合法return ps->top;
}
  1. 确保ps合法
  2. 直接将top返回即可

3.7 销毁栈 (StackDestroy)

// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps); //确保ps合法free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
  1. 确保ps合法
  2. 将ps指向的数组空间归还给操作系统,同时将topcapacity置为0

3.8 完整代码

  • Stack.h
#pragma once #include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>typedef int STDataType;typedef struct Stack
{STDataType* a;  //指向栈空间int top;        //栈顶int capacity;   //容量
}Stack;// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空, 如果为空返回非零结果, 如果不为空返回 0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
  • Stack.c
#include "Stack.h"// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps->a = NULL;     ps->top = 0;ps->capacity = 0;
}//入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);       //确保ps合法//如果容量不够则扩容if (ps->capacity == ps->top){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;   //定义新的容量STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);  //开辟新的空间if (tmp == NULL){perror("malloc error");exit(-1);}else {ps->a = tmp;ps->capacity = newCapacity;}}//将数据入栈ps->a[ps->top] = data;ps->top++;
}// 出栈
void StackPop(Stack* ps)
{assert(ps); //确保ps合法assert(!StackEmpty(ps));  //确保栈不为空ps->top--;}// 检测栈是否为空, 如果为空返回非零结果, 如果不为空返回 0
int StackEmpty(Stack* ps)
{assert(ps); //确保ps合法if (ps->top > 0){return 0;}else {return 1;}
}// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);   //确保ps合法assert(!StackEmpty(ps));  //确保栈不为空return ps->a[ps->top - 1];
}// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);   //确保ps合法return ps->top;
}// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps); //确保ps合法free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
  • Test.c
#include "Stack.h"void StackTest1()
{Stack st;StackInit(&st);StackPush(&st, 1);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPush(&st, 2);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPush(&st, 3);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPush(&st, 4);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPush(&st, 5);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPop(&st);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPop(&st);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPop(&st);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPop(&st);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPop(&st);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPop(&st);
}int main(void)
{StackTest1();return 0;
}printf("%d\n", StackTop(&st));StackPop(&st);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPop(&st);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPop(&st);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPop(&st);
}int main(void)
{StackTest1();return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【算法系列篇】分治-归并

文章目录 前言什么是归并算法1. 排序数组1.1 题目要求1.2 做题思路1.3 Java代码实现 2. 数组中逆序对2.1 题目要求2.2 做题思路2.3 Java代码实现 3. 计算右侧小于当前元素的个数3.1 题目要求3.2 做题思路3.3 Java代码实现 4. 翻转对4.1 题目要求4.2 做题思路4.3 Java代码实现 总…

【漏洞复现】广联达办公OAsql+文件上传+弱口令

漏洞描述 广联达办公OA是一款综合办公自动化解决方案,旨在提高组织内部的工作效率和协作能力。它提供了一系列功能和工具,帮助企业管理和处理日常办公任务、流程和文档。默认弱口令admin password,后面就不提了。 免责声明 技术文章仅供参考,任何个人和组织使用网络应当…

uni-app:实现右侧弹窗

效果&#xff1a; 代码&#xff1a; <template><view class"container"><button click"showModal true">点击按钮</button><view class"modal-overlay" v-if"showModal" click"closeModal">…

Django学习

1、启动项目 python manage.py runserversettings.py 视图函数&#xff0c;用于接收浏览器请求 Django使用的是MTV,是MVC是升级

通过nginx将https协议反向代理到http协议请求上

通过nginx将https协议反向代理到http协议请求上 1、问题背景2、介绍nginx的反向代理功能及配置https协议3、具体实现3.1 后端服务支持方式3.2 nginx重定向方式 3.3、nginx的反向代理方式4、关于nginx常用模块和指令 1、问题背景 目前一个系统仅支持https协议访问&#xff0c;因…

【Linux安装java环境】超简单,以jdk8为例

文章目录 前言详细步骤总结 前言 一些小伙伴在到手一台虚拟机后&#xff0c;发现需要配置java环境&#xff0c;看了文章后会发现超级简单&#xff0c;以下内容以安装jdk1.8为例。 详细步骤 查看是否存在java环境java -version若弹出找不到java命令&#xff0c;执行下一步。官…

linux并发服务器 —— IO多路复用(八)

半关闭、端口复用 半关闭只能实现数据单方向的传输&#xff1b;当TCP 接中A向 B 发送 FIN 请求关闭&#xff0c;另一端 B 回应ACK 之后 (A 端进入 FIN_WAIT_2 状态)&#xff0c;并没有立即发送 FIN 给 A&#xff0c;A 方处于半连接状态 (半开关)&#xff0c;此时 A 可以接收 B…

Java逻辑控制

目录 一、顺序结构 二、分支结构 1、if语句 &#xff08;1&#xff09; 语法格式1​编辑 &#xff08;2&#xff09;语法格式2​编辑 &#xff08;3&#xff09;语法格式3 2、switch 语句 三、循环结构 1、while循环 2、break 3、continue 4、for 循环 5、do whil…

实训笔记9.1

实训笔记9.1 9.1笔记一、项目开发流程一共分为七个阶段1.1 数据产生阶段1.2 数据采集存储阶段1.3 数据清洗预处理阶段1.4 数据统计分析阶段1.5 数据迁移导出阶段1.6 数据可视化阶段 二、项目的数据产生阶段三、项目的数据采集存储阶段四、项目数据清洗预处理的实现4.1 清洗预处…

MongoDB基础知识点

MongoDB基础知识点 1.MongoDB简介1.1基本信息1.2作用1.3下载 2.MongoDB安装1.Ubuntu22.042.Windows(非msi) 3.MongoDB基本操作1.基本概念2.MongoDB文件增删改查(CURD)1.插入数据2.查询数据3.修改数据4.删除数据5.删除字段 4.MongoDB实战管理系统数据库设计1.设计数据库2.Mongod…

企业架构LNMP学习笔记13

上线商城项目&#xff1a; 1&#xff09;上传项目文件到数据库&#xff1a; 入口文件位置的设计是为了让应用部署更安全&#xff0c;public目录为web可访问目录&#xff0c;其他的文件都可以放到非web访问目录下面。 nginx 默认访问index.html。没有index.html&#xff0c;就会…

宠物电商Chewy第二季度销售额28亿美元,同比增长14.3%

美国宠物电商Chewy公布2023年第二季度财报。报告显示&#xff0c;其Q2季度销售额同比增长14.3%至28亿美元&#xff0c;超出市场预期。 以下为Chewy期内业绩概要&#xff1a; 1.毛利率28.3%&#xff0c;同比增长20个基点 2.净利润有所收窄&#xff0c;同比下降15.2%至1890万美…

【深入解析spring cloud gateway】06 gateway源码简要分析

上一节做了一个很简单的示例&#xff0c;微服务通过注册到eureka上&#xff0c;然后网关通过服务发现访问到对应的微服务。本节将简单地对整个gateway请求转发过程做一个简单的分析。 一、核心流程 主要流程&#xff1a; Gateway Client向 Spring Cloud Gateway 发送请求请求…

客服部门都应该建立一个自有的在线FAQ系统

问答系统是目前应用最广泛的问答系统。这种问答系统的结构框架明了、实现简单、容易理解&#xff0c;非常适合作为问答系统入门学习时的观察对象。所以越来越多的企业需要建立一个自有的在线FAQ系统&#xff0c;这对对于客服部门来说是非常有益的。 企业需要搭建自己FAQ系统的理…

【Linux】Ubuntu20.04版本配置pytorch环境2023.09.05【教程】

【Linux】Ubuntu20.04版本配置pytorch环境2023.09.05【教程】 文章目录 【Linux】Ubuntu20.04版本配置pytorch环境2023.09.05【教程】一、安装Anaconda虚拟环境管理器二、创建虚拟环境并激活三、安装Pytorch四、测试pytorchReference 一、安装Anaconda虚拟环境管理器 首先进入…

LeetCode(力扣)216. 组合总和 IIIPython

LeetCode216. 组合总和 III 题目链接代码 题目链接 https://leetcode.cn/problems/combination-sum-iii/ 代码 class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:result[]self.backtracking(n, k, 0, 1, [], result)return resultdef back…

多个pdf怎么合并在一起?跟着我的步骤一起合并

多个pdf怎么合并在一起&#xff1f;利用PDF文档合并功能可以帮助您更有效地管理文件&#xff0c;将多个相关文件整合成一个文件&#xff0c;避免分散在多个文件中。此外&#xff0c;合并后的文件更便于共享和传输&#xff0c;因为只需共享一个文件而不是多个文件。虽然合并文件…

900. RLE 迭代器

900. RLE 迭代器 原题链接&#xff1a;完成情况&#xff1a;解题思路&#xff1a;参考代码&#xff1a; 原题链接&#xff1a; 900. RLE 迭代器 https://leetcode.cn/problems/rle-iterator/description/ 完成情况&#xff1a; 解题思路&#xff1a; //int next(int n) 以这…

git: ‘lfs‘ is not a git command unclear

首先可以尝试 git lfs install 是否可以&#xff0c;不可以后就看这个连接&#xff1a;https://stackoverflow.com/questions/48734119/git-lfs-is-not-a-git-command-unclear。 我的是ubuntu&#xff0c;所以&#xff1a; git-lfs requires git version 1.8.3.1 or later. Yo…

webpack打包

文章目录 一、什么是webpack二、使用步骤1.创建一个新的文件夹,并将其初始化2.在当前目录下安装webpack以及webpack-cli3.配置webpack自定义命令,使之生效4.运行自定义命令,打包webpack5.打包成功之后会将内容打包到dist文件夹下6.配置webpack1)修改webpack打包入口和出口2)配置…