当前位置: 首页 > 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 …...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...