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

数据结构--栈的实现

数据结构–栈的实现

1.栈的概念和结构:

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

栈的应用:栈其实可以看作一个弹夹,数据就是一个一个的子弹,而子弹在弹夹中确是先进去的要后被发射,最后后进去的反而会先被发射。**进栈就是装子弹的过程,而出栈就是发射子弹的过程。**同时,向栈中插入数据的操作也被称作压栈、进栈、入栈等。取出栈中数据的的操作则被称之为出栈、弹栈。
在这里插入图片描述

栈的结构

下图是向栈中插入数据(Top),只能从栈顶插入数据。
在这里插入图片描述

下图是取出栈中的数据(Pop),只能从栈顶取出数据。
在这里插入图片描述

1.1进出栈的变化形式

  1. 请问现在向栈中顺序插入了1,2,3这三个数据的出栈顺序是不是就是3,2,1呢?
    其实这个出栈的顺序和入栈的顺序有很大的关系.比如先向栈入插入了1和2,然后将这两个取出来,那么取出的顺序就是2,1,接着将3插入栈中,接着就取出3,那么所有元素的出栈的顺序就是2,1,3,这与入栈元素的个数和出栈的情况有关.
  2. 先入栈的元素是不是就只能最后出栈呢??
    答案也是不一定的,举个例子:现在有1,2,3这三个元素,向栈中先插入1和2,接着将这两个元素取出,那么取出的顺序就是2和1,接着将3入栈,然后将3取出来,此时对于整个栈来讲,最先进栈的是1,而最后出栈的则是3.
  3. 此时还是有1,2,3这三个元素,请问有没有一种特定的插入栈顺序(保证1,2,3是按顺序进栈),使得这些元素按照3,1,2(3最先出栈)的顺序出栈呢??
    答案是没有的,无论如何都不可能是3,1,2这样的顺序出栈.因为要想第一个出3,那么肯定需要将1,2,3按次序都插入栈中,将3取出之后,接着栈顶的元素是2,要想取到1,必须先取出2.那么显然是不可能先取出1的.

2.栈的实现

栈的特点:
由于栈拥有顺序表的特点,但是由于栈的特殊性,所以针对栈在操作上会有变化,特别是插入和删除操作分别称作push和pop,英文翻译分别是压和弹,更方便理解.当作是对子弹进行操作就比较好记忆了.

实现方式:
栈的实现可以采用链表和数组两种方式,但是使用数组更方便,用数组对栈进行删除和插入操作时,只需要对数组的下标进行操作即可,代价较小,但是使用链表还需要进行释放节点,新建节点等操作,成本高.
栈中存储的数据可以使用typedef来定义,这样就可以做到自由更改栈中的数据类型.

那么针对的栈的特有的操作有哪些呢 ??

// 初始化栈
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);

​ 针对栈这种只能支持在一端进行插入和删除操作的特殊结构,采用数组的0下标处作为栈底是比较好的,因为首元素都在栈底,变化最小.我们使用一个top指针来指向栈顶的元素,也就是在top变量中存储栈顶元素在数组中的下标.
​ top指针就相当于游标卡尺上的游标,游标来回移动就代表中栈顶元素的插入和删除,当游标到了最大容量时,也就是栈满了的时候,就需要扩容了,所以需要一个capacity变量用于记录栈的最大容量,容量满了之后就用realloc函数进行扩容,为数组动态开辟空间.所以栈的定义如下:

typedef int STDataType;
typedef struct Stack
{STDataType* a;int Capacity;//容量int top;//栈顶指针
}Stack;

​ 但是当一开始栈中没有元素时,top的值该设置为多少呢??假如top的初始值是0,想象在坐标-1处有一个元素,那么此时的top相当于就是指向了栈顶元素的下一个位置.假定top的初始值为-1,就说明top指向的是栈顶元素.本文采用的是前者这种方式.

2.1初始化栈

这里首先将栈的容量设置为0.

void StackInit(Stack* ps)
{assert(ps);ps->a = NULL;ps->Capacity = 0;ps->top = 0;//top的值为0则说明指向栈顶的下一个元素
}

2.2向栈中插入数据

向栈中插入数据是push(压)操作,注意:插入之前要注意检查栈的容量是否已经满了.并且向栈中插入数据之后,top一定要自增1.因为本文这里top永远保存的是栈顶元素的下一个位置.

// 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);//先检查容量if (ps->top == ps->Capacity){int newCapacity = ps->Capacity == 0 ? 4 : ps->Capacity * 2;ps->Capacity = newCapacity;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)*newCapacity);if (tmp == NULL){perror("realloc fail:");exit(-1);}ps->a = tmp;}ps->a[ps->top] = data;ps->top++;
}

2.3获取栈顶数据

获取栈顶数据之前,要检查top是否为0.为0则说明栈已经为空,没有数据了,由于top存储的是栈顶元素的下一个位置,所以返回的值是top-1位置处的值.

// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps->top);return ps->a[(ps->top)-1];
}

2.4删除栈顶数据

删除栈顶数据之前,要检查top是否为0.为0则说明栈已经为空,没有数据了,同时只需要将top–即可,因为top指向的栈顶元素的下一个位置,相当于此时就把栈顶元素等效删除了.

void StackPop(Stack* ps)
{assert(ps);assert(ps->top);//防止元素个数为0(ps->top)--;//让栈顶指针后移
}

2.5销毁栈

// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->Capacity = ps->top = 0;ps = NULL;
}

2.6获取栈中有效元素的个数

既然top指向的是栈顶元素的下一个位置的下标,那么top的值刚好就是栈中的元素的个数.

// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}

2.7检测栈是否为空

// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps)
{assert(ps);return (ps->top) == 0;
}

3.栈的作用

有的小伙伴可能会想,可以直接使用数组或链表实现这些功能即可.为什么还需要单独设计出来这个栈的数据结构呢?其实,栈的引入简化了程序设计问题,划分了不同层次,使得思考范围缩小,更加聚焦于我们要解决的问题的核心,反之,像数组等,需要我们分散精力取考虑元素的下标的增减问题等问题,反而掩盖了问题的本质.

4.结束

栈就讲到这里啦,欢迎各位小伙伴在评论区中指正本文的不足.下期见!

相关文章:

数据结构--栈的实现

数据结构–栈的实现 1.栈的概念和结构: 栈的概念:栈是一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Las…...

第十章 异常

python使用异常的特殊对象管理程序执行期间发生的错误。每当发生错误时,python会创建异常对象。如果编写了处理该异常的代码,程序将继续运行;如果未处理,程序将显示traceback。 异常是使用try-except代码块处理的。使用try-excep…...

Rust冒泡排序

Rust冒泡排序 这段代码定义了一个名为 bubble_sort 的函数,接受一个可变的整数类型数组作为输入,然后使用嵌套的循环来实现冒泡排序。外部循环从数组的第一个元素开始迭代到倒数第二个元素,内部循环从数组的第一个元素开始迭代到倒数第二个元…...

麒麟信安服务器操作系统V3.5.2重磅发布!

9月25日,麒麟信安基于openEuler 22.03 LTS SP1版本的商业发行版——麒麟信安服务器操作系统V3.5.2正式发布。 麒麟信安服务器操作系统V3定位于电力、金融、政务、能源、国防、工业等领域信息系统建设,以安全、稳定、高效为突破点,满足重要行…...

密码技术 (1) - 对称密码

一. 前言 对称密码是指加密数据和解密数据使用的是相同的秘钥。发送者使用秘钥将加密后的数据发送给接受者,接收者收到数据后用相同的秘钥解密,恢复原始数据。 对称密码具有加密和解密快速的特点,适用于需要快速加密的场景,常用的…...

基于PYQT5的GUI开发系列教程【二】QT五个布局的介绍与运用

目录 本文概述 作者介绍 创建主窗口 水平布局 垂直布局 栅格布局 分裂器水平布局 分裂器垂直布局 自由布局 取消原先控件的布局的方法 尾言 本文概述 PYQT5是一个基于python的可视化GUI开发框架,具有容易上手,界面美观,多平台…...

Cadence PCB 焊盘和封装

封装(Packaging) 封装指的是在电子元件制造中将电子元件(例如集成电路芯片、电子元器件等)进行物理保护和连接的过程。封装通常涉及将电子元件封装到外部保护壳或包装中,以确保其正常运作、连接到电路板并保护它们免受环境因素的影响。 封装的主要目标包括以下几个方面:…...

正在等待操作系统重新启动。 请重新启动计算机以安装autocad 2024。

正在等待操作系统重新启动。 请重新启动计算机以安装autocad 2024。 这是刚启动Autodesk 2024产品就弹出的弹窗,重启之后启动还是有这个 一直阻止安装程序运行 出现问题的原因是安装包存在问题 使用正确的安装包即可解决这个问题 需要的朋友查看图片或者评伦取…...

Windows电脑显示部分功能被组织控制

目录 问题描述 解决方法 总结 问题描述 如果你的电脑出现以上情况,建议你使用我这种方法(万不得已) 解决方法 原因就是因为当时你的电脑在激活的时候是选择了组织性激活的,所以才会不管怎么搞,都无法摆脱组织的控…...

Django模板加载与响应

前言 Django 的模板系统将 Python 代码与 HTML 代码解耦,动态地生成 HTML 页面。Django 项目可以配置一个或多个模板引擎,但是通常使用 Django 的模板系统时,应该首先考虑其内置的后端 DTL(Django Template Language,D…...

Python 内置函数详解 (4) 类型转换

Python 内置函数 Python3.11共有75个内置函数,其来历和分类请参考:Python 新版本有75个内置函数,你不会不知道吧_Hann Yang的博客-CSDN博客https://blog.csdn.net/boysoft2002/article/details/132520234 函数列表 abs aiter all …...

SpringBoot之Web原生组件注入

文章目录 前言一、原生注解方式注入二、Spring方式注入三、切换web服务器与定制化总结 前言 注入Web原生Servlet、Filter、Listeber以及切换Web服务器。 一、原生注解方式注入 官方文档 - Servlets, Filters, and listeners Servlet注入: WebServlet(urlPattern…...

[每周一更]-(第64期):Dockerfile构造php定制化镜像

利用php官网镜像php:7.3-fpm,会存在部分插件缺失的情况,自行搭建可适用业务的镜像,才是真理 Dockerhub 上 PHP 官方基础镜像主要分为三个分支: cli: 没有开启 CGI 也就是说不能运行fpm。只可以运行命令行。fpm: 开启了CGI&#x…...

若依不分离+Thymeleaf select选中多个回显

项目中遇到的场景&#xff0c;亲测实用 表单添加时&#xff0c;select选中多个&#xff0c;编辑表单时&#xff0c;select多选回显&#xff0c;如图 代码&#xff1a; // 新增代码 <label class"col-sm-3 control-label">通道&#xff1a;</label><…...

OCX 添加方法和事件 HTML调用ocx函数及回调 ocx又调用dll VS2017

ocx添加方法 类视图 最后面的XXXXXlib 右键 添加 添加方法。 其它默认 添加事件 类视图 最后面的XXXXX 右键 添加 添加事件。 这样编译就ocx可以了。 #include <iostream> #include <string> #include <comutil.h>CMFCActiveXControlSmartPosCtrl* …...

苹果iPhone手机使用草柴返利APP查询领取淘宝天猫京东优惠券如何取消关闭粘贴商品链接时的弹窗提示?

使用苹果手机在淘宝或京东复制商品链接&#xff0c;到草柴APP粘贴时总是弹窗提示&#xff0c;如何关闭苹果手机粘贴弹窗的提示&#xff1f; 苹果手机如何关闭粘贴弹窗提示&#xff1f; 1、在草柴APP内&#xff0c;点击底部「我的」接着点击「系统设置」进入&#xff1b; 2、进…...

主机安装elasticsearch后无法登陆

问题描述 2023年7月31日11点02分&#xff0c;主机安装elasticsearch后无法登陆&#xff0c;通过后台查看主机宕机状态&#xff0c;CPU达到100%&#xff0c;按业务侧要求执行重启操作后发现主机黑屏无法正常进入系统&#xff0c;系统卡死。 2&#xff0e;原因分析 2.1通过故障…...

【面试题精讲】JavaSe和JavaEE的区别

“ 有的时候博客内容会有变动&#xff0c;首发博客是最新的&#xff0c;其他博客地址可能会未同步,认准https://blog.zysicyj.top ” 首发博客地址[1] 文章更新计划[2] 系列文章地址[3] 1. 什么是 JavaSE 和 JavaEE? JavaSE&#xff08;Java Platform, Standard Edition&#…...

React 全栈体系(十五)

第八章 React 扩展 一、setState 1. 代码 /* index.jsx */ import React, { Component } from reactexport default class Demo extends Component {state {count:0}add ()>{//对象式的setState/* //1.获取原来的count值const {count} this.state//2.更新状态this.set…...

【逆向】(c++)分析pe结构,拉伸pe结构,缩小pe结构

建议大家认认真真写一遍&#xff0c;收获蛮大的&#xff0c;是可以加深对pe结构的理解&#xff0c;尤其是对指针的使用&#xff0c;和对win32的一些宏的定义的理解和使用。 #include <windows.h> #include <iostream> #include <string>using namespace std…...

PyTorch实战:常用卷积神经网络搭建结构速览

目录 前言 常用卷积神经网络 1.AlexNet 2.VGGNet 3.GoogLeNet 4.ResNet 总览 前言 PyTorch可以说是三大主流框架中最适合初学者学习的了&#xff0c;相较于其他主流框架&#xff0c;PyTorch的简单易用性使其成为初学者们的首选。这样我想要强调的一点是&#xff0c;框架…...

排序算法之【快速排序】

&#x1f4d9;作者简介&#xff1a; 清水加冰&#xff0c;目前大二在读&#xff0c;正在学习C/C、Python、操作系统、数据库等。 &#x1f4d8;相关专栏&#xff1a;C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 &#x1f44d…...

声明式调用 —— SpringCloud OpenFeign

Feign 简介 Spring Cloud Feign 是一个 HTTP 请求调用的轻量级框架&#xff0c;可以以 Java 接口注解的方式调用 HTTP 请求&#xff0c;而不用通过封装 HTTP 请求报文的方式直接调用 Feign 通过处理注解&#xff0c;将请求模板化&#xff0c;当实际调用的时候传入参数&#x…...

LuatOS-SOC接口文档(air780E)-- fota - 底层固件升级

fota.init(storge_location, len, param1)# 初始化fota流程 参数 传入值类型 解释 int/string fota数据存储的起始位置 如果是int&#xff0c;则是由芯片平台具体判断 如果是string&#xff0c;则存储在文件系统中 如果为nil&#xff0c;则由底层决定存储位置 int 数据存…...

第二章 Introduction

Armv8.4 架构引入了在安全状态下的虚拟化扩展。Arm SMMU v3.2 架构 [1] 增加了对安全流的第二阶段翻译的支持&#xff0c;以补充 Armv8.4 PE 中的安全 EL2 翻译体制。这些架构特性使得可以在安全状态下将彼此不信任的软件组件隔离开来。隔离是实现最小权限原则的机制&#xff1…...

WebGL 渲染三维图形作为纹理贴到另一个三维物体表面

目录 渲染到纹理 帧缓冲区对象和渲染缓冲区对象 帧缓冲区对象 帧缓冲区对象的结构 如何实现渲染到纹理 示例程序&#xff08;FramebufferObject.js&#xff09; 创建帧缓冲区对象&#xff08;gl.createFramebuffer&#xff08;&#xff09;&#xff09; gl.createFra…...

国庆《乡村振兴战略下传统村落文化旅游设计》许少辉八一新书行将售罄

国庆《乡村振兴战略下传统村落文化旅游设计》许少辉八一新书行将售罄 国庆《乡村振兴战略下传统村落文化旅游设计》许少辉八一新书行将售罄...

Source Insight 工具栏图标功能介绍

这篇文章并不介绍 Source Insight 的具体使用方法&#xff0c;这类教程网上有很多&#xff0c;这里只分析 Souce Insight 工具栏图标的功能。 文章目录 Source Insight 简介Souce Insight 工具栏文件操作新建&#xff08;CtrlN&#xff09;打开&#xff08;CtrlO&#xff09;保…...

模板与泛型编程-函数模板

本专栏由于缺少函数模板专题,我本以为这个不用讲解,但由于某些同学基础比较薄弱,特地在此补充一下。 函数模板的定义一般都在头文件中。 一、如何定义一个模板函数 下面是一个求和函数 template<typename T,typename U> auto Add(T a, U b) {return a + b; }int...

了解ActiveMQ、RabbitMQ、RocketMQ和Kafka的特点

ActiveMQ ActiveMQ是一种基于JMS&#xff08;Java消息服务&#xff09;规范的消息中间件&#xff0c;由Apache基金会开发和维护 核心组件和特点&#xff1a; Broker&#xff08;代理&#xff09;&#xff1a;ActiveMQ的核心组件是Broker&#xff0c;它负责接收、存储和路由消息…...

建筑网站首页大图/网站seo运营

触摸事件: 三种在规范中列出并获得跨移动设备广泛实现的基本触摸事件&#xff1a; 1.touchstart&#xff1a;手指放在一个DOM元素上。 2.touchmove&#xff1a;手指拖曳一个DOM元素。 3.touchend&#xff1a;手指从一个DOM元素上移开。 每个触摸事件都包括了三个触摸列表&#…...

深圳网页设计培训机构/郑州网站排名优化公司

局部性一个计算机程序常常具备良好的局部性。其含义是程序在未来总是倾向于访问那些最近使用过的数据周围附近的数据&#xff0c;或者是引用那个最近使用的数据本身。这就是局部性原理。 局部性通常包含两种形式&#xff1a; ①&#xff1a;时间局部性&#xff1a;一个被引用的…...

免费开源网站/国外搜索引擎排行榜

csc.exe使用来编译*.cs文件的&#xff0c;但必须要在安装目录下使用。所以需要设置一下环境变量。 C#的环境变量设置 1.“winR” 打开运行窗口&#xff0c;并输入 “cmd”&#xff1b; 2.运行“set path%path%;C:\Windows\Microsoft.NET\Framework\v4.0.30319”(不包含“”)。后…...

网站维护费用包括哪些/seo网站自动发布外链工具

分析 JUnit 框架源代码 理解 JUnit 测试框架实现原理和设计模式 文档选项打印本页 将此页作为电子邮件发送 级别&#xff1a; 中级 何 正华 , 软件工程师, IBM徐 晔 (yexucn.ibm.com ), 软件工程师, IBM, Software Group 2009 年 5 月 31 日 本文细致地描述了 JUnit 的代码实现…...

怎么让别人访问自己做的网站/南宁百度seo推广

2019独角兽企业重金招聘Python工程师标准>>> SVN地址:http://115.29.228.243:50029/svn/zdj_svn 用户名:jeasyframe 密码:jeasyframe 在svn下有两个文件夹, 其中code文件夹中为通用版本,支持mysql与sqlserver; oracle文件夹中为oracle专用版本,支持oracle10g以…...

可以做网络攻防的实验的网站/品牌推广的具体方法

Microsoft Office Visio绘画双箭头直线的具体步骤介绍作者:小鑫 来源:PC下载网时间:2019-07-19 15:27:03你们的工作中是不是也离不开Microsoft Office Visio呢?不过你们了解Microsoft Office Visio是怎么绘画双箭头直线吗?以下文章就为你们带来了Microsoft Office Visio绘画双…...