7 月12日学习打卡--栈和队列的相互转换

hello大家好呀,本博客目的在于记录暑假学习打卡,后续会整理成一个专栏,主要打算在暑假学习完数据结构,因此会发一些相关的数据结构实现的博客和一些刷的题,个人学习使用,也希望大家多多支持,有不足之处也请指出,谢谢大家。

前言

为了更深入理解栈和队列,本篇博客我将介绍力扣上两道栈和队列的转化问题。

一,力扣225,用队列实现栈

. - 力扣(LeetCode)

我们知道栈的特点是先进后出,队列是先进先出,因此,我们需要两个队列才能实现一个栈,通过队列中元素的转移来获取我们想要删除的元素,下面逐一介绍各个方法

1:push

根据后面的pop()方法和我们需要实现栈的特性可知,我们每次需要在两个队列中非空的队列中插入元素(插入元素肯定是插在一个队列中),如果都为空,则指定一个队列插入

public void push(int x) {
        if (!q2.isEmpty()) {
            q2.offer(x);
        } else if (!q1.isEmpty()) {
            q1.offer(x);
        } else {
            q1.offer(x);
        }

2.empty

我们先看empty,因为后面方法需要用到,显然,两个队列均为空则模拟栈空

 public boolean empty() {
        return q1.isEmpty()&&q2.isEmpty();
    }

3.pop

pop方法我们的思路是如果哪个队列不空,则把队列中的size-1个元素移动到另一个队列,剩下的便是不需要的数(虽然看起来代码多但是else里的只需要把if里的改下就行)

public int pop() {
        if (empty()){
            return -1;
        }
        if(!q2.isEmpty()){
            int size=q2.size();
            for (int i = 0; i < size-1; i++) {
                q1.offer(q2.poll());
            }
            return q2.poll();
        }else {
            int size=q1.size();
            for (int i = 0; i < size-1; i++){
                q2.offer(q1.poll());
            }
            return q1.poll();
        }
    }

4.empty

与pop类似,只是我们不需要删除元素,而且需要一个整形纪录栈顶元素

public int top() {
        if (empty()){
            return -1;
        }

        if(!q2.isEmpty()){
            int size=q2.size();
            int val=0;
            for (int i = 0; i < size; i++) {
                val=q2.poll();
                q1.offer(val);
            }
            return val;
        }else {
            int size=q1.size();
            int val=0;
            for (int i = 0; i < size; i++) {
                val=q1.poll();
                q2.offer(val);
            }
            return val;
        }
    }

完整代码

class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;
    public MyStack() {
         q1=new LinkedList();
         q2=new LinkedList();

    }
    public void push(int x) {
        if (!q2.isEmpty()) {
            q2.offer(x);
        } else if (!q1.isEmpty()) {
            q1.offer(x);
        } else {
            q1.offer(x);
        }

    }
    public int pop() {
        if (empty()){
            return -1;
        }
        if(!q2.isEmpty()){
            int size=q2.size();
            for (int i = 0; i < size-1; i++) {
                q1.offer(q2.poll());
            }
            return q2.poll();
        }else {
            int size=q1.size();
            for (int i = 0; i < size-1; i++){
                q2.offer(q1.poll());
            }
            return q1.poll();
        }
    }

    public int top() {
        if (empty()){
            return -1;
        }

        if(!q2.isEmpty()){
            int size=q2.size();
            int val=0;
            for (int i = 0; i < size; i++) {
                val=q2.poll();
                q1.offer(val);
            }
            return val;
        }else {
            int size=q1.size();
            int val=0;
            for (int i = 0; i < size; i++) {
                val=q1.poll();
                q2.offer(val);
            }
            return val;
        }
    }

    public boolean empty() {
        return q1.isEmpty()&&q2.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

二,力扣232,用栈实现队列

. - 力扣(LeetCode)

思路:和上面类似,不过这里push方法都是放到第一个栈,出队操作分两步:

1.判断第二个栈是不是空的?如果是,则把第一个栈中所有元素都放到第二个栈里,取出第二个栈当中的栈顶元素。

2.如果不是空的,直接取出第二个栈中的栈顶元素

代码:

class MyQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;

    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

    public void push(int x) {
        s1.push(x);
    }

    public int pop() {
        if (empty())
            return -1;
        if (s2.isEmpty()) {
            int size = s1.size();
            for (int i = 0; i < size; i++) {
                s2.push(s1.pop());
            }
            return s2.pop();
        } else {
            return s2.pop();
        }

    }

    public int peek() {
        if (empty())
            return -1;
        if (s2.isEmpty()) {
            int size = s1.size();
            for (int i = 0; i < size; i++) {
                s2.push(s1.pop());
            }
            return s2.peek();
        } else {
            return s2.peek();
        }

    }

    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

好了,今天练车耽误了一下,今天就到这里吧,谢谢大家

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

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

相关文章

深度学习论文: YOLOv5, YOLOv8 and YOLOv10: The Go-To Detectors for Real-time Vision

深度学习论文: YOLOv5, YOLOv8 and YOLOv10: The Go-To Detectors for Real-time Vision YOLOv5, YOLOv8 and YOLOv10: The Go-To Detectors for Real-time Vision PDF:https://arxiv.org/pdf/2407.02988v1 PyTorch: https://github.com/shanglianlm0525/PyTorch-Networks 1 概…

通过maven基于springboot项目构建脚手架archetype

1、引入脚手架构建的插件依赖 <!--构建脚手架archetype--><plugin><groupId>org.apache.maven.plugins</groupId><artifactId>maven-archetype-plugin</artifactId><version>3.2.1</version></plugin><plugin><…

nodejs安装配置详解

一、下载Node.js安装包 官网下载链接[点击跳转] 建议下载LTS版本&#xff08;本教程不适用于苹果电脑&#xff09; 二 、安装Node.js 2.1 下载好安装包后双击打开安装包&#xff0c;然后点击Next 2.2 勾选同意许可后点击Next 2.3 点击Change选择好安装路径后点击Next&#x…

Mysql的语句执行很慢,如何分析排查?

1、检查服务器性能是否存在瓶颈 如果系统资源使用率比较高&#xff0c;比如CPU,硬盘&#xff0c;那访问肯定会慢&#xff0c;如果你发现是Mysl占比比较高&#xff0c;说明Mysql的读写频率高&#xff0c;如果本身网站访问量不大&#xff0c;说明你的sql参数&#xff0c;sql语句查…

羧基聚乙二醇生物素的制备方法;COOH-PEG-Biotin

羧基聚乙二醇生物素&#xff08;COOH-PEG-Biotin&#xff09;是一种常见的生物分子聚合物&#xff0c;具有多种应用&#xff0c;特别是在生物实验、药物研发和生物技术等领域。以下是对该化合物的详细解析&#xff1a; 一、基本信息 名称&#xff1a;羧基聚乙二醇生物素&#x…

Angular进阶之九: JS code coverage是如何运作的

环境准备 需要用到的包 node 18.16.0# Javascript 代码编辑"babel/core": "^7.24.7","babel/preset-env": "^7.24.7","babel-loader": "^9.1.3",# 打包时使用的 module&#xff0c; 给代码中注入新的方法# http…

云盘挂载 开机自动模拟 cmd- alist server

云盘挂载 开机自动模拟 cmd- alist server 打开Kimi智能助手, 网址:Kimi.ai - 帮你看更大的世界 (moonshot.cn) 问他: 帮我写一个vbs命令:在D:\sky目录下, 然后cmd, 进入命令行后, 输入 alist server 然后回车 这里 这个目录, 换成自己的 alist.exe所在目录 下面是我完善的示…

uni-app 保存号码到通讯录

1、 添加模块 2、添加权限 3、添加策略 Android&#xff1a; "permissionExternalStorage" : {"request" : "none","prompt" : "应用保存运行状态等信息&#xff0c;需要获取读写手机存储&#xff08;系统提示为访问设备上的照片…

pdf工具

iLovePDF | 为PDF爱好者提供的PDF文件在线处理工具 https://www.ilovepdf.com/zh-cn 图片 pdf 合并成一个pdf也可以拆分

C++ | Leetcode C++题解之第231题2的幂

题目&#xff1a; 题解&#xff1a; class Solution { private:static constexpr int BIG 1 << 30;public:bool isPowerOfTwo(int n) {return n > 0 && BIG % n 0;} };

西邮计科嵌入式复习

西邮嵌入式复习 一、第一章复习二、第二章复习三、第三章复习四、第四章复习 一、第一章复习 二、第二章复习 三、第三章复习 四、第四章复习

【零基础】学JS之APIS

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 非常期待和您一起在这个小…

使用Vsftpd服务传输文件

前言&#xff1a;本博客仅作记录学习使用&#xff0c;部分图片出自网络&#xff0c;如有侵犯您的权益&#xff0c;请联系删除 目录 一、文件传输协议 二、Vsftpd服务程序 三、TFTP简单文件传输协议 致谢 一、文件传输协议 FTP&#xff08;File Transfer Protocol&#xf…

vue3使用Echarts图表生成项目进度甘特图

先看效果 代码展示 <template><h1>项目进度甘特图</h1><div id"app"><!-- Echarts 图表 --><div ref"progressChart" class"progressChart"></div></div> </template><script setup&…

PMP是什么?PMP证书在国作用大吗?

PMP是全球认可的项目管理专业人士的通用语言&#xff0c;已在200多个国家得到认可。 1999年&#xff0c;中国国际人才交流基金会引入了项目管理知识体系指南和PMP职业资格认证。这一举措不仅推动了中国项目管理实践与国际接轨&#xff0c;也促进了项目管理培训和教育的发展&am…

Vue3 使用 Vue Router 时,prams 传参失效和报错问题

Discarded invalid param(s) “id“, “name“, “age“ when navigating 我尝试使用 prams 传递数据 <script setup> import { useRouter } from vue-routerconst router useRouter() const params { id: 1, name: ly, phone: 13246566476, age: 23 } const toDetail…

Golang:数据科学领域中的高性能并发编程新星

文章目录 📖 介绍 📖🏡 演示环境 🏡📒 文章内容 📒📝 并发性能的卓越表现📝 系统级工具的便捷性📝 语言设计的简洁性📝 强类型系统的严格性📝 版本兼容性的稳定性📝 内置工具的全面性⚓️ 相关链接 ⚓️📖 介绍 📖 在数据科学和机器学习的广阔天地…

.Net Core 微服务之Consul(二)-集群搭建

引言: 集合上一期.Net Core 微服务之Consul(一)(.Net Core 微服务之Consul(一)-CSDN博客) 。 目录 一、 Consul集群搭建 1. 高可用 1.1 高可用性概念 1.2 高可用集群的基本原理 1.3 高可用集群的架构设计 1.3.1 主从复制架构 1.3.2 共享存储架构 1.3.3 负载均衡…

[每周一更]-(第105期):SSL证书过期后引发的DNS缓存问题

问题回顾&#xff1a; ​ 上班路上收到ZeroSSL邮件通知我们清点项目的SSL证书到期了&#xff0c;到公司还是登录网址查看信息&#xff0c;一看果然是7.10也就是今天到期&#xff0c;开始看下acme.sh的定制任务为何没生效&#xff0c;一看crontab脚本&#xff0c;日志任务丢垃圾…

【吊打面试官系列-ZooKeeper面试题】简述 Zookeeper 文件系统?

大家好&#xff0c;我是锋哥。今天分享关于 【简述 Zookeeper 文件系统?】面试题&#xff0c;希望对大家有帮助&#xff1b; 简述 Zookeeper 文件系统? Zookeeper 提供一个多层级的节点命名空间&#xff08;节点称为 znode&#xff09;。与文件系统不同的是&#xff0c;这些节…