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

【数据结构】队列(链表实现 + 力扣 + 详解 + 数组实现循环队列 )

Hi~!这里是奋斗的明志,很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎 ~~
🌱🌱个人主页:奋斗的明志
🌱🌱所属专栏:数据结构

在这里插入图片描述

📚本系列文章为个人学习笔记,在这里撰写成文一为巩固知识,二为展示我的学习过程及理解。文笔、排版拙劣,望见谅。

在这里插入图片描述

文章目录

  • 一、队列(Queue)
    • 1.概念
    • 2.队列的使用
  • 二、队列模拟实现
    • 1.用双链表实现队列
    • 2.循环队列(利用数组设计)
      • 2.1循环队列图解
      • 2.2代码展示
  • 三、双端队列 (Deque)
  • 四、用队列实现栈(面试题)
    • 1.题目
    • 2.解析
    • 3.代码展示
  • 五、用栈实现队列(面试题)
    • 1.题目
    • 2.解析
    • 3.代码展示
  • 总结


一、队列(Queue)


1.概念


队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)
入队列:进行插入操作的一端称为队尾(Tail/Rear)
出队列:进行删除操作的一端称为队头 (Head/Front)
在这里插入图片描述


2.队列的使用


在Java中, Queue是个接口,底层是通过链表实现的。
在这里插入图片描述

方法功能
boolean offer(E e)入队列
E poll()出队列
peek()获取队头元素
int size()获取队列中有效元素个数
boolean isEmpty()检测队列是否为空

代码如下(示例):

public static void main(String[] args) {Queue<Integer> q = new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5); //从队尾入队列 System.out.println(q.size());System.out.println(q.peek()); // 获取队头元素q.poll();System.out.println(q.poll()); // 从队头出队列 ,并将删除的元素返回if (q.isEmpty()) {System.out.println("队列空");} else {System.out.println(q.size());}
}

二、队列模拟实现


队列中既然可以存储元素,那底层肯定要有能够保存元素的空间,通过前面线性表的学习了解到常见的空间类型有两种:顺序结构链式结构

思考下: 队列的实现使用顺序结构还是链式结构好?


1.用双链表实现队列

进队:
在这里插入图片描述
出队:

在这里插入图片描述


代码如下(示例):

package queuedemo;public class MyQueue {//用双链表实现队列//结点类static class ListNode {public int val;public ListNode next;public ListNode prev;//提供构造方法public ListNode(int val) {this.val = val;}}public ListNode head;//头结点public ListNode last;//尾结点/*** 1.尾插法* 相当于入队*/public void offer(int val) {ListNode node = new ListNode(val);if (head == null) {head = last = node;} else {last.next = node;node.prev = last;last = last.next;}}/*** 2.头删* 相当于出队*/public int poll() {if (head == null) {return -1;}int val = -1;if (head.next == null) {val = head.val;head = null;last = null;return val;}val = head.val;head = head.next;head.prev = null;return val;}public boolean empty() {return head == null;}public int peek(){if (head == null){return -1;}return head.val;}
}

2.循环队列(利用数组设计)


实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列环形队列通常使用数组实现

如何区分空与满?

  1. 通过添加 size 属性记录
  2. 保留一个位置
  3. 使用标记

2.1循环队列图解


在这里插入图片描述


在这里插入图片描述

2.2代码展示

设计循环队列


在这里插入图片描述


package queuedemo;//利用数组设计循环队列
public class MyCircularQueue {public int[] elem;public int front;public int rear;public MyCircularQueue(int k) {//构造方法进行数组初始化this.elem = new int[k];}/*** 入队操作** @param value* @return*/public boolean enQueue(int value) {if (isFull()) {return false;}elem[rear] = value;//例如  (k - 1 + 1) % k = 0rear = (rear + 1) % elem.length;return true;}/*** 出队操作** @return*/public boolean deQueue() {//先判断空不空if (isEmpty()) {return false;}front = (front + 1) % elem.length;return true;}/*** 得到队头元素,不删除* @return*/public int Front() {//先判断空不空if (isEmpty()) {return -1;}return elem[front];}/*** 得到队尾元素,不删除* @return*/public int Rear() {//先判断空不空if (isEmpty()) {return -1;}int index = (rear == 0) ? elem.length - 1 : rear - 1;return elem[index];}public boolean isEmpty() {return front == rear;}/*** 判断是否满了** @return*/public boolean isFull() {return (rear + 1) % elem.length == front;}
}

三、双端队列 (Deque)

双端队列(deque)是指允许两端都可以进行入队和出队操作的队列, deque 是“double ended queue” 的简称。 那就说明元素可以从队头出队和入队,也可以从队尾出队和入队。
在这里插入图片描述

  • Deque是一个接口,使用时必须创建LinkedList的对象。

在这里插入图片描述

  • 在实际工程中,使用Deque接口是比较多的,栈和队列均可以使用该接口。
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现 
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

四、用队列实现栈(面试题)

用队列实现栈

1.题目


在这里插入图片描述

2.解析

  • 构造方法 MyStack():

    初始化两个队列 queue1queue2,这两个队列用来辅助实现栈的操作。

  • 压栈操作 push(int x):

    如果当前栈为空(即两个队列都为空),直接将元素 x 放入 queue1。
    如果其中一个队列不为空,将元素 x 放入非空的队列中(保持一个队列为空,一个队列非空的状态,以便后续操作)。

  • 弹出栈顶元素 pop():

    首先判断栈是否为空,如果为空直接返回 -1。
    如果 queue1 非空,将 queue1 中除了最后一个元素外的所有元素依次转移到 queue2 中,然后弹出 queue1 的最后一个元素作为栈顶元素返回。
    如果 queue2 非空,类似地操作,将 queue2 中除了最后一个元素外的所有元素转移到 queue1 中,然后弹出 queue2 的最后一个元素返回。

  • 获取栈顶元素 top():

    同样先判断栈是否为空,为空则返回 -1。
    如果 queue1 非空,将 queue1 中的所有元素依次转移到 queue2 中,并记录最后一个转移的元素作为栈顶元素返回。
    如果 queue2 非空,类似地操作,将 queue2 中的所有元素依次转移到 queue1 中,并记录最后一个转移的元素返回。

  • 判断栈是否为空 empty():

    如果 queue1 和 queue2 都为空,则栈为空,返回 true;否则返回 false。

这种使用两个队列来模拟栈的实现方式是经典的算法题目,可以有效地实现栈的各种操作。


3.代码展示

class MyStack {//利用队列实现栈//不能使用双端队列public Queue<Integer> queue1;public Queue<Integer> queue2;public MyStack() {//在构造方法里面实例化this.queue1 = new LinkedList<>();this.queue2 = new LinkedList<>();}/*** 压栈操作* @param x*/public void push(int x) {if (empty()){queue1.offer(x);return;}if (!queue1.isEmpty()){queue1.offer(x);}else {queue2.offer(x);}}/*** 弹出栈顶元素* @return*/public int pop() {if (empty()){//说明模拟的栈是空的return -1;}//找到不为空的元素,出size - 1 个元素if (!queue1.isEmpty()){int size = queue1.size();for (int i = 0; i < size - 1; i++) {queue2.offer(queue1.poll());}return queue1.poll();}else {int size = queue2.size();for (int i = 0; i < size - 1; i++) {queue1.offer(queue2.poll());}return queue2.poll();}}public int top() {if (empty()){//说明模拟的栈是空的return -1;}//找到不为空的元素,出size - 1 个元素if (!queue1.isEmpty()){int size = queue1.size();int tmp = -1;for (int i = 0; i < size; i++) {tmp = queue1.poll();queue2.offer(tmp);}return tmp;}else {int size = queue2.size();int tmp = -1;for (int i = 0; i < size; i++) {tmp = queue2.poll();queue1.offer(tmp);}return tmp;}}public boolean empty() {return queue1.isEmpty() && queue2.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();*/

五、用栈实现队列(面试题)

1.题目

用栈实现队列


在这里插入图片描述


2.解析


在这里插入图片描述

  • stack1 和 stack2:这两个栈用来实现队列的操作。

  • stack1 用于存储入队的元素。

  • stack2 在需要出队或查看队头元素时用来辅助操作。

  • 入队方法 push(int x):

    直接将元素 x 压入 stack1 中,即将元素添加到队列的末尾。

  • 出队方法 pop():

    首先检查队列是否为空,如果为空则返回 -1。
    如果 stack2 为空(即队列中的元素都在 stack1 中),则将 stack1 中的所有元素逐个弹出并压入 stack2,然后从 stack2 弹出栈顶元素作为出队元素返回。
    如果 stack2 非空,则直接从 stack2 弹出栈顶元素作为出队元素返回。

  • 查看队头元素方法 peek():

    首先检查队列是否为空,如果为空则返回 -1。
    如果 stack2 为空,则将 stack1 中的所有元素逐个弹出并压入 stack2,然后返回 stack2 的栈顶元素作为队头元素,但不移除它。
    如果 stack2 非空,则直接返回 stack2 的栈顶元素。

  • 判断队列是否为空方法 empty():

    如果 stack1 和 stack2 都为空,则队列为空,返回 true;否则返回 false。

总结

这段代码通过两个栈 stack1 和 stack2 实现了队列的基本功能,其中 stack1 用于入队操作,而 stack2 在需要出队或查看队头元素时扮演辅助作用。这种实现方式保证了入队操作的时间复杂度为 O(1),出队和查看队头元素的平均时间复杂度为 O(1),空间复杂度为 O(n),其中 n 是队列中的元素个数。

3.代码展示


package queuedemo;import java.util.Stack;public class MyQueue1 {//用栈实现队列//两个栈public Stack<Integer> stack1;public Stack<Integer> stack2;public MyQueue1() {this.stack1 = new Stack<>();this.stack2 = new Stack<>();}/*** 入队列** @param x*/public void push(int x) {stack1.push(x);}/*** 出队列** @return*/public int pop() {if (empty()) {return -1;}if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}return stack2.pop();}return stack2.pop();}/*** 队头元素** @return*/public int peek() {if (empty()) {return -1;}if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}return stack2.peek();}return stack2.peek();}public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
}

总结

数组下标循环的小技巧

  1. 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length

在这里插入图片描述
在这里插入图片描述

  1. 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length

在这里插入图片描述


在这里插入图片描述

在这里插入图片描述

相关文章:

【数据结构】队列(链表实现 + 力扣 + 详解 + 数组实现循环队列 )

Hi~&#xff01;这里是奋斗的明志&#xff0c;很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~~ &#x1f331;&#x1f331;个人主页&#xff1a;奋斗的明志 &#x1f331;&#x1f331;所属专栏&#xff1a;数据结构 &#x1f4da;本系列文章为个人学…...

02 Go语言操作MySQL基础教程_20240729 课程笔记

概述 如果您没有Golang的基础&#xff0c;应该学习如下前置课程。 Golang零基础入门Golang面向对象编程Go Web 基础Go语言开发REST API接口_20240728 基础不好的同学每节课的代码最好配合视频进行阅读和学习&#xff0c;如果基础比较扎实&#xff0c;则阅读本教程巩固一下相…...

相交链表 - 力扣(LeetCode)C语言

160. 相交链表 - 力扣&#xff08;LeetCode&#xff09; (点击前面链接即可查看题目) 一、题目 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。 图示两个链表在节点 c1 开始…...

【Python】基础学习技能提升代码样例3:JSON文本处理

对json的处理&#xff0c;无非是编码和解码两部分 编码&#xff1a;将python数据结构转换为json字符串解码: 将json字符串转换为python数据结构 另外&#xff0c;还有.json文件的读写 一、编码 json.dumps(obj, *, skipkeysFalse, ensure_asciiTrue, check_circularTrue, a…...

最新Yiso智云搜索引擎系统源码/开源PHP源码/修复版

源码简介&#xff1a; 最新Yiso智云搜索引擎系统源码/开源PHP源码/修复版。Yiso 是一个性能非常好的搜索引擎&#xff0c;不仅免费开源&#xff0c;还能当作收录网址的平台来用呢&#xff01;只需要输入关键词&#xff0c;就能轻松找到相关的搜索结果内容。 1、Yiso 用的是自…...

Anconda 快速常用命令简洁版

目的&#xff1a;简单清楚的使用基本的conda 命令 可能需求 查看项目中的虚拟环境及依赖是否满足需求操作新环境来满足项目或者论文的实现 Anconda 常用命令 conda 查看基础命令1. 进入Anaconda 环境2. 查看版本3.查看有哪些虚拟环境4.激活虚拟环境5. 进入虚拟环境查看6. 退出…...

Android 系统启动动画

一、接着我们把 bootanimation.zip 动画文件 预制到 /system/media/ 目录下&#xff1a; 二、目录/system/media/bootanimation.zip PRODUCT_COPY_FILES \$(LOCAL_PATH)/bootanimation.zip:/system/media/bootanimation.zipPRODUCT_ARTIFACT_PATH_REQUIREMENT_WHITELIST \ /…...

解决antd打开modal时页面自动跳到顶部问题

问题原因&#xff1a;antd的样式中有一行&#xff0c;如下样式代码&#xff0c;这行代码导致了在本来有滚动条的页面底部触发modal弹出时&#xff0c;会自动滚动到页面顶部。 html {overflow-y: scroll; } 解决办法&#xff1a;删除这行代码、或者将html的overflow-y属性改成…...

什么是等保测评2.0,等保测评如何定级

在信息化时代&#xff0c;网络安全已成为国家安全的重要组成部分。为了应对日益复杂的网络安全形势&#xff0c;我国推出了网络安全等级保护制度&#xff0c;其中等保测评是评估信息系统安全防护能力的关键环节。本文将深入探讨等保2.0的测评流程和定级标准&#xff0c;以揭示其…...

【嵌入式英语教程--6】C语言中的数组与指针

C语言中的数组与指针 英文原文 Arrays and pointers are fundamental concepts in the C programming language. An array is a collection of elements of the same data type stored in contiguous memory locations. Arrays can be used to store and manipulate sequence…...

RocketMQ 中的同步发送

在现代分布式系统中&#xff0c;消息队列是实现异步通信和解耦的重要组件。Apache RocketMQ 是一款高性能、高吞吐量的分布式消息中间件&#xff0c;广泛应用于电商、金融等领域。本文将详细介绍 RocketMQ 中的同步发送&#xff0c;包括其原理、应用场景、代码示例及注意事项。…...

c语言指针2

文章目录 一、void * 指针二、const关键字1.const修饰变量2.const修饰指针变量2. 1 const放在*的右边2. 2 const放在*的左边2. 3 总结 三、指针的运算3. 1指针的加减运算3. 2 指针 - 指针3. 3 指针的关系运算 四、野指针4. 1 什么叫野指针&#xff1f;4. 1 野指针的成因4.1.1 指…...

十七、openCV教程 图像轮廓

一、图像轮廓 图像轮廓是具有相同颜色或灰度的连续点的曲线.轮廓在形状分析和物体的检测和识别中很有用。 轮廓的作用:.用于图形分析、物体的识别和检测 注意点: 为了检测的准确性&#xff0c;需要先对图像进行二值化或Canny操作。 画轮廓时会修改输入的图像,如…...

基于视觉的语义匹配见多了,那基于雷达的呢?

论文题目&#xff1a; LiDAR-based HD Map Localization using Semantic Generalized ICP with Road Marking Detection 论文作者&#xff1a; Yansong Gong, Xinglian Zhang, Jingyi Feng, Xiao He and Dan Zhang 作者单位&#xff1a;北京驭势科技有限公司 导读&#xff…...

01、爬虫学习入门

爬虫&#xff1a;通过编写程序&#xff0c;来获取获取互联网上的资源 需求&#xff1a;用程序模拟浏览器&#xff0c;输入一个网址&#xff0c;从该网址获取到资源或内容 一、入门程序 #使用urlopen来进行爬取 from urllib.request import urlopen url "http://www.ba…...

我与C语言二周目邂逅vlog——6.文件操作

1. 为什么使⽤⽂件&#xff1f; 如果没有⽂件&#xff0c;我们写的程序的数据是存储在电脑的内存中&#xff0c;如果程序退出&#xff0c;内存回收&#xff0c;数据就丢失 了&#xff0c;等再次运⾏程序&#xff0c;是看不到上次程序的数据的&#xff0c;如果要将数据进⾏持久…...

Hugo 部署与自动更新(Git)

文章目录 Nginx部署Hugonginx.confhugo.conf Hugo自动更新Hugo自动更新流程添加访问令牌添加web hookrust实现自动更新接口 Nginx部署Hugo nginx.conf user nginx; worker_processes auto;error_log /var/log/nginx/error.log notice; pid /var/run/nginx.pid;even…...

HTTP代理揭秘:这些场景你都用对了吗?

HTTP代理是网络中常见的一种工具&#xff0c;可以帮助我们提升网络安全性和隐私保护&#xff0c;优化网络访问速度。本文将详细介绍什么是HTTP代理及其适用的场景。 HTTP代理是介于客户端&#xff08;如浏览器&#xff09;和服务器之间的中间服务器。它接收客户端的HTTP请求&a…...

电动汽车充电技术及运营知识问答pdf

电动汽车充电技术及运营知识问答 作者:马银山编著 出版社:北京&#xff1a;中国电力出版社 ISBN:9787512320406 资源大小:16.99MB 目录&#xff1a; http://literalink.top/resource/detail/7181601144102195200 第一章 电动汽车基本知识 1 1-1什么是电动汽车&#xff1f; 11-…...

playbooks 分布式部署 LNMP

1、环境配置 ansible 服务器 192.168.10.10nginx 服务器 192.168.10.20mysql 服务器 192.168.10.21php 服务器 192.168.10.22 2、安装 ansble #192.168.10.10节点 yum install -y epel-release #先安装 epel 源 yum install -y ansible配置主机清单 …...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...