【数据结构】队列(链表实现 + 力扣 + 详解 + 数组实现循环队列 )
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配置主机清单 …...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...

Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...

Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...
云原生周刊:k0s 成为 CNCF 沙箱项目
开源项目推荐 HAMi HAMi(原名 k8s‑vGPU‑scheduler)是一款 CNCF Sandbox 级别的开源 K8s 中间件,通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度,为容器提供统一接口,实现细粒度资源配额…...

Vue3 PC端 UI组件库我更推荐Naive UI
一、Vue3生态现状与UI库选择的重要性 随着Vue3的稳定发布和Composition API的广泛采用,前端开发者面临着UI组件库的重新选择。一个好的UI库不仅能提升开发效率,还能确保项目的长期可维护性。本文将对比三大主流Vue3 UI库(Naive UI、Element …...