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

队列(循环数组队列,用队列实现栈,用栈实现队列)

基础知识

队列(Queue):先进先出的数据结果,底层由双向链表实现

入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为对头

常用方法

boolean offer(E e)  入队

E(弹出元素的类型) poll() 出队

peek() 获取队头

int size 获取队列元素个数

boolean isEmpty() 判定队列是否为空

设计循环队列

链接:https://leetcode.cn/problems/design-circular-queue/description/ 

思路:创建一个数组,useSize记录这个数组有效元素个数,rear记录这个数组(队列)下一个要插入的位置,front记录这个队列的对头,也就是要删除元素的位置.

插入元素:如果这个数组已经满了(useSize等于数组的长度),则插入失败返回false,没满就是往rear指向的位置放入一个元素,然后rear++,useSize++,值得注意的是这是一个循环队列,当rear指向的是数组的最后一个下标也就是(array.length-1),此时再如果让rear++,它就指向了array.length.数组是越界的,我们可以给一个判断条件,如果rear等于array.length,就让它重新等于0

删除元素:如果这个队列是空,则删除失败,不为空,就让front++,useSize--,这样就可以删除了,同理front也可能指向array.lenth,让他重新指向0就好了

获取队头元素:当队列为空获取失败,不为空就返回front下标指向的元素

获取队尾元素:当队列为空获取失败,不为空,因为rear指向的是下一个要插入的元素的位置,所以我们返回rear-1下标的元素就是当前的队尾元素,注意的是,当rear指向的是0时,也不为空说明它刚刚循环过来的,此时队尾元素就是数组最后的下标元素,返回即可

是否为空:useSize为0就为空,是否为满:useSize等于数组长度队列就满了

代码

class MyCircularQueue {private int[] array;private int front;private int rear;private int useSize;private int size;public MyCircularQueue(int k) {array = new int[k];size = k;}public boolean enQueue(int value) {if(isFull()){return false;}array[rear] = value;rear++;if(rear==size){rear=0;}useSize++;return true;}public boolean deQueue() {if(isEmpty()){return false;}front++;if(front==size){front=0;}useSize--;return true;}public int Front() {if(isEmpty()){return -1;}return array[front];}public int Rear() {if(isEmpty()){return -1;}if(rear-1<0){return array[size-1];}return array[rear-1];}public boolean isEmpty() {return useSize==0;}public boolean isFull() {return useSize==size;}
}

用队列实现栈

链接:https://leetcode.cn/problems/implement-stack-using-queues/

思路
创建俩个队列,qu1 和 qu2
入栈,如果qu1和qu2都为空(第一次入栈),就放入到qu1队列中,否则就入到不为空的队列中
出栈:找到不为空的队列,把useSize-1个元素移动到另一个队列当中去,如果俩个队列都为空,则出栈失败
查看栈顶元素:如果俩个队列都为空,查看失败,找到不为空的队列,把useSIze个元素移动到另一个队列中,每次入队列都用一个值来接收,这样入队列完成后,这个值就是栈顶元素,把它返回即可

class MyStack {private Queue<Integer> qu1;private Queue<Integer> qu2;public MyStack() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}public void push(int x) {if(!qu1.isEmpty()){qu1.offer(x);}else if(!qu2.isEmpty()){qu2.offer(x);}else{qu1.offer(x);}}public int pop() {if(empty()){return -1;}if(!qu1.isEmpty()){int size = qu1.size();for(int i = 0;i<size-1;i++){int x = qu1.poll();qu2.offer(x);}return qu1.poll();}else{int size = qu2.size();for(int i = 0;i<size-1;i++){int x = qu2.poll();qu1.offer(x);}return qu2.poll();}}public int top() {if(empty()){return -1;}if(!qu1.isEmpty()){int size = qu1.size();int x = -1;for(int i = 0;i<size;i++){x = qu1.poll();qu2.offer(x);}return x;}else{int size = qu2.size();int x = -1;for(int i = 0;i<size;i++){x = qu2.poll();qu1.offer(x);}return x;}}public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}

用栈实现队列

链接:https://leetcode.cn/problems/implement-queue-using-stacks/


思路:
创建俩个栈,
入队:直接放到第一个栈中,
出队:出第二个队列中的数据,如果第二个队列中没有,就把第一个栈中的所有元素弹入到第二个栈中,
(第二个栈的顺序就是队列的顺序) 

代码

class MyQueue {private Stack<Integer> qu1;private Stack<Integer> qu2;public MyQueue() {qu1 = new Stack();qu2 = new Stack();}public void push(int x) {qu1.push(x);}public int pop() {if(empty()){return -1;}if(qu2.isEmpty()){int size = qu1.size();while(size != 0){int x = qu1.pop();qu2.push(x);size--;}}return qu2.pop();}public int peek() {if(empty()){return -1;}if(qu2.isEmpty()){int size = qu1.size();while(size != 0){int x = qu1.pop();qu2.push(x);size--;}}return qu2.peek();}public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}

相关文章:

队列(循环数组队列,用队列实现栈,用栈实现队列)

基础知识 队列(Queue):先进先出的数据结果,底层由双向链表实现 入队列:进行插入操作的一端称为队尾出队列:进行删除操作的一端称为对头 常用方法 boolean offer(E e) 入队 E(弹出元素的类型) poll() 出队 peek() 获取队头 int size 获取队列元素个数 boolean isEmpty(…...

卷积神经网络-池化层和激活层

2.池化层 根据特征图上的局部统计信息进行下采样&#xff0c;在保留有用信息的同时减少特征图的大小。和卷积层不同的是&#xff0c;池化层不包含需要学习的参数。最大池化(max-pooling)在一个局部区域选最大值作为输出&#xff0c;而平均池化(average pooling)计算一个局部区…...

API基础————包

什么是包&#xff0c;package实际上就是一个文件夹&#xff0c;便于程序员更好的管理维护自己的代码。它可以使得一个项目结构更加清晰明了。 Java也有20年历史了&#xff0c;这么多年有这么多程序员写了无数行代码&#xff0c;其中有大量重复的&#xff0c;为了更加便捷省时地…...

【C++】一文带你走入vector

文章目录 一、vector的介绍二、vector的常用接口说明2.1 vector的使用2.2 vector iterator的使用2.3 vector空间增长问题2.4 vector 增删查改 三、总结 ヾ(๑╹◡╹)&#xff89;" 人总要为过去的懒惰而付出代价ヾ(๑╹◡╹)&#xff89;" 一、vector的介绍 vector…...

《Secure Analytics-Federated Learning and Secure Aggregation》论文阅读

背景 机器学习模型对数据的分析具有很大的优势&#xff0c;很多敏感数据分布在用户各自的终端。若大规模收集用户的敏感数据具有泄露的风险。 对于安全分析的一般背景就是认为有n方有敏感数据&#xff0c;并且不愿意分享他们的数据&#xff0c;但可以分享聚合计算后的结果。 联…...

十三、Django之添加用户(原始方法实现)

修改urls.py path("user/add/", views.user_add),添加user_add.html {% extends layout.html %} {% block content %}<div class"container"><div class"panel panel-default"><div class"panel-heading"><h3 c…...

Elasticsearch数据操作原理

Elasticsearch 是一个开源的、基于 Lucene 的分布式搜索和分析引擎&#xff0c;设计用于云计算环境中&#xff0c;能够实现实时的、可扩展的搜索、分析和探索全文和结构化数据。它具有高度的可扩展性&#xff0c;可以在短时间内搜索和分析大量数据。 Elasticsearch 不仅仅是一个…...

gitgitHub

在git中复制CtrlInsert、粘贴CtrlShif 一、用户名和邮箱的配置 查看用户名 &#xff1a;git config user.name 查看密码&#xff1a; git config user.password 查看邮箱&#xff1a;git config user.email 查看配置信息&#xff1a; $ git config --list 修改用户名 git co…...

十天学完基础数据结构-第九天(堆(Heap))

堆的基本概念 堆是一种特殊的树形数据结构&#xff0c;通常用于实现优先级队列。堆具有以下两个主要特点&#xff1a; 父节点的值始终大于或等于其子节点的值&#xff08;最大堆&#xff09;&#xff0c;或者父节点的值始终小于或等于其子节点的值&#xff08;最小堆&#xff…...

vertx的学习总结7之用kotlin 与vertx搞一个简单的http

这里我就简单的聊几句&#xff0c;如何用vertx web来搞一个web项目的 1、首先先引入几个依赖&#xff0c;这里我就用maven了&#xff0c;这个是kotlinvertx web <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apac…...

golang学习笔记(二):链路追踪

自定义http连接的服务端 package serverimport ("github.com/gin-gonic/gin""go.opentelemetry.io/contrib/instrumentation/github.com/gin-gonic/gin/otelgin""net/http" )type MyServer struct {Server *http.Server }func GetServer() *MyS…...

git提交代码实际操作

1.仓库的代码 2.克隆代码下存在的分支 git clobe https://gitee.com/sadsadasad/big-event-11.git 3.查看当下存在的分支 git branch -a 在很多情况下,我们是要围绕着dev分支进行开发,所以我们可以在开发之前问明白围绕那个分支进行开发。 4.直接拉去dev分支代码 5.如果没在…...

TF坐标变换

ROS小乌龟跟随 5.1 TF坐标变换 Autolabor-ROS机器人入门课程《ROS理论与实践》零基础教程 tf模块&#xff1a;在 ROS 中用于实现不同坐标系之间的点或向量的转换。 在ROS中坐标变换最初对应的是tf&#xff0c;不过在 hydro 版本开始, tf 被弃用&#xff0c;迁移到 tf2,后者更…...

如何进行网络编程和套接字操作?

网络编程是计算机编程中重要的领域之一&#xff0c;它使程序能够在网络上进行数据传输和通信。C语言是一种强大的编程语言&#xff0c;也可以用于网络编程。网络编程通常涉及套接字&#xff08;Socket&#xff09;操作&#xff0c;套接字是一种用于网络通信的抽象接口。本文将详…...

在Spark中集成和使用Hudi

本文介绍了在Spark中集成和使用Hudi的功能。使用Spark数据源API(scala和python)和Spark SQL,插入、更新、删除和查询Hudi表的代码片段。 1.安装 Hudi适用于Spark-2.4.3+和Spark 3.x版本。 1.1 Spark 3支持矩阵 Hudi...

力扣第226翻转二叉数 c++三种方法 +注释

题目 226. 翻转二叉树 简单 给你一棵二叉树的根节点 root &#xff0c;翻转这棵二叉树&#xff0c;并返回其根节点。 示例 1&#xff1a; 输入&#xff1a;root [4,2,7,1,3,6,9] 输出&#xff1a;[4,7,2,9,6,3,1]示例 2&#xff1a; 输入&#xff1a;root [2,1,3] 输出&am…...

React项目部署 - Nginx配置

写在前面&#xff1a;博主是一只经过实战开发历练后投身培训事业的“小山猪”&#xff0c;昵称取自动画片《狮子王》中的“彭彭”&#xff0c;总是以乐观、积极的心态对待周边的事物。本人的技术路线从Java全栈工程师一路奔向大数据开发、数据挖掘领域&#xff0c;如今终有小成…...

【Vue3】定义全局变量和全局函数

// main.ts import { createApp } from vue import App from ./App.vue const app createApp(App)// 解决 ts 报错 type Filter {format<T>(str: T): string } declare module vue {export interface ComponentCustomProperties {$filters: Filter,$myArgs: string} }a…...

【Pandas】Apply自定义行数

文章目录 1. Series的apply方法2. DataFrame的apply方法2.1 针对列使用apply2.2 针对行使用apply Pandas提供了很多数据处理的API,但当提供的API不能满足需求的时候,需要自己编写数据处理函数, 这个时候可以使用apply函数apply函数可以接收一个自定义函数, 可以将DataFrame的行…...

C#,数值计算——完全VEGAS编码的蒙特·卡洛计算方法与源程序

1 文本格式 using System; namespace Legalsoft.Truffer { /// <summary> /// Complete VEGAS Code /// adaptive/recursive Monte Carlo /// </summary> public abstract class VEGAS { const int NDMX 50; const int …...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

LOOI机器人的技术实现解析:从手势识别到边缘检测

LOOI机器人作为一款创新的AI硬件产品&#xff0c;通过将智能手机转变为具有情感交互能力的桌面机器人&#xff0c;展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家&#xff0c;我将全面解析LOOI的技术实现架构&#xff0c;特别是其手势识别、物体识别和环境…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...