【数据结构】队列篇| 超清晰图解和详解:循环队列模拟、用栈实现队列、用队列实现栈
- 博主简介:努力学习的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的应用,为用户带来更智能、更个性化的直播体验。 …...

JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...

Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...

Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

Windows安装Miniconda
一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

Unity UGUI Button事件流程
场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

Linux操作系统共享Windows操作系统的文件
目录 一、共享文件 二、挂载 一、共享文件 点击虚拟机选项-设置 点击选项,设置文件夹共享为总是启用,点击添加,可添加需要共享的文件夹 查询是否共享成功 ls /mnt/hgfs 如果显示Download(这是我共享的文件夹)&…...

VSCode 使用CMake 构建 Qt 5 窗口程序
首先,目录结构如下图: 运行效果: cmake -B build cmake --build build 运行: windeployqt.exe F:\testQt5\build\Debug\app.exe main.cpp #include "mainwindow.h"#include <QAppli...
第14节 Node.js 全局对象
JavaScript 中有一个特殊的对象,称为全局对象(Global Object),它及其所有属性都可以在程序的任何地方访问,即全局变量。 在浏览器 JavaScript 中,通常 window 是全局对象, 而 Node.js 中的全局…...