当前位置: 首页 > news >正文

【数据结构】队列篇| 超清晰图解和详解:循环队列模拟、用栈实现队列、用队列实现栈

在这里插入图片描述

  • 博主简介:努力学习的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中的元素顺次移入,此时再把queue1queue2互换即可(脱裤子放屁的感觉,和方法一基本上是一样的)
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语言核心编程

  • 算法

相关文章:

【数据结构】队列篇| 超清晰图解和详解:循环队列模拟、用栈实现队列、用队列实现栈

博主简介&#xff1a;努力学习的22级计算机科学与技术本科生一枚&#x1f338;博主主页&#xff1a; 是瑶瑶子啦每日一言&#x1f33c;: 每一个不曾起舞的日子&#xff0c;都是对生命的辜负。——尼采 目录 一、 模拟实现循环队列二、用栈实现队列⭐三、225. 用队列实现栈 一、…...

js+html实现打字游戏v2

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

Python之作业(一)

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

uni-app 之 v-on:click点击事件

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

迁移学习:实现快速训练和泛化的新方法

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

蓝队追踪者工具TrackAttacker,以及免杀马生成工具

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

ELK日志收集系统(四十九)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 前言 一、概述 二、组件 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多线程&#xff08;四&#xff09; 文章目录 Linux知识点 -- Linux多线程&#xff08;四&#xff09;一、线程池1.概念2.实现3.单例模式的线程池 二、STL、智能指针和线程安全1.STL的容器是否是线程安全的2.智能指针是否是线程安全的 三、其他常见的各种锁…...

Java设计模式:四、行为型模式-07:状态模式

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

很多应用都是nginx+apache+tomcat

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

原型模式:复制对象的技巧

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

ClickHouse进阶(五):副本与分片-1-副本与分片

进入正文前&#xff0c;感谢宝子们订阅专题、点赞、评论、收藏&#xff01;关注IT贫道&#xff0c;获取高质量博客内容&#xff01; &#x1f3e1;个人主页&#xff1a;含各种IT体系技术,IT贫道_Apache Doris,大数据OLAP体系技术栈,Kerberos安全认证-CSDN博客 &#x1f4cc;订阅…...

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&#xff1f; 答&#xff1a;所谓 CEP&#xff0c;其实就是“复杂事件处理&#xff08;Complex Event Processing&#xff09;”的缩写&#xff1b;而 Flink CEP&#xff0c;就是 Flink 实现的一个用于复杂事件处理的库&#xff08…...

谷歌IndexedDB客户端存储数据

IndexedDB 具有以下主要特点&#xff1a; 1.存储大量数据&#xff1a;IndexedDB 可以存储大量的数据&#xff0c;比如存储离线应用程序的本地缓存或存储在线应用程序的大量数据。 2.结构化数据&#xff1a;IndexedDB 使用对象存储空间&#xff08;Object Stores&#xff09;来…...

天气数据的宝库:解锁天气预报API的无限可能性

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

插入排序(Insertion Sort)

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

2023蓝帽杯初赛

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

风险评估

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

直播软件app开发中的AI应用及前景展望

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

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

【Veristand】Veristand环境安装教程-Linux RT / Windows

首先声明&#xff0c;此教程是针对Simulink编译模型并导入Veristand中编写的&#xff0c;同时需要注意的是老用户编译可能用的是Veristand Model Framework&#xff0c;那个是历史版本&#xff0c;且NI不会再维护&#xff0c;新版本编译支持为VeriStand Model Generation Suppo…...

【若依】框架项目部署笔记

参考【SpringBoot】【Vue】项目部署_no main manifest attribute, in springboot-0.0.1-sn-CSDN博客 多一个redis安装 准备工作&#xff1a; 压缩包下载&#xff1a;http://download.redis.io/releases 1. 上传压缩包&#xff0c;并进入压缩包所在目录&#xff0c;解压到目标…...

从实验室到产业:IndexTTS 在六大核心场景的落地实践

一、内容创作&#xff1a;重构数字内容生产范式 在短视频创作领域&#xff0c;IndexTTS 的语音克隆技术彻底改变了配音流程。B 站 UP 主通过 5 秒参考音频即可克隆出郭老师音色&#xff0c;生成的 “各位吴彦祖们大家好” 语音相似度达 97%&#xff0c;单条视频播放量突破百万…...

GAN模式奔溃的探讨论文综述(一)

简介 简介:今天带来一篇关于GAN的,对于模式奔溃的一个探讨的一个问题,帮助大家更好的解决训练中遇到的一个难题。 论文题目:An in-depth review and analysis of mode collapse in GAN 期刊:Machine Learning 链接:...