【数据结构】队列篇| 超清晰图解和详解:循环队列模拟、用栈实现队列、用队列实现栈
- 博主简介:努力学习的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的应用,为用户带来更智能、更个性化的直播体验。 …...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...

ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...
提升移动端网页调试效率:WebDebugX 与常见工具组合实践
在日常移动端开发中,网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时,开发者迫切需要一套高效、可靠且跨平台的调试方案。过去,我们或多或少使用过 Chrome DevTools、Remote Debug…...
面试高频问题
文章目录 🚀 消息队列核心技术揭秘:从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"?性能背后的秘密1.1 顺序写入与零拷贝:性能的双引擎1.2 分区并行:数据的"八车道高速公路"1.3 页缓存与批量处理…...
6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙
Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...