Java——队列(Queue)

embedded/2025/1/20 17:37:43/

1.概念

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

2. 方法使用

方法
功能
boolean offer(E e)
入队列
E poll()
出队列
peek()
获取队头元素
int size()
获取队列中有效元素个数
boolean isEmpty()
检测队列是否为空
注意:在 Java 中, Queue 是个接口,底层是通过链表实现 的。因此在实例化时必须实例化 LinkedList 的对象,因为 LinkedList 实现了 Queue 接口。
代码示例如下:
java">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());}}

运行结果如下:

3.功能模拟实现(以int为例)

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

3.1 链式结构

Queue的链式结构的底层采用双向链表结构。

代码示例

java">public class MyQueue {static class ListNode {public int val;public ListNode prev ;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;public int usedSize;//从队尾入队列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;}usedSize++;}//从队头出队列,并将删除的元素返回public int poll() {if(head == null) {return -1;}int ret = head.val;if(head.next == null) {head = null;last = null;}else {head = head.next;head.prev = null;}usedSize--;return ret;}//获得队头元素public int peek() {if(head == null) {return -1;}return head.val;}//获取队列容量public int size(){return usedSize;}//判断是否为空public boolean isEmpty() {return head == null;}
}
测试代码
java">public static void main(String[] args) {MyQueue q = new MyQueue();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());}}

运行结果如下:

3.2 顺序结构(以循环队列为例)

3.2.1 概念

  队列的顺序结构,通常被称为顺序队列,是一种基于数组的队列实现方式。在这种结构中,队列的元素被存储在一段连续的存储空间(如数组)中,并通过两个指针(或索引)来跟踪队列的头部(front)和尾部(rear)。

   在顺序队列中,如果队列的尾部已经到达数组的末尾,而头部还有空闲空间,此时再尝试入队就会导致“假溢出”问题。为了解决这个问题,可以采用循环队列或动态调整数组大小的方法。

3.2.2 循环队列

   循环队列是顺序队列的一种特殊形式,它通过将数组的末尾和开头连接起来形成一个环状结构,从而有效地解决了“假溢出”问题。在循环队列中,当 rear 指针到达数组的末尾时,它会自动回绕到数组的开头。因此,在判断队列是否已满时,需要采用特殊的方法(如保留一个空闲位置或使用取模运算)来避免与队列为空的情况混淆。

3.2.2.1 数组下标循环

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

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

3.2.2.2 区分空和满
1. 使用一个额外的变量(如计数器)
2. 少用一个元素空间
3. 使用标记
创建队列时,front 与  rear 第一次相遇,用 boolean flg = false 来进行标记,如果再次遇到 flg = true 代表队列满了。
3.2.2.3 功能实现

本文主要介绍区分空和满的第二种方法。

代码示例

java">  public int[] elem;public int front;public int rear;public MyCircularQueue(int capacity) {elem = new int[capacity + 1];}//入队public boolean enQueue(int value) {if(isFull()) {return false;}elem[rear] = value;rear= (rear+1)%elem.length;return true;}//出队public boolean deQueue() {if(isEmpty()) {return false;}front= (front+1)%elem.length;return true;}//得到队头元素public int Front() {if(isEmpty()) {return -1;}return elem[front];}//判断队列是否为空public boolean isEmpty() {return front== rear;}// 判断队列是否为满public boolean isFull() {return (rear+ 1) % elem.length == front;}

测试代码

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

运行结果如下:

4. 双端队列 (Deque)

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

注意Deque是一个接口,使用时必须创建对象。

java">Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

Deque的使用与实现和Queue的差不多,我们就不在进行过多的介绍了。

本文是作者学习后的总结,如果有什么不恰当的地方,欢迎大佬指正!!!


http://www.ppmy.cn/embedded/155538.html

相关文章

Nginx正向代理配置

Nginx 正向代理默认只支持 http 协议&#xff0c;不支持 https 协议&#xff0c;需借助 "ngx_http_proxy_connect_module" 模块实现 https 正向代理&#xff0c;详情请参考&#xff1a; https://github.com/chobits/ngx_http_proxy_connect_module 安装Nginx某些模块…

算法刷题笔记——图论篇

这里写目录标题 理论基础图的基本概念图的种类度 连通性连通图强连通图连通分量强连通分量 图的构造邻接矩阵邻接表 图的遍历方式 深度优先搜索理论基础dfs 与 bfs 区别dfs 搜索过程深搜三部曲所有可达路径广度优先搜索理论基础广搜的使用场景广搜的过程 岛屿数量孤岛的总面积沉…

【C语言系列】深入理解指针(1)

前言 总所周知&#xff0c;C语言中指针部分是非常重要的&#xff0c;这一件我们会介绍指针相关的内容&#xff0c;当然后续我还会出大概4篇与指针相关的文章&#xff0c;来深入的讲解C语言指针部分&#xff0c;希望能够帮助到指针部分薄弱或者根本不会的程序员们&#xff0c;后…

IO多路复用详解-selectpollepoll

目录 1.IO多路复用概念 2.系统调用函数 2.1select 2.1.1select函数细节 2.2基于select实现并发处理 2.2.1处理流程 2.2.2服务端通信代码 2.2.3客户端通信代码 2.3基于poll函数实现并发处理 2.3.1select与poll函数区别 2.3.2poll函数 2.3.3服务器端代码实现 2.3.4客…

【论文投稿】探秘计算机视觉算法:开启智能视觉新时代

目录 引言 一、计算机视觉算法基石&#xff1a;图像基础与预处理 二、特征提取&#xff1a;视觉信息的精华萃取 三、目标检测&#xff1a;从图像中精准定位目标 四、图像分类&#xff1a;识别图像所属类别 五、语义分割&#xff1a;理解图像的像素级语义 六、计算机视觉…

nginx常用配置 (含负载均衡、反向代理、限流、Gzip压缩、图片防盗链 等示例)

nginx的配置文件通常在 /etc/nginx/nginx.conf , /etc/nginx/conf.d/*.conf 中&#xff0c; 一般直接 改 conf.d目录下的 default.conf文件&#xff0c; 然后 先检测配置文件是否有错误 nginx -t 再重新加载配置文件 或 重启nginx&#xff0c;命令如下 nginx -s reload 或…

springboot医院信管系统

摘 要 随着信息技术和网络技术的飞速发展&#xff0c;人类已进入全新信息化时代&#xff0c;传统管理技术已无法高效&#xff0c;便捷地管理信息。为了迎合时代需求&#xff0c;优化管理效率&#xff0c;各种各样的管理系统应运而生&#xff0c;各行各业相继进入信息管理时代&a…

Android 13/14 关键宏导致系统无声

ProjectConfig.mk MTK_USE_PREBUILT_BOOTIMAGE no 必须添加 否则&#xff1a; 1.会导致喇叭无声音 2.会导致录音失败 3.会导致插入耳机卡死 禁用prebuilt boot.img替换&#xff1a;或者 在device/mediatek/vendor/common/BoardConfig-vext.mk中&#xff0c;将 MTK_USE_P…