算法通过村第四关-栈青铜笔记|手写栈操作
文章目录
- 前言
- 1. 栈的基础概要
- 1.1 栈的特征
- 1.2 栈的操作
- 1.3 Java中的栈
- 2. 栈的实现(手写栈)
- 2.1 基于数组实现
- 2.2 基于链表实现
- 2.3 基于LinkedList实现
- 总结
前言
提示:我自己一个人的感觉很好 我并不想要拥有你 除非你比我的独处更加宜人 --瓦尔桑·希雷
1. 栈的基础概要
1.1 栈的特征
栈和队列是比较特殊的线性表,为什么特殊呢?(又称为访问受限的线性表)。栈常用于表达式、符号等运算的基础,也是递归的底层实现。理论上递归可以做的题目栈都是可以做的,只是有些问题用栈相对复杂一些。
栈的底层实现是我们常见的链表或者顺序表,栈与线性表的最大区别在于数据的存取操作被限制了,其插入和删除操作只允许在线性表的一端进行。一般而言,我们把允许操作的一端称为栈顶(top),不可以操作的一端称为栈底(bottom),同时插入元素的操作称为入栈(push)删除元素的操作称为出栈(pop)。若栈中没有任何元素,则称为空栈,栈的结构如图所示:
1.2 栈的操作
栈的常见操作主要有:
- push(E):增加一个元素E
- pop():弹出元素E
- peek():显示栈顶元素,但是不出栈
- empty():判断栈是否为空
我们在设计自己的栈的时候,不管是使用数组还是链表,都需要实现以上的几个方法。
一道经典的题目,入栈顺序为1234,所有可能的出栈序列是什么?
这个题是什么意思呢?举个例子,我们可以先让1,2入栈,然后2,1出栈,再让3,4入栈,然后一次出栈,就可以得到2143的序列。
4个元素的全排列有4!= 24,栈要求符合先进后出,根据这个条件我们可以排除:
1234 √ 1243 √ 1324 √ 1342 √ 1423 × 1432 √
2134 √ 2143 √ 2314 √ 2341 √ 2413 × 2431 √
3124 × 3142 × 3214 √ 3241 √ 3412 × 3421 √
4123 × 4132 × 4213 × 4231 × 4312× 4321 √
14中可能,10中不可能。
1.3 Java中的栈
Java中的栈,uitl中就提供了栈Stack类,使用起来也不复杂,我们看一下例子:
import java.util.Stack;public class MainTest {public static void main(String[] args) {Stack<Integer> stack = new Stack<>();// 入栈stack.push(1);stack.push(2);stack.push(3);stack.push(4);// 出栈stack.pop();while (!stack.isEmpty()) {// 展示但是不删除System.out.println(stack.peek());// 删除System.out.println(stack.pop());}}
}
2. 栈的实现(手写栈)
我们在学习栈的过程中,需要了解一些问题,top栈顶指针的指向,有的地方指向栈顶再往上一个空位,有的地方指向栈顶元素。我们确定好设计就行,(根据题目调整,有时候也可以直接问面试官 top指向哪里)这里采用指向栈顶空位置。
如果我们自己要实现栈,可以使用数组,链表Java中提供了LinkedList三种基本实现方式,我们都可以看一下。
2.1 基于数组实现
采用顺序表实现的栈,内部以数组为基础,实现对元素的存取操作。在应用中还要之一每次入栈之前要确保栈的容量是否足够,不够需要考虑扩容的问题。
我们画一下入栈的过程:
出栈的过程:
出栈先将栈顶元素取出,然后top–
展示代码:
import java.util.Arrays;
class Mystack<T> {private Object[] stack;// 栈顶指针private int top;
public Mystack() {// 初始长度为10stack = new Object[10];}
/*** 判断是否为空** @return*/public boolean isEmpty() {return top == 0;}
/*** 返回栈顶元素但是不删除** @return*/public T peek() {T t = null;if (top > 0) {t = (T) stack[top - 1];}return t;}
/*** 入栈操作** @param t*/public void push(T t) {expandCapacity(top + 1);stack[top] = t;top++;}
public T pop() {T t = peek();if (!isEmpty()) {// 清除元素stack[top - 1] = null;top--;}return t;}
/*** 确保容量** @param size*/public void expandCapacity(int size) {int len = stack.length;if (size > len) {size = size * 3 / 2 + 1;stack = Arrays.copyOf(stack, size);}}
public static void main(String[] args) {Mystack<String> stack = new Mystack<>();System.out.println(stack.peek());// nullSystem.out.println(stack.isEmpty());// truestack.push("java");stack.push("is");stack.push("beautiful");stack.push("language");System.out.println(stack.pop());// languageSystem.out.println(stack.isEmpty());// falseSystem.out.println(stack.peek()); // beautiful}
}
2.2 基于链表实现
链表用来实现栈也很简单,头插法(在头部操作链表就可以了)。
我们先画个图:
在链表的那一章我们介绍过没有虚拟节点时对链表头部元素进行插入和删除的操作,不记得的可以回顾一下算法通过村第二关-链表青铜笔记_师晓峰的博客-CSDN博客,这里基于链表实现栈的操作时完全一样的。
代码实现:
class ListStack<T> {// 构造节点class Node<T> {public T t;private Node next;}public Node<T> head;ListStack() {head = null;}/*** 入栈操作* @param t*/public void push(T t) {if (t == null) {throw new IllegalStateException("参数不能为空");}// 头节点为空if (head == null) {head = new Node<T>();head.t = t;head.next = null;}else {Node<T> temp = head;head = new Node<T>();head.t = t;head.next = temp;}}/*** 出栈操作* @return*/public T pop(){if (head == null) {return null;}T t = head.t;head = head.next;return t;}public T peek(){if (head == null) {return null;}return head.t;}/*** 判断是否为空** @return*/public boolean isEmpty() {return head == null;}public static void main(String[] args) {ListStack stack = new ListStack();System.out.println(stack.isEmpty());// truestack.push("Java");stack.push("is");stack.push("beautiful");System.out.println(stack.peek());// beautifulSystem.out.println(stack.pop());// beautifulSystem.out.println(stack.isEmpty());// false}
}
2.3 基于LinkedList实现
这里就很简单了,直接上代码就行;
import java.util.LinkedList;/*** 基于Java的LinkedList来实现栈* @param <T>*/
public class LinkedListStack<T> {private LinkedList<T> ll;LinkedListStack(){ll = new LinkedList<T>();}/*** 入栈操作* @param t*/public void push( T t){ll.addFirst(t);}/*** 出栈但是不删除* @return*/public T peek(){T t = null;if (!ll.isEmpty()){t = ll.peek();}return t;}public T pop(){return ll.removeFirst();}public boolean isEmpty(){return ll.isEmpty();}public static void main(String[] args) {LinkedListStack<String> stack = new LinkedListStack();System.out.println(stack.isEmpty());//trueSystem.out.println(stack.peek());//nullstack.push("java");stack.push("is");stack.push("beautiful");System.out.println(stack.peek());//beautifulSystem.out.println(stack.pop());//beautifulSystem.out.println(stack.isEmpty());//false}
}
总结
提示:记住栈的特性,先进后出
相关文章:
算法通过村第四关-栈青铜笔记|手写栈操作
文章目录 前言1. 栈的基础概要1.1 栈的特征1.2 栈的操作1.3 Java中的栈 2. 栈的实现(手写栈)2.1 基于数组实现2.2 基于链表实现2.3 基于LinkedList实现 总结 前言 提示:我自己一个人的感觉很好 我并不想要拥有你 除非你比我的独处更加宜人 --…...
Python计算加速利器
迷途小书童的 Note 读完需要 6分钟 速读仅需 2 分钟 1 简介 Python 是一门应用非常广泛的高级语言,但是,长久以来,Python的运行速度一直被人诟病,相比 c/c、java、c#、javascript 等一众高级编程语言,完全没有优势。 那…...
PyTorch 深度学习实践 第10讲刘二大人
总结: 1.输入通道个数 等于 卷积核通道个数 2.卷积核个数 等于 输出通道个数 1.单通道卷积 以单通道卷积为例,输入为(1,5,5),分别表示1个通道,宽为5,高为5。假设卷积核大小为3x3,…...
Linux特殊指令
目录 1.dd命令 2.mkfs格式化 3.df命令 4.mount实现硬盘的挂载 5.unshare 1.dd命令 dd命令可以用来读取转换并输出数据。 示例一: if表示infile,of表示outfile。这里的/dev/zero是一个特殊文件,会不断产生空白数据。 bs表示复制一块的大…...
MPI之主从模式的一般编程示例
比如,我们可以选举0号进程为master进程,其余进程为slaver进程 #include "mpi.h" #include <unistd.h> #include <iostream>int main(int argc, char *argv[]) {int err MPI_Init(&argc,&argv);int rank,size;MPI_Comm_r…...
基于野狗算法优化的BP神经网络(预测应用) - 附代码
基于野狗算法优化的BP神经网络(预测应用) - 附代码 文章目录 基于野狗算法优化的BP神经网络(预测应用) - 附代码1.数据介绍2.野狗优化BP神经网络2.1 BP神经网络参数设置2.2 野狗算法应用 4.测试结果:5.Matlab代码 摘要…...
C语言面向对象的编程思想
面向对象编程 面向对象编程Object-Oriented Programming,OOP) 作为一种新方法,其本质是以建立模型体现出来的抽象思维过程和面向对象的方法。模型是用来反映现实世界中事物特征的。任何一个模型都不可能反映客观事物的一切具体特征࿰…...
MPI之非阻塞通信中通信完成检测接口简介
在之前的文章中,简单的写了一个非阻塞的通信代码介绍最最基本的使用: int main(int argc, char *argv[]) {int err MPI_Init(&argc,&argv);int rank,size;MPI_Comm_rank(MPI_COMM_WORLD,&rank);MPI_Comm_size(MPI_COMM_WORLD, &size);…...
Excel:如何实现分组内的升序和降序?
一、POWER 1、构建辅助列D列,在D2单元格输入公式: -POWER(10,COUNTA($A$2:A2)3)C2 2、选中B1:D10,注意不能宣导A列的合并单元格,进行以下操作: 3、删除辅助列即可 二、COUNTA 第一步,D2建立辅助列…...
深度学习论文: Segment Any Anomaly without Training via Hybrid Prompt Regularization
深度学习论文: Segment Any Anomaly without Training via Hybrid Prompt Regularization Segment Any Anomaly without Training via Hybrid Prompt Regularization PDF: https://arxiv.org/pdf/2305.10724.pdf PyTorch代码: https://github.com/shanglianlm0525/CvPytorch Py…...
【算法训练-字符串】一 最长无重复子串
废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是最长无重复子串或最长无重复子数组,这类题目出现频率还是很高的。 最长无重复子串【MID】 先来看字符串数据结构的题目 题干 解题思…...
【数据结构】手撕顺序表
一,概念及结构 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储; 在数组上完成数据的增删查改。 1, 静态顺序表:使用定长数组存储元素。 2.,动态顺序表࿱…...
景联文科技数据标注:人体关键点标注用途及各点的位置定义
人体关键点标注是一种计算机视觉任务,指通过人工的方式,在指定位置标注上关键点,例如人脸特征点、人体骨骼连接点等,常用来训练面部识别模型以及统计模型。这些关键点可以表示图像的各个方面,例如角、边或特定特征。在…...
typescript基础之never
TypeScript 的 never 类型是一种特殊的类型,它表示的是那些永远不存在的值的类型。例如,一个抛出异常或无限循环的函数的返回值类型就是 never,因为它们永远不会返回任何值。never 类型是所有类型的子类型,也就是说,任…...
电子电路学习笔记之NCP304LSQ37T1G ——超低电流电压检测器
超低电流电压检测器是一种专门用于检测极小电流值的设备。它们常用于电子元件或电路中,用于监测电流的存在和程度。这些检测器通常具有高灵敏度和高精度,能够测量微安级别或更小的电流。 超低电流电压检测器的应用领域广泛,例如电池管理系统…...
【计算机组成原理】一文快速入门,很适合JAVA后端看
作者简介: CSDN内容合伙人、CSDN新星计划导师、JAVA领域优质创作者、阿里云专家博主,计算机科班出身、多年IT从业经验、精通计算机核心理论、Java SE、Java EE、数据库、中间件、分布式技术,参加过国产中间件的核心研发,对后端有…...
10万字智慧政务大数据平台项目建设方案222页[Word]
导读:原文《10万字智慧政务大数据平台项目建设方案222页[Word]》(获取来源见文尾),本文精选其中精华及架构部分,逻辑清晰、内容完整,为快速形成售前方案提供参考。 1.1 项目建设目标 推进市一级政府搭建数字政府建设的规划要求,结合市一级政府“互联网+政务服务”建设…...
Python-主线程控制子线程-4
需求:在Python-主线程控制子线程-3的基础上,新增使用UDP接收指令功能,代替从键盘输入指令 # 修改后的程序,主线程可以获取子线程的结果 import threading import time import queue import tracebackfrom loguru import logger i…...
设计模式二十二:策略模式(Strategy Pattern)
定义一系列算法,将每个算法封装成独立的对象,并使这些对象可互相替换。这使得在运行时可以动态地选择算法,而不必改变使用算法的客户端代码。策略模式的主要目标是将算法的定义与使用分离,使得客户端可以根据需要灵活地选择和切换…...
【c语言】结构体内存对齐,位段,枚举,联合
之前学完结构体,有没有对结构体的大小会很疑惑呢??其实结构体在内存中存储时会存在内存对齐,捎带讲讲位段,枚举,和联合,跟着小张一起学习吧 结构体内存对齐 结构体的对齐规则: 第一个成员在与结…...
干货丨软件测试行业迎来新时代,AI将成为主流技术?
随着科技日新月异的发展,人工智能正逐渐渗透到我们生活的各方各面,从智能语音助手到自动驾驶汽车、从智能家居到人脸识别技术,AI正以其卓越的智能和学习能力引领着新时代的发展方向。 在这个快速演进的时代中,软件测试领域也受到了…...
MacOS goland go1.21 debug问题
安装dlv brew install dlv 安装之后在终端会显示所在目录 类似/usr/local/Cellar/delve/1.21.0/bin 配置goland 在文件系统中找到goland 右击选择show package contents -> Contents -> plugins -> go 尝试替换 其中对应系统 的 dlv 结果还是不行 然后打开应用gol…...
python 笔记(1)——基础和常用部分
目录 1、print 输出不换行 2、格式化输出字符串 3、浮点数的处理 4、进制转换和ASCII与字符间的转换 5、随机数 6、字符串截取和内置方法 6-1)字符串截取 6-2)字符串内置方法 7、元组、列表,及其遍历方式 7-1)列表常用内…...
kafka架构和原理详解
Apache Kafka 是一个分布式流数据平台,用于高吞吐量、持久性、可扩展的发布和订阅消息。它具有高度的可靠性,被广泛用于构建实时数据流处理、日志收集和数据管道等应用。 基本架构 1. 主题(Topic): 主题是消息的逻辑分类生产者将消息发布到特定的主题中,而消费者可以订阅…...
wsl Ubuntu中非root的普通用户怎么直接执行docker命令
docker需要root权限,如果希望非root用户直接使用docker命令,而不是使用sudo,可以选择将该用户加入到docker用户组。 sudo groupadd docker:添加到groupadd用户组(已经有docker用户组,所以可以不用再新增do…...
Web开发模式、API接口、restful规范、序列化和反序列化、drf安装和快速使用、路由转换器(复习)
一 Web开发模式 1. 前后端混合开发模式 前后端混合开发模式是一种开发方式,将前端和后端的开发工作结合在一起,以加快项目的开发速度和 提高协作效率。这种模式通常用于快速原型开发、小型项目或敏捷开发中。在前后端混合开发模式中,前端和…...
<AMBA总线篇> AXI总线协议介绍
目录 01 AXI协议简介 AXI协议特性 AXI协议传输特性 02 AXI协议架构 AXI协议架构 write transaction(写传输) read tramsaction(读传输) Interface and interconnect 典型的AXI系统拓扑 03 文章总结 大家好,这里是程序员杰克。一名平平无奇的嵌入式软件工程…...
一个简单的Python网络爬虫教程
网络爬虫是一种自动获取网页内容的程序,它可以从互联网上的网站中提取数据并进行分析。本教程将带您逐步了解如何使用 Python 构建一个简单的网络爬虫。 注意:在进行网络爬虫时,请遵守网站的使用条款和法律法规,避免对目标网站造…...
YARN资源管理框架论述
一、简介 为了实现一个Hadoop集群的集群共享、可伸缩性和可靠性,并消除早期MapReduce框架中的JobTracker性能瓶颈,开源社区引入了统一的资源管理框架YARN。 YARN是将JobTracker的两个主要功能(资源管理和作业调度/监控)分离&…...
Unity查找资源依赖关系
这个方法主要是发现资源乱用的情况,对应的逻辑可能要改一个才能用到自己的项目里面 [MenuItem("Tools/Prefab/查找选中资源依赖关系", false, 0)] public static void FindDependencies() { foreach (var guid in Selection.assetGUIDs…...
【操作系统】聊聊局部性原理是如何提升性能的
对于目前数据主导的系统,大多数都是Java/Go 技术栈MySQL,但是随着时间的推移,数据库数据的数据量过多,并且会频繁访问热点数据,为了提升系统的性能,一般都是加入缓存中间件、Redis。 局部性原理 我们知道…...
多线程应用——单例模式
单例模式 文章目录 单例模式一.什么是单例模式二.如何实现1.口头实现2.利用语法特性 三.实现方式(饿汉式懒汉式)1.饿汉式2.懒汉式3.线程安全的单例模式4.双重检查锁5.禁止指令重排序 一.什么是单例模式 单例模式(Singleton Patternÿ…...
几种在JavaScript中创建对象的方式!
聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 字面量方式⭐ 构造函数方式⭐ Object.create()方式⭐ 工厂函数方式⭐ ES6类方式⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门…...
java项目mysql转postgresql
特殊函数 : mysql: find_in_set(?, ancestors) postgresql: ? ANY (string_to_array(ancestors,,)) mysql: date_format(t1.oper_time, %Y-%m-%d) postgresql: rksj::date to_char(inDate,YYYY-MM-DD) mysql&am…...
SpringBoot Mybatis 多数据源 MySQL+Oracle
一、背景 在SpringBoot Mybatis 项目中,需要连接 多个数据源,连接多个数据库,需要连接一个MySQL数据库和一个Oracle数据库 二、依赖 pom.xml <dependencies><dependency><groupId>org.springframework.boot</groupId&…...
(笔记五)利用opencv进行图像几何转换
参考网站:https://docs.opencv.org/4.1.1/da/d6e/tutorial_py_geometric_transformations.html (1)读取原始图像和标记图像 import cv2 as cv import numpy as np from matplotlib import pyplot as pltpath r"D:\data\flower.jpg&qu…...
【Flutter】Flutter 使用 fluttertoast 实现显示 Toast 消息
【Flutter】Flutter 使用 fluttertoast 实现显示 Toast 消息 文章目录 一、前言二、安装和基础使用三、不同平台的支持情况四、如何自定义 Toast五、在实际业务中的应用六、完整的业务代码示例(基于 Web 端)七、总结 一、前言 在这篇文章中,…...
nowcoder NC236题 最大差值
目录 题目描述: 示例1 示例2 题干解析: 暴力求解: 代码展示: 优化: 代码展示: 题目跳转https://www.nowcoder.com/practice/a01abbdc52ba4d5f8777fb5dae91b204?tpId128&tqId33768&ru/exa…...
TCP/IP五层模型、封装和分用
1.网络通信基础2.协议分层OSI七层协议模型TCP/IP五层/四层协议模型【重点】 3. 封装&分用 1.网络通信基础 IP地址:表示计算机的位置,分源IP和目标IP;举个例子:买快递,商家从上海发货,上海就是源IP&…...
LeetCode 面试题 01.08. 零矩阵
文章目录 一、题目二、C# 题解 一、题目 编写一种算法,若M N矩阵中某个元素为0,则将其所在的行与列清零。 点击此处跳转题目。 示例 1: 输入: [ [1,1,1], [1,0,1], [1,1,1] ] 输出: [ [1,0,1], [0,0,0], [1,0,1] ] 示…...
Qt应用开发(基础篇)——进度条 QProgressBar
一、前言 QProgressBar类继承于QWidget,是一个提供了横向或者纵向进度条的小部件。 QProgressBar进度条一般用来显示用户某操作的进度,比如烧录、导入、导出、下发、上传、加载等这些需要耗时和分包的概念,让用户知道程序还在正常的执行中。 …...
108页石油石化5G智慧炼化厂整体方案PPT
导读:原文《108页石油石化5G智慧炼化厂整体方案PPT》(获取来源见文尾),本文精选其中精华及架构部分,逻辑清晰、内容完整,为快速形成售前方案提供参考。以下是部分内容,...
Codeforces 1625E2 括号树 + BIT
题意 传送门 Codeforces 1625E2 Cats on the Upgrade (hard version) 题解 首先利用栈将原始字符串转换为合法的 RBS,不能匹配的括号设为 ‘.’。根据匹配的括号序列构造树,具体而言,遇到左括号,则新建节点向下递归,…...
PHP命令行CLI的使用
PHP命令行界面 PHP命令行界面(CLI)是一种使用命令行(终端)来运行PHP脚本的方式,与在Web服务器环境下运行PHP不同。CLI提供了一种与操作系统交互的方式,能够在命令行中直接执行PHP代码。 以下是一些与PHP命…...
近期嵌软线下笔试题记录
1、以下代码的输出结果是? #include <stdio.h> #include <string.h>int main() {int a,b,c,d;a 10;b a; //a先赋值给b,然后自增1c a; //a自增1后赋值给cd 10*a; //先进行运算然后a自增1printf("b,c,d:%d…...
基于MYSQL的主从同步和读写分离
目录 一.完成MySQL主从同步(一主两从) 1.主库配置 2.建立同步账号 3.锁表设置只读 4.备份数据库数据 5.主库备份数据上传到从库 6.从库上还原备份 7.解锁 8.从库上设定主从同步 9.启动从库同步开关 10.检查状态 二.基于MySQL一主两从配置&…...
java八股文面试[多线程]——合适的线程数是多少
知识来源: 【并发与线程】 合适的线程数量是多少?CPU 核心数和线程数的关系?_哔哩哔哩_bilibili 【2023年面试】程序开多少线程合适_哔哩哔哩_bilibili...
Linux系统下vim常用命令
一、基础命令: v:可视模式 i:插入模式 esc:命令模式下 :q :退出 :wq :保存并退出 ZZ:保存并退出 :q! :不保存并强制退出二、在Esc下: dd : 删除当前行 yy:复制当前行 p:复制已粘贴的文本 u:撤销上一步 U:…...
【2023】LeetCode HOT 100——链表
目录 1. 相交链表1.1 C++实现1.2 Python实现1.3 时空分析2. 反转链表2.1 C++实现2.2 Python实现2.3 时空分析3. 回文链表3.1 C++实现3.2 Python实现3.3 时空分析4. 环形链表4.1 C++实现4.2 Python实现4.3 时空分析5. 环形链表 II5.1 C++实现5.2 Python实现...
智能井盖传感器,物联网智能井盖系统
随着城市人口的不断增加和城市化进程的不断推进,城市基础设施的安全和可靠性变得愈发重要,城市窨井盖作为城市基础设施重要组成部分之一,其安全性事关城市安全有序运行和居民生产生活安全保障。 近年来,各地都在加强城市窨井盖治理…...