Java中的Stack与Queue

news/2024/3/29 4:02:25/文章来源:https://blog.csdn.net/weixin_52758364/article/details/129165167

文章目录

  • 一、栈的概念及使用
    • 1.1 概念
    • 1.2 栈的使用
    • 1.3 栈的模拟实现
  • 二、队列的概念及使用
    • 2.1 概念
    • 2.2 队列的使用
    • 2.3 双端队列(Deque)
  • 三、相关OJ题
    • 3.1 用队列实现栈。
    • 3.2 用栈实现队列。
  • 总结

一、栈的概念及使用

1.1 概念

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端栈顶,另一端称为栈底。栈中的数据元素遵循后进先出的原则。

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶

出栈:栈的删除操作叫做出栈,出数据在栈顶

1.2 栈的使用

方法功能
Stack()构造一个空的栈
E push(E e)将e入栈,并返回e
E pop()将栈顶元素出栈并返回
E peek()获取栈顶元素
int size()获取栈中有效元素个数
boolean empty()检测栈是否为空
public static void main(String[] args) {Stack<Integer> s = new Stack();s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size()); // 获取栈中有效元素个数---> 4System.out.println(s.peek()); // 获取栈顶元素---> 4s.pop(); // 4出栈,栈中剩余1 2 3,栈顶元素为3System.out.println(s.pop()); // 3出栈,栈中剩余1 2 栈顶元素为3if(s.empty()){System.out.println("栈空");}else{System.out.println(s.size());}
}

1.3 栈的模拟实现

在这里插入图片描述
从上图中可以看到,Stack继承了Vector,Vector和ArrayList类似,都是动态的顺序表,不同的是Vector是线程安全的。

public class MyStack {int[] array;int size;public MyStack(){array = new int[3];}public int push(int e){ensureCapacity();array[size++] = e;return e;}public int pop(){int e = peek();size--;return e;}public int peek(){if(empty()){throw new RuntimeException("栈为空,无法获取栈顶元素");}return array[size-1];}public int size(){return size;}public boolean empty(){return 0 == size;}private void ensureCapacity(){if(size == array.length){array = Arrays.copyOf(array, size*2);}}
}

二、队列的概念及使用

2.1 概念

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出的特点。

入队列:进行插入操作的一端称为队尾

出队列:进行删除操作的一端称为队头

2.2 队列的使用

在java中,Queue是个接口,底层是通过链表实现的。
在这里插入图片描述

方法功能
boolean offer(E e)入队列
E pool()出队列
peek()获取队头元素
int size()获取队列中有效元素个数
boolean isEmpty()检测元素是否为空

注意:Queue是个接口,在实例化时必须实例化LinkedList的对象,因为LinkedList实现了Queue接口。

public static void main(String[] args) {Queue<Integer> q = new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5); // 从队尾入队列System.out.println(q.size());System.out.println(q.peek()); // 获取队头元素q.poll();System.out.println(q.poll()); // 从队头出队列,并将删除的元素返回if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());}
}

2.3 双端队列(Deque)

双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,deque是"double ended queue"的简称。那就说明元素可以从队头出队和入队,也可以从队尾出队和入队。

Deque是一个接口,使用时必须创建LinkedList的对象。

在实际工程中,使用Deque接口是比较多的,栈和队列均可以使用该接口。

Deque<Integer> stack = new ArrayDeque<>(); //双端队列的线性实现
Deque<Integer> queue = new LinkedList<>(); //双端队列的链式实现

三、相关OJ题

3.1 用队列实现栈。

OJ链接

代码如下:

class MyStack {private Queue<Integer> qu1;private Queue<Integer> qu2;public MyStack() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}public void push(int x) {if(!qu1.isEmpty()) {qu1.offer(x);}else if (!qu2.isEmpty()) {qu2.offer(x);}else  {qu1.offer(x);}}public int pop() {if(empty()) {return -1;}if(!qu1.isEmpty()) {int size = qu1.size();for (int i = 0; i < size-1; i++) {int val = qu1.poll();qu2.offer(val);}return qu1.poll();}else  {int size = qu2.size();for (int i = 0; i < size-1; i++) {int val = qu2.poll();qu1.offer(val);}return qu2.poll();}}public int top() {if(empty()) {return -1;}if(!qu1.isEmpty()) {int size = qu1.size();int val = -1;for (int i = 0; i < size; i++) {val = qu1.poll();qu2.offer(val);}return val;}else  {int size = qu2.size();int val = -1;for (int i = 0; i < size; i++) {val = qu2.poll();qu1.offer(val);}return val;}}public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}

3.2 用栈实现队列。

OJ链接

代码如下:

class MyQueue {private Stack<Integer> stack1;private Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int x) {stack1.push(x);}public int pop() {if(empty()) {return -1;}if(stack2.empty()) {while (!stack1.empty()) {stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if(empty()) {return -1;}if(stack2.empty()) {while (!stack1.empty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
}

总结

以上就是今天要讲的内容,本文仅仅简单介绍了栈与队列的概念及其使用,栈与队列在解决实际问题中有着很大的作用,我们需要多练习,熟能生巧。

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

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

相关文章

Linux系统安装MySQL8.0版本详细教程【亲测有效】

首先官网下载安装包&#xff1a;https://downloads.mysql.com/archives/community/ 一、上传到安装服务器 二、解压 tar -xvf mysql-8.0.31-linux-glibc2.12-x86_64.tar.xz三、移动位置并重新命名 mv mysql-8.0.31-linux-glibc2.12-x86_64 /usr/local/mysql四、创建mysql用户…

Docker 如何配置镜像加速

Docker 镜像加速 国内从 DockerHub 拉取镜像有时会遇到困难&#xff0c;此时可以配置镜像加速器。Docker 官方和国内很多云服务商都提供了国内加速器服务&#xff0c;例如&#xff1a; 科大镜像&#xff1a;https://docker.mirrors.ustc.edu.cn/网易&#xff1a;https://hub-…

代码随想录【Day21】| 530. 二叉搜索树的最小绝对差、501. 二叉搜索树中的众数、236. 二叉树的最近公共祖先

530. 二叉搜索树的最小绝对差 题目链接 题目描述&#xff1a; 给你一棵所有节点为非负值的二叉搜索树&#xff0c;请你计算树中任意两节点的差的绝对值的最小值。 示例&#xff1a; 提示&#xff1a;树中至少有 2 个节点。 难点&#xff1a; 解答错误&#xff01;仅考虑了…

【Npde.js】express以及nodemon

express初始Express什么是Express不使用Express可以创建web服务器吗&#xff1f;Express能做什么安装Express监听GET请求和post请求获取URL中携带的查询参数获取URL中携带的动态参数托管静态资源nodemon为什么使用nodemon初始Express 什么是Express 官方给出的概念&#xff0…

Vue3 基础

Vue3 基础 概述 Vue (发音为 /vjuː/&#xff0c;类似 view) 是一款用于构建用户界面的 JavaScript 框架。它基于标准 HTML、CSS 和 JavaScript 构建&#xff0c;并提供了一套声明式的、组件化的编程模型&#xff0c;帮助你高效地开发用户界面。无论是简单还是复杂的界面&…

Java:Java与Python — 编码大战

Java和Python是目前市场上最热门的两种编程语言&#xff0c;因为它们具有通用性、高效性和自动化能力。两种语言都有各自的优点和缺点&#xff0c;但主要区别在于Java 是静态类型的&#xff0c;Python是动态类型的。它们有相似之处&#xff0c;因为它们都采用了“一切都是对象”…

单片机输入输出模式

单片机输入输出模式输入模式模拟输入、浮空输入、上拉输入、下拉输入GPIO输出模式推挽输出、开漏输出、复用推挽输出、复用开漏输出。上下拉电阻上拉电阻下拉电阻输入模式 模拟输入、浮空输入、上拉输入、下拉输入 模拟输入&#xff1a;I/O端口的模拟信号&#xff08;电压信号…

日志收集笔记(架构设计、Log4j2项目初始化、Lombok)

1 架构设计 ELK 技术栈架构设计图&#xff1a; 从左往右看&#xff0c; Beats&#xff1a;主要是使用 Filebeat&#xff0c;用于收集日志&#xff0c;将收集后的日志数据发送给 Kafka&#xff0c;充当 Kafka 的生产者Kafka&#xff1a;高性能消息队列&#xff0c;主要起缓冲…

关于客户背景调查的两个案例,说下我的真实看法

这篇文章我只是想客观陈述下事实&#xff0c;并没有对他人的贬低与对自己的吹捧之意。只是想通过这样两件小事&#xff0c;传递出来一个观点&#xff1a;在外贸业务开发过程中&#xff0c;很多时候正是那些我们内心抗拒&#xff0c;不愿意沉下心去做的事&#xff0c;才给了我们…

C#与三菱PLC MC协议通信,Java与三菱PLC MC协议通信

三菱PLC的MC协议是一种常用的通信协议&#xff0c;用于实现三菱PLC与其他设备之间的通信。以下是一些关于MC协议的基本信息&#xff1a;协议格式MC协议的通信数据格式如下&#xff1a;数据头网络编号PC编号目标模块IO编号目标模块站号本机模块IO编号本机模块站号请求数据长度请…

嵌套走马灯Carousel

Carousel 的应用很广泛&#xff0c;基础用法这里不多做阐述&#xff0c;感兴趣的可以去element-gui了解Carousel 组件。 今天主要是梳理嵌套走马灯的逻辑&#xff0c;背景如下&#xff1a; 需要对项目做一个展示&#xff0c;项目可能有一个或多个&#xff0c;同时一个项目可能…

初探 qiling ( 麒麟 ):开源的二进制分析、高级代码模拟框架

官方介绍&#xff1a; 官网&#xff1a;https://qiling.io/&#xff1a;https://twitter.com/qiling_iogithub 地址&#xff1a;https://github.com/qilingframework/qiling 1、qiling 简介 qiling 是什么 qiling 基于 python 开发&#xff0c;是一个开源的、可模拟多种架构…

Web前端:全栈开发人员的责任

多年来&#xff0c;关于全栈开发人员有很多说法&#xff0c;全栈开发人员是一位精通应用程序全栈开发过程的专业人士。这包括数据库、API、前端技术、后端开发语言和控制系统版本。你一定遇到过前端和后端开发人员。前端开发人员将构建接口&#xff0c;而后端开发人员将开发、更…

狂神说:方法

何为方法方法是语句和集合&#xff0c;一起执行一个功能【实际上方法就是函数&#xff0c;说法不一样而已】定义方法加了static才能被main方法调用修饰符&#xff08;public static&#xff09; 返回类型 方法名&#xff08;参数类型 参数名&#xff09;// main方法public stat…

vscode SSH 保存密码自动登录服务器

先在win local上拿到秘钥&#xff0c;然后再把这秘钥copy 进服务器 1. 创建 RSA 密钥对 第一步是在客户端机器&#xff08;通常是您的计算机 win 10&#xff09;上创建密钥对&#xff1a;打开powershell, 输入 ssh-keygen默认情况下ssh-keygen将创建一个 2048 位 RSA 密钥对…

“双碳”目标下二氧化碳地质封存技术应用前景及模型构建实践方法与讨论

我国二氧化碳地质封存技术起步较晚&#xff0c;目前仍没有一套相对完整的行业规范&#xff1b;且就该技术而言&#xff0c;涉及环节众多&#xff0c;理论相对复杂&#xff0c;对于行业的新入局者不太友好。因此&#xff0c;结合时代背景&#xff0c;我们首次尝试对二氧化碳地质…

nodejs出现require is not defined和__dirname is not define 错误

参阅此&#xff0c; Cesium环境搭建成功和初步看一下它的示例_bcbobo21cn的博客-CSDN博客 运行Cesium入门示例&#xff0c;出现下图错误&#xff0c;根据资料&#xff0c;这是node版本的问题&#xff1b; 解决方法是&#xff0c;在server.js头部加入&#xff0c; import { cre…

Flink04: Flink核心API之DataStream

一、Flink 4种不同层次的API Flink中提供了4种不同层次的API&#xff0c;每种API在简洁和易表达之间有自己的权衡&#xff0c;适用于不同的场景。目前上面3个会用得比较多。 • 低级API(Stateful Stream Processing)&#xff1a;提供了对时间和状态的细粒度控制&#x…

Endless lseek导致的SQL异常

最近碰到同事咨询的一个问题&#xff0c;在执行一个函数时&#xff0c;发现会一直卡在那里。 strace抓了下发现会话一直在执行lseek&#xff0c;大致情况如下&#xff1a; 16:13:55.451832 lseek(33, 0, SEEK_END) 1368064 <0.000037> 16:13:55.477216 lseek(33, 0, SE…

linux下安装mongoDB

一、下载mongoDB包 下载地址&#xff1a; https://www.mongodb.com/try/download/community 个人建议&#xff1a;如果是学习阶段&#xff0c;使用5以下版本更好些。 二、安装及配置 1、安装 # 1、解压 $ tar -zxvf mongodb-linux-x86_64-rhel70-4.4.19-rc1.tgz# 2、迁移目…