【数据结构】队列(链表实现 + 力扣 + 详解 + 数组实现循环队列 )
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.循环队列(利用数组设计)
实际中我们有时还会使用一种队列叫
循环队列
。如操作系统课程讲解生产者消费者模型
时可以就会使用循环队列
。环形队列通常使用数组实现
。
如何区分空与满?
- 通过添加 size 属性记录
- 保留一个位置
- 使用标记
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():
初始化两个队列
queue1
和queue2
,这两个队列
用来辅助
实现栈的操作。 -
压栈操作 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();}
}
总结
数组下标循环的小技巧
- 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length
- 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length
相关文章:

【数据结构】队列(链表实现 + 力扣 + 详解 + 数组实现循环队列 )
Hi~!这里是奋斗的明志,很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎 ~~ 🌱🌱个人主页:奋斗的明志 🌱🌱所属专栏:数据结构 📚本系列文章为个人学…...

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

相交链表 - 力扣(LeetCode)C语言
160. 相交链表 - 力扣(LeetCode) (点击前面链接即可查看题目) 一、题目 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 图示两个链表在节点 c1 开始…...
【Python】基础学习技能提升代码样例3:JSON文本处理
对json的处理,无非是编码和解码两部分 编码:将python数据结构转换为json字符串解码: 将json字符串转换为python数据结构 另外,还有.json文件的读写 一、编码 json.dumps(obj, *, skipkeysFalse, ensure_asciiTrue, check_circularTrue, a…...

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

Anconda 快速常用命令简洁版
目的:简单清楚的使用基本的conda 命令 可能需求 查看项目中的虚拟环境及依赖是否满足需求操作新环境来满足项目或者论文的实现 Anconda 常用命令 conda 查看基础命令1. 进入Anaconda 环境2. 查看版本3.查看有哪些虚拟环境4.激活虚拟环境5. 进入虚拟环境查看6. 退出…...
Android 系统启动动画
一、接着我们把 bootanimation.zip 动画文件 预制到 /system/media/ 目录下: 二、目录/system/media/bootanimation.zip PRODUCT_COPY_FILES \$(LOCAL_PATH)/bootanimation.zip:/system/media/bootanimation.zipPRODUCT_ARTIFACT_PATH_REQUIREMENT_WHITELIST \ /…...
解决antd打开modal时页面自动跳到顶部问题
问题原因:antd的样式中有一行,如下样式代码,这行代码导致了在本来有滚动条的页面底部触发modal弹出时,会自动滚动到页面顶部。 html {overflow-y: scroll; } 解决办法:删除这行代码、或者将html的overflow-y属性改成…...
什么是等保测评2.0,等保测评如何定级
在信息化时代,网络安全已成为国家安全的重要组成部分。为了应对日益复杂的网络安全形势,我国推出了网络安全等级保护制度,其中等保测评是评估信息系统安全防护能力的关键环节。本文将深入探讨等保2.0的测评流程和定级标准,以揭示其…...
【嵌入式英语教程--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 中的同步发送
在现代分布式系统中,消息队列是实现异步通信和解耦的重要组件。Apache RocketMQ 是一款高性能、高吞吐量的分布式消息中间件,广泛应用于电商、金融等领域。本文将详细介绍 RocketMQ 中的同步发送,包括其原理、应用场景、代码示例及注意事项。…...

c语言指针2
文章目录 一、void * 指针二、const关键字1.const修饰变量2.const修饰指针变量2. 1 const放在*的右边2. 2 const放在*的左边2. 3 总结 三、指针的运算3. 1指针的加减运算3. 2 指针 - 指针3. 3 指针的关系运算 四、野指针4. 1 什么叫野指针?4. 1 野指针的成因4.1.1 指…...
十七、openCV教程 图像轮廓
一、图像轮廓 图像轮廓是具有相同颜色或灰度的连续点的曲线.轮廓在形状分析和物体的检测和识别中很有用。 轮廓的作用:.用于图形分析、物体的识别和检测 注意点: 为了检测的准确性,需要先对图像进行二值化或Canny操作。 画轮廓时会修改输入的图像,如…...

基于视觉的语义匹配见多了,那基于雷达的呢?
论文题目: LiDAR-based HD Map Localization using Semantic Generalized ICP with Road Marking Detection 论文作者: Yansong Gong, Xinglian Zhang, Jingyi Feng, Xiao He and Dan Zhang 作者单位:北京驭势科技有限公司 导读ÿ…...

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

我与C语言二周目邂逅vlog——6.文件操作
1. 为什么使⽤⽂件? 如果没有⽂件,我们写的程序的数据是存储在电脑的内存中,如果程序退出,内存回收,数据就丢失 了,等再次运⾏程序,是看不到上次程序的数据的,如果要将数据进⾏持久…...

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代理是网络中常见的一种工具,可以帮助我们提升网络安全性和隐私保护,优化网络访问速度。本文将详细介绍什么是HTTP代理及其适用的场景。 HTTP代理是介于客户端(如浏览器)和服务器之间的中间服务器。它接收客户端的HTTP请求&a…...
电动汽车充电技术及运营知识问答pdf
电动汽车充电技术及运营知识问答 作者:马银山编著 出版社:北京:中国电力出版社 ISBN:9787512320406 资源大小:16.99MB 目录: http://literalink.top/resource/detail/7181601144102195200 第一章 电动汽车基本知识 1 1-1什么是电动汽车? 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配置主机清单 …...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...

汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...

tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...

力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...
【Android】Android 开发 ADB 常用指令
查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...
嵌入式常见 CPU 架构
架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集,单周期执行;低功耗、CIP 独立外设;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel(原始…...

倒装芯片凸点成型工艺
UBM(Under Bump Metallization)与Bump(焊球)形成工艺流程。我们可以将整张流程图分为三大阶段来理解: 🔧 一、UBM(Under Bump Metallization)工艺流程(黄色区域ÿ…...

rm视觉学习1-自瞄部分
首先先感谢中南大学的开源,提供了很全面的思路,减少了很多基础性的开发研究 我看的阅读的是中南大学FYT战队开源视觉代码 链接:https://github.com/CSU-FYT-Vision/FYT2024_vision.git 1.框架: 代码框架结构:readme有…...
游戏开发中常见的战斗数值英文缩写对照表
游戏开发中常见的战斗数值英文缩写对照表 基础属性(Basic Attributes) 缩写英文全称中文释义常见使用场景HPHit Points / Health Points生命值角色生存状态MPMana Points / Magic Points魔法值技能释放资源SPStamina Points体力值动作消耗资源APAction…...