数据结构-03-栈

1-栈的结构和特点

先进后出,后进先出 是栈的特点;

       从图中,我们看到A入栈先放入底部,然后依次B和C;出栈的顺序依次是C-B-A;这种结构只能在一端操作。所以当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出(last-in-first-out(LIFO) )、先进后出的特性,我们就应该首选“栈”这种数据结构

2-栈的实现

我们可以使用数组和链表来实现栈,下面我们基于数组来现实一个基础功能的栈。

@Getter
@Setter
public class MyArrayStack {private Object[] elementData;//存储元素的数组private int elementCount;//元素的个数private int capacity;//容量public MyArrayStack(int capacity) {this.elementData = new Object[capacity];this.capacity = capacity;this.elementCount = 0;}// 入栈操作public boolean push(Objectitem) {if (elementCount == capacity) return false;elementData[elementCount] = item;++elementCount;return true;}// 出栈操作public Object pop() {if (elementCount == 0) return null;Object tmp = elementData[elementCount-1];--elementCount;return tmp;}
}@Slf4j
public class TestStack {public static void main(String[] args) {MyArrayStack stack=new MyArrayStack(3);log.info("push1={}",stack.push("hello"));log.info("push2={}",stack.push("java"));log.info("push3={}",stack.push("world"));log.info("push4={}",stack.push("china"));log.info("pop1={}",stack.pop());log.info("pop2={}",stack.pop());log.info("pop3={}",stack.pop());log.info("pop4={}",stack.pop());}
}

控制台输出:

10:19:38.417 [main] INFO  c.y.d.statck.TestStack - push1=true
10:19:38.423 [main] INFO  c.y.d.statck.TestStack - push2=true
10:19:38.423 [main] INFO  c.y.d.statck.TestStack - push3=true
10:19:38.424 [main] INFO  c.y.d.statck.TestStack - push4=false
10:19:38.424 [main] INFO  c.y.d.statck.TestStack - pop1=world
10:19:38.424 [main] INFO  c.y.d.statck.TestStack - pop2=java
10:19:38.424 [main] INFO  c.y.d.statck.TestStack - pop3=hello
10:19:38.424 [main] INFO  c.y.d.statck.TestStack - pop4=null

当然上面代码是简易的栈实现:还有优化的空间,比如支持泛型,支持扩容等功能;可以自行实现。

入栈、出栈只涉及栈顶个别数据的操作,所以时间复杂度都是O(1)

如何基于数组实现一个可以支持动态扩容的栈呢?当数组空间不够时,我们就重新申请一块更大的内存,将原来数组中数据统统拷贝过去。这样就实现了一个支持动态扩容的数组。Java中也有栈Stack实现的代码(支持泛型和扩容)。

3-栈的使用LeetCode

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 第20题,判断有效括号就可以使用栈这种结构来解决。

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

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

相关文章

模型层——单表操作

单表操作 一 ORM简介 查询数据层次图解:如果操作mysql,ORM是在pymysq之上又进行了一层封装 MVC或者MTV框架中包括一个重要的部分,就是ORM,它实现了数据模型与数据库的解耦,即数据模型的设计不需要依赖于特定的数据库…

线性规划问题

线性规划问题: 将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规划问题 一般线性规划问题的描述: 为了解决这类问题,首先需要确定问题的决策变量:然后确定问题的目标,并将目标表示为决策变量的线性函数;最后找出问…

Spring Security 6.x 系列(8)—— 源码分析之配置器SecurityConfigurer接口及其分支实现

一、前言 本章主要内容是关于配置器的接口架构设计,任意找一个配置器一直往上找,就会找到配置器的顶级接口:SecurityConfigurer。 查看SecurityConfigurer接口的实现类情况: 在 AbstractHttpConfigurer 抽象类的下面可以看到所有…

利用异或、取反、自增bypass_webshell_waf

目录 引言 利用异或 介绍 eval与assert 蚁剑连接 进阶题目 利用取反 利用自增 引言 有这样一个waf用于防御我们上传的文件: function fun($var): bool{$blacklist ["\$_", "eval","copy" ,"assert","usort…

pip的基本命令和使用

pip 简介 pip是Python官方的包管理器,可以方便地安装、升级和卸载Python包。 pip 常用命令 显示版本和路径 pip --version获取帮助 pip --help升级pip和升级包 pip install --upgrade pip # Linux/macOS pip install -U pip # windowspip install…

每日一练【盛最多水的容器】

一、题目描述 11. 盛最多水的容器 给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明&…

Qt Creator使用Heob检测内存泄漏

开发环境:win10 qt5.12.0 编译环境:MinGW 使用内存泄漏排查工具heob步骤如下: 第一步:下载heob.exe--注:我本机仅有heob.exe还不行,提示如下 所以需要下载heob和Dwarfstack,然后把他们放到同级目录下,我已经下载并且…

Mybatis中的设计模式

Mybatis中的设计模式 Mybatis中使用了大量的设计模式。 以下列举一些看源码时,觉得还不错的用法: 创建型模式 工厂方法模式 DataSourceFactory 通过不同的子类工厂,实例化不同的DataSource TransactionFactory 通过不同的工厂&#xff…

js moment时间范围拿到中间间隔时间

2023.11.27今天我学习了如何对只返回的开始时间和结束时间做处理,比如后端返回了: [time:{start:202301,end:202311}] 我们需要把中间的间隔渲染出来。 [202301,202302,202303,202304,202305,202306,202307,202308,202309,202310,202311] 利用moment…

01 高等数学.武忠祥.0基础

第一章 函数与极限 01映射与函数 02 函数概念 对应法则 定义域 常见函数 函数的几种特性 周期函数不一定有最小周期。 涉及额外与复习 存在与任意的关系

Star 10.4k!推荐一款国产跨平台、轻量级的文本编辑器,内置代码对比功能

notepad 相信大家从学习这一行就开始用了,它是开发者/互联网行业的上班族使用率最高的一款轻量级文本编辑器。但是它只能在Windows上进行使用,而且正常来说是收费的(虽然用的是pj的)。 对于想在MacOS、Linux上想使用,…

关于使用百度开发者平台处理语音朗读问题排查

错误信息:"convert_offline": false, "err_detail": "16: Open api characters limit reach 需要领取完 识别和合成都要有

Clean 架构下的现代 Android 架构指南

Clean 架构下的现代 Android 架构指南 Clean 架构是 Uncle Bob 提出的一种软件架构,Bob 大叔同时也是 SOLID 原则的命名者。 Clean 架构图如下: 这张图描述的是整个软件系统的架构,而不是单体软件,其中至少包括服务端以及客户端…

【Java】类和对象之超级详细的总结!!!

文章目录 前言1. 什么是面向对象?1.2面向过程和面向对象 2.类的定义和使用2.1什么是类?2.2类的定义格式2.3类的实例化2.3.1什么是实例化2.3.2类和对象的说明 3.this引用3.1为什么会有this3.2this的含义与性质3.3this的特性 4.构造方法4.1构造方法的概念4…

ElasticSearch学习笔记(一)

计算机软件的学习,最重要的是举一反三,只要大胆尝试,认真验证自己的想法就能收到事办功倍的效果。在开始之前可以看看别人的教程做个快速的入门,然后去官方网站看看官方的教程,有中文教程固然是好,没有中文…

dcat admin日志扩展 dcat-log-viewer 遇到的问题记录

扩展地址: https://github.com/duolabmeng6/dcat-log-viewer 问题描述: 使用很简单,直接安装扩展包,开启扩展就可以了,会自动生成菜单。 之前在别的系统用过,没问题,今天在一个新的系统用的时…

【网络奇缘】- 计算机网络|分层结构|深入探索TCP/IP模型|5层参考模型

​ 🌈个人主页: Aileen_0v0🔥系列专栏: 一见倾心,再见倾城 --- 计算机网络~💫个人格言:"没有罗马,那就自己创造罗马~" 目录 OSI参考模型与TCP/IP参考模型相同点 OSI参考模型与TCP/IP参考模型不同点 面向连接三阶段&#xff08…

单片机系统

我们来看单片机 的例子,读者可能会担心单片机(又称MCU,或微控制器) 过于专业而无法理解。完全没必要!在这里我们仅借它谈论一下有关时间的话题,顺带提一下单片机系统的概念。 单片机顾名思义是集成到一个芯…

基于SSM框架的网上书店系统

基于SSM框架的网上书店系统 文章目录 基于SSM框架的网上书店系统 一.引言二.系统设计三.技术架构四.功能实现五.界面展示六.源码获取 一.引言 随着互联网的普及和电子商务的快速发展,网上书店系统成为了现代人购买图书的主要方式之一。网上书店系统不仅提供了便捷的…

Redis队列stream,Redis多线程详解

Redis 目前最新版本为 Redis-6.2.6 ,会以 CentOS7 下 Redis-6.2.4 版本进行讲解。 下载地址: https://redis.io/download 安装运行 Redis 很简单,在 Linux 下执行上面的 4 条命令即可 ,同时前面的 课程已经有完整的视…