【数据结构】队列篇| 超清晰图解和详解:循环队列模拟、用栈实现队列、用队列实现栈
- 博主简介:努力学习的22级计算机科学与技术本科生一枚🌸
- 博主主页: @是瑶瑶子啦
- 每日一言🌼: 每一个不曾起舞的日子,都是对生命的辜负。——尼采
目录
- 一、 模拟实现循环队列
- 二、用栈实现队列⭐
- 三、225. 用队列实现栈
一、 模拟实现循环队列
🔗622. 设计循环队列
- 👧🏻思路:
- 🍊数据结构:使用数组为数据结构,且采用牺牲一个空间的方法来包装判空和判满的不同。
- 判空:
Q.rear == Q.front
- 判满:
Q.rear.next == Q.front
/(rear+1)%size == front
(满的时候可以看上图,此时rear指向的空间浪费掉了)
- 判空:
⭐这里就要注意,因为是浪费一个空间来判满的,所以比如我们需要一个容量为
k
的循环队列,那么实际的物理容量应该设计为k+1
个!!!(这题在下面代码有体现,否则只能存k-1个)!
-
🍊头尾指针含义(重点)
font
:指向队头元素rear
:下一个待插入元素的位置
-
🦆
-
🙇🏻♀️代码:
class MyCircularQueue {int[] myCircularQueue;int front = 0;int rear = 0;int size = 0;//构造函数,创建一个循环队列public MyCircularQueue(int k) {this.size = k+1;//!注意,这里需要+1this.myCircularQueue = new int[size];}//入队操作public boolean enQueue(int value) {if (isFull()){return false;}myCircularQueue[rear] = value;rear = (rear+1)%size;return true;}//出队操作public boolean deQueue() {if(isEmpty()){return false;}front = (front + 1)%size;return true;}//读取队头元素(注意判空)public int Front() {if(isEmpty()){return -1;}return myCircularQueue[front];}//读取队尾元素(注意判空)public int Rear() {if(isEmpty()){return -1;}return myCircularQueue[(rear - 1 + size) % size ];}//判空public boolean isEmpty() {if(front == rear){return true;}return false;}//判满public boolean isFull() {if((rear+1)%size == front){return true;}return false;}
}/*** Your MyCircularQueue object will be instantiated and called as such:* MyCircularQueue obj = new MyCircularQueue(k);* boolean param_1 = obj.enQueue(value);* boolean param_2 = obj.deQueue();* int param_3 = obj.Front();* int param_4 = obj.Rear();* boolean param_5 = obj.isEmpty();* boolean param_6 = obj.isFull();*/
二、用栈实现队列⭐
🔗232. 用栈实现队列
- 👧🏻思路:
- 若只有一个栈
stack1
,是不可能实现队列的,它可以实现在“队尾”入队,但不能实现拿到队头元素
- 于是我们需要一个辅助的中转栈
stack2
, 把stack1的元素依次放入,再通过stack2.peek
,间接取得队头元素
此时两个栈一起便实现了队列。(注意,当stack2为空时,及时把stack1的元素挪过去!)
- 若只有一个栈
- 🙇🏻♀️代码:
class MyQueue {Stack<Integer> stack1;Stack<Integer> stack2 ;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}/** 添加元素到队尾 */public void push(int x) {stack1.push(x);}/** 将stack1的元素挪到stack2 */public void stack1ToStack2(){while(!stack1.empty()){stack2.push(stack1.pop());}}/** 删除队头的元素并返回 */public int pop() {if(stack2.empty()){stack1ToStack2();}return stack2.pop();}/** 返回队头元素 */public int peek() {if(stack2.empty()){stack1ToStack2();}return stack2.peek();}/** 判断队列是否为空 */public boolean empty() {return stack1.empty() && stack2.empty();}
}/*** 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();*/
三、225. 用队列实现栈
🔗225. 用队列实现栈
- 👧🏻思路:
- 一个队列实现栈的问题在于:可以像栈一样正常入栈,但是队列的话只能拿到栈底元素,无法拿到栈顶(队尾)元素。
- 为了解决这个问题,关键是,如何在正常入栈操作的基础上,让新添加元素(即栈顶元素处于队头位置,这才可以始得每次出队列(出栈)拿到的是最新添加的栈顶元素。
- 方法1:单个队列实现
即每次加入新元素后,把新元素前面的元素顺次弹出,排到该元素后面,即可让新元素成为队头元素,即栈顶元素。这样就保证队头元素为栈顶元素。
- 🙇🏻♀️代码:
class MyStack {Queue<Integer> queue;public MyStack() {queue = new LinkedList<>();}public void push(int x) {//先直接添加queue.offer(x);//将新元素(栈顶元素)前的所有元素顺次移到栈顶元素之后for (int i = 0; i < queue.size() - 1; i++){queue.offer(queue.poll());}}public int pop() {return queue.poll();}public int top() {return queue.peek();}public boolean empty() {return queue.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();*/
- 方法2:双队列实现
本质和单队列是一样的,实现栈的队列是queue1
,只不过在添加新元素之前,把新元素放在空的辅助队列queue2
中——使之处于队头(栈顶),然后将queue1
中的元素顺次移入,此时再把queue1
和queue2
互换即可(脱裤子放屁的感觉,和方法一基本上是一样的)
class MyStack {Queue<Integer> queue1;Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<Integer>();queue2 = new LinkedList<Integer>();}public void push(int x) {queue2.offer(x);while (!queue1.isEmpty()) {queue2.offer(queue1.poll());}Queue<Integer> temp = queue1;queue1 = queue2;queue2 = temp;}public int pop() {return queue1.poll();}public int top() {return queue1.peek();}public boolean empty() {return queue1.isEmpty();}
}
💐若有疑问的地方,欢迎随时在评论区or私信找瑶瑶子交流讨论🌺
-
Java岛冒险记【从小白到大佬之路】
-
LeetCode每日一题–进击大厂
-
Go语言核心编程
-
算法
相关文章:

【数据结构】队列篇| 超清晰图解和详解:循环队列模拟、用栈实现队列、用队列实现栈
博主简介:努力学习的22级计算机科学与技术本科生一枚🌸博主主页: 是瑶瑶子啦每日一言🌼: 每一个不曾起舞的日子,都是对生命的辜负。——尼采 目录 一、 模拟实现循环队列二、用栈实现队列⭐三、225. 用队列实现栈 一、…...

js+html实现打字游戏v2
实现逻辑,看jshtml实现打字游戏v1,在此基础之上增加了从文件读取到的单词,随机选取10个单词。 效果演示 上代码: <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8">&l…...

Python之作业(一)
Python之作业(一) 作业 打印九九乘法表 用户登录验证 用户依次输入用户名和密码,然后提交验证用户不存在、密码错误,都显示用户名或密码错误提示错误3次,则退出程序验证成功则显示登录信息 九九乘法表 代码分析 先…...

uni-app 之 v-on:click点击事件
uni-app 之 v-on:click点击事件 image.png <template><!-- vue2的<template>里必须要有一个盒子,不能有两个,这里的盒子就是 view--><view>--- v-on:click点击事件 ---<view v-on:click"onclick">{{title}}<…...

迁移学习:实现快速训练和泛化的新方法
文章目录 迁移学习的原理迁移学习的应用快速训练泛化能力提升 迁移学习的代码示例拓展应用与挑战结论 🎉欢迎来到AIGC人工智能专栏~迁移学习:实现快速训练和泛化的新方法 ☆* o(≧▽≦)o *☆嗨~我是IT陈寒🍹✨博客主页:IT陈寒的博…...

蓝队追踪者工具TrackAttacker,以及免杀马生成工具
蓝队追踪者工具TrackAttacker,以及免杀马生成工具。 做过防守的都知道大HW时的攻击IP量,那么对于这些攻击IP若一个个去溯源则显得效率低下,如果有个工具可以对这些IP做批量初筛是不是更好? 0x2 TrackAttacker获取 https://githu…...

ELK日志收集系统(四十九)
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 目录 前言 一、概述 二、组件 1. elasticsearch 2. logstash 2.1 工作过程 2.2 INPUT 2.3 FILETER 2.4 OUTPUTS 3. kibana 三、架构类型 3.1 ELK 3.2 ELKK 3.3 ELFK 3.5 EF…...

Linux知识点 -- Linux多线程(四)
Linux知识点 – Linux多线程(四) 文章目录 Linux知识点 -- Linux多线程(四)一、线程池1.概念2.实现3.单例模式的线程池 二、STL、智能指针和线程安全1.STL的容器是否是线程安全的2.智能指针是否是线程安全的 三、其他常见的各种锁…...

Java设计模式:四、行为型模式-07:状态模式
文章目录 一、定义:状态模式二、模拟场景:状态模式2.1 状态模式2.2 引入依赖2.3 工程结构2.4 模拟审核状态流转2.4.1 活动状态枚举2.4.2 活动信息类2.4.3 活动服务接口2.4.4 返回结果类 三、违背方案:状态模式3.0 引入依赖3.1 工程结构3.2 活…...

很多应用都是nginx+apache+tomcat
nginx 负责负载均衡,将大量的访问量平衡分配给多个服务器 apache 是用来处理静态html、图片等资源,在对HTML解析、响应等方面比tomcat效率更高。 tomcat 处理JSP等内容,进行后台业务操作。 upstream bbb.com.cn{ server 192.168.10.1:80 ;…...

原型模式:复制对象的技巧
欢迎来到设计模式系列的第六篇文章!在前面的几篇文章中,我们已经学习了一些常见的设计模式,今天我们将继续探讨另一个重要的设计模式——原型模式。 原型模式简介 原型模式是一种创建型设计模式,它主要用于复制对象。原型模式通…...

ClickHouse进阶(五):副本与分片-1-副本与分片
进入正文前,感谢宝子们订阅专题、点赞、评论、收藏!关注IT贫道,获取高质量博客内容! 🏡个人主页:含各种IT体系技术,IT贫道_Apache Doris,大数据OLAP体系技术栈,Kerberos安全认证-CSDN博客 📌订阅…...

Android 华为手机荣耀8X调用系统裁剪工具不能裁剪方形图片,裁剪后程序就奔溃,裁剪后获取不到bitmap的问题
买了个华为荣耀8X,安装自己写的App后,调用系统裁剪工具发现裁剪是圆形的,解决办法: //专门针对华为手机解决华为手机裁剪图片是圆形图片的问题 if (Build.MANUFACTURER.equals("HUAWEI")) {intent.putExtra("aspectX", 9998);intent.putExtra("a…...

《Flink学习笔记》——第十二章 Flink CEP
12.1 基本概念 12.1.1 CEP是什么 1.什么是CEP? 答:所谓 CEP,其实就是“复杂事件处理(Complex Event Processing)”的缩写;而 Flink CEP,就是 Flink 实现的一个用于复杂事件处理的库(…...

谷歌IndexedDB客户端存储数据
IndexedDB 具有以下主要特点: 1.存储大量数据:IndexedDB 可以存储大量的数据,比如存储离线应用程序的本地缓存或存储在线应用程序的大量数据。 2.结构化数据:IndexedDB 使用对象存储空间(Object Stores)来…...

天气数据的宝库:解锁天气预报API的无限可能性
前言 天气预报一直是我们日常生活中的重要组成部分。我们依赖天气预报来决定穿什么衣服、何时出行、规划户外活动以及做出关于农业、交通和能源管理等方面的重要决策。然而,要提供准确的天气预报,需要庞大的数据集和复杂的计算模型。这就是天气预报API的…...

插入排序(Insertion Sort)
C自学精简教程 目录(必读) 插入排序 每次选择未排序子数组中的第一个元素,从后往前,插入放到已排序子数组中,保持子数组有序。 打扑克牌,起牌。 输入数据 42 20 17 13 28 14 23 15 执行过程 完整代码 #include <iostream…...

2023蓝帽杯初赛
最近打完蓝帽杯 现在进行复盘 re 签到题 直接查看源代码 输出的内容就是 变量s 变量 number 而这都是已经设定好了的 所以flag就出来了 WhatisYourStory34982733 取证 案件介绍 取证案情介绍: 2021年5月,公安机关侦破了一起投资理财诈骗类案件&a…...

风险评估
风险评估概念 风险评估是一种系统性的方法,用于识别、评估和量化潜在的风险和威胁,以便组织或个人能够采取适当的措施来管理和减轻这些风险。 风险评估的目的 风险评估要素关系 技术评估和管理评估 风险评估分析原理 风险评估服务 风险评估实施流程...

直播软件app开发中的AI应用及前景展望
在当今数字化时代,直播市场蓬勃发展,而直播软件App成为人们获取实时信息和娱乐的重要渠道。随着人工智能(AI)技术的迅猛发展,直播软件App开发正逐渐融入AI的应用,为用户带来更智能、更个性化的直播体验。 …...

vscode html使用less和快速获取标签less结构
扩展插件里面搜索 css tree 插件 下载 使用方法 选择你要生成的标签结构然后按CTRLshiftp 第一次需要在输入框输入 get 然后选择 Generate CSS tree less结构就出现在这个里面直接复制到自己的less文件里面就可以使用了 在html里面使用less 下载 Easy LESS 插件 自己创建…...

excel中的引用与查找函数篇1
1、COLUMN(reference):返回与列号对应的数字 2、ROW(reference):返回与行号对应的数字 参数reference表示引用/参考单元格,输入后引用单元格后colimn()和row()会返回这个单元格对应的列号和行号。若参数reference没有引用单元格,…...

【python】—— 函数详解
前言: 本期,我们将要讲解的是有关python中函数的相关知识!!! 目录 (一)函数是什么 (二)语法格式 (三)函数参数 (四)函…...

springboot web开发登录拦截器
在SpringBoot中我们可以使用HandlerInterceptorAdapter这个适配器来实现自己的拦截器。这样就可以拦截所有的请求并做相应的处理。 应用场景 日志记录,可以记录请求信息的日志,以便进行信息监控、信息统计等。权限检查:如登陆检测ÿ…...

大数据课程K17——Spark的协同过滤法
文章作者邮箱:yugongshiye@sina.cn 地址:广东惠州 ▲ 本章节目的 ⚪ 了解Spark的协同过滤概念; 一、协同过滤概念 1. 概念 协同过滤是一种借助众包智慧的途径。它利用大量已有的用户偏好来估计用户对其未接触过的物品的喜好程度。其内在思想是相似度的定义…...

【力扣】1588. 所有奇数长度子数组的和 <前缀和>
【力扣】1588. 所有奇数长度子数组的和 给你一个正整数数组 arr ,请你计算所有可能的奇数长度子数组的和。子数组 定义为原数组中的一个连续子序列。请你返回 arr 中 所有奇数长度子数组的和 。 示例 1: 输入:arr [1,4,2,5,3] 输出&#x…...

socket,tcp,http三者之间的原理和区别
目录 1、TCP/IP连接 2、HTTP连接 3、SOCKET原理 4、SOCKET连接与TCP/IP连接 5、Socket连接与HTTP连接 socket,tcp,http三者之间的区别和原理 http、TCP/IP协议与socket之间的区别 下面的图表试图显示不同的TCP/IP和其他的协议在最初OSI模型中的位置…...

【FPGA零基础学习之旅#11】数码管动态扫描
🎉欢迎来到FPGA专栏~数码管动态扫描 ☆* o(≧▽≦)o *☆嗨~我是小夏与酒🍹 ✨博客主页:小夏与酒的博客 🎈该系列文章专栏:FPGA学习之旅 文章作者技术和水平有限,如果文中出现错误,希望大家能指正…...

JavaExcel:自动生成数据表并插入数据
故事背景 出于好奇,当下扫描excel读取数据进数据库 or 导出数据库数据组成excel的功能层出不穷,代码也是前篇一律,poi或者easy excel两种SDK的二次利用带来了各种封装方法。 那么为何不能直接扫描excel后根据列的属性名与行数据的属性建立S…...

哪吒汽车“三头六臂”之「浩智电驱」
撰文 / 翟悦 编审 / 吴晰 8月21日,在哪吒汽车科技日上,哪吒汽车发布“浩智战略2025”以及浩智技术品牌2.0。根据公开信息,主编梳理了以下几点:◎浩智滑板底盘支持400V/800V双平台◎浩智电驱包括180kW 400V电驱系统和250kW 800…...