数据结构与算法——Java实现 19.队列

目录

一、概述

二、链表实现队列

接口定义

 接口实现类

测试类 

三、环形数组实现队列

优点

下标计算

判满和判空

判满

判空

辅助变量size判空和判满

方法1

 接口定义

接口实现类

测试类 

方式2

接口定义

接口实现类

测试类

方法3

 接口定义

接口实现类

测试类 


生活鲜少给人留下退路

                        —— 24.9.27

一、概述

计算机科学中,queue 是以顺序的方式维护的一组数据集合,在一端添加数据,从另一端移除数据。习惯来说,添加的一端称为尾,移除的一端称为头,就如同生活中的排队买商品

二、链表实现队列

下面以单向环形带哨兵链表方式来实现队列

接口定义

offer:向队列尾部插入值

poll:从队列头部获取值,并移除

peek:从队列头获取值,不移除

isEmpty:检查队列是否为空

isFull:检查队列是否为满

public interface Queue<E> {/*向队列尾部插入值Params:value-待插入值Returns:插入成功返回true,插入失败返回false*/boolean offer(E e);/*从队列头获取值,并移除Returns:如果队列非空返回头部值,否则返回null*/E poll();/*从队列头获取值,不移除Returns:如果队列非空返回队头值,否则返回null*/E peek();/*检查队列是否为空Return:空返回true,否则返回false*/boolean isEmpty();/*检查队列是否为满Return:满返回true,否则返回false*/boolean isFull();
}

 接口实现类

import java.util.Iterator;// 用泛型好处:1.用null代表特殊值   2.代表更多类型
public class LinkedListQueue<E>implements Queue<E>,Iterable<E> {// 静态内部结点类private static class Node<E>{E value;Node<E> next;public Node(E value, Node<E> next){this.value = value;this.next = next;}}// 定义队列的头结点和尾节点Node<E> head = new Node<>(null,null);Node<E> tail = head;private int size = 0; // 当前节点数private int capacity = 10; // 队列最大容量public LinkedListQueue(int capacity) {this.capacity = capacity;tail.next = head;}public LinkedListQueue() {tail.next = head;}/*队列插入方法,在尾部插入Params:value-待插入值Returns:插入成功返回true,插入失败返回false*/@Overridepublic boolean offer(E e) {if(isFull()){return false;}Node<E> newNode = new Node<>(e,head);tail.next = newNode;tail = newNode;size++;return true;}/*从队头获取值,并移除Returns:如果队列非空返回队头值,否则返回null*/@Overridepublic E poll() {if (isEmpty()){return null;}Node<E> first = head.next;head.next = first.next;if (first == tail){tail = head;}size--;return first.value;}/*从队列头获取值,不移除Returns:如果队列非空返回队头值,否则返回null*/@Overridepublic E peek() {if(isEmpty()){return null;}return head.next.value;}/*检查队列是否为空Return:空返回true,否则返回false*/@Overridepublic boolean isEmpty() {return head == tail;}/*检查队列是否为满Return:满返回true,否则返回false*/@Overridepublic boolean isFull() {return size == capacity;}// 队列遍历方法 迭代器@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {Node<E> current = head.next;@Overridepublic boolean hasNext() {return current != head;}@Overridepublic E next() {E value = current.value;current = current.next;return value;}};}
}

测试类 

import org.junit.Test;import java.util.List;import static org.junit.jupiter.api.Assertions.*;public class TestLinkedListQueue {// 向队列尾部插入值@Testpublic void offer() {LinkedListQueue<Integer> queue = new LinkedListQueue<>();queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertIterableEquals(queue,List.of(1,2,3,4,5));}// 从队列头获取值,不移除@Testpublic void peek(){LinkedListQueue<Integer> queue = new LinkedListQueue<>();assertNull(queue.peek());queue.offer(1);assertEquals(1,queue.peek());queue.offer(2);assertEquals(1,queue.peek());queue.offer(3);assertEquals(1,queue.peek());}// 从队头获取值,并移除@Testpublic void poll() {LinkedListQueue<Integer> queue = new LinkedListQueue<>();queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertEquals(1,queue.poll());assertEquals(2,queue.poll());assertEquals(3,queue.poll());assertEquals(4,queue.poll());assertEquals(5,queue.poll());assertNull(queue.poll());}// 向有限队列头部加入元素@Testpublic void offerLimit(){LinkedListQueue<Integer> queue = new LinkedListQueue<>(3);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertIterableEquals(queue,List.of(1,2,3));}}

三、环形数组实现队列

环形数组:

        大小固定,首尾相连的数组

        环形数组是一种逻辑上形成环形结构的数组,它在物理上通常是一个普通的线性数组,但在访问和操作时采用特定的逻辑来处理边界条件,使得元素可以从数组的末尾“循环”到开头,或者从开头“循环”到末尾。这种结构常用于实现循环队列、滑动窗口和约瑟夫环等问题,因为它避免了传统数组的越界问题,并且具有空间效率高、适合FIFO(先进先出)操作等优点。

环形数组的特点

① 逻辑环形:环形数组在逻辑上形成一个闭环,数组的最后一个元素与第一个元素相连。

② 无边界问题:由于索引是循环的,因此不存在传统数组的越界问题。

③ 空间效率高:环形数组可以充分利用数组空间,避免不必要的空间浪费。

④ 适合特定操作:如循环队列、滑动窗口等,这些操作在环形数组上实现起来更加高效。

环形数组的应用

① 循环队列:队列是一种先进先出(FIFO)的数据结构,而循环队列则是使用环形数组来实现的一种队列。在循环队列中,当队列的尾部达到数组的末尾时,下一个元素将插入到数组的开头,从而形成一个循环。

② 滑动窗口:滑动窗口是一种常用于数组/字符串处理的算法技巧,它可以在线性时间内解决一些看似需要嵌套循环的问题。环形数组可以用于实现滑动窗口的某些变体,特别是当窗口大小固定且需要循环移动时。

③ 约瑟夫环问题:约瑟夫环问题是一个著名的数学问题,描述的是n个人围成一圈,从第一个人开始报数,报到m的人出圈,然后从下一个人重新开始报数,如此循环直到所有人出圈。环形数组可以很好地模拟这个问题中的环形结构。

优点

        1.对比普通数组,起点和终点更为自由,不用考虑数据移动

        2.“环“意味着不会存在【越界】问题

        3.数组性能更佳

        4.环形数组比较适合实现有界队列、RingBuffer 等

下标计算

索引位置 =  (cur + step) % length

cur:当前指针位置

step:前进步数

length:数组长度

判满和判空

判满

(尾指针+1)% 数组长度 = 头指针

判空

头指针 = 尾指针

辅助变量size判空和判满

方法1

使用头尾指针判断队列空和满的情况

 接口定义

public interface Queue<E> {/*向队列尾部插入值Params:value-待插入值Returns:插入成功返回true,插入失败返回false*/boolean offer(E e);/*从队列头获取值,并移除Returns:如果队列非空返回头部值,否则返回null*/E poll();/*从队列头获取值,不移除Returns:如果队列非空返回队头值,否则返回null*/E peek();/*检查队列是否为空Return:空返回true,否则返回false*/boolean isEmpty();/*检查队列是否为满Return:满返回true,否则返回false*/boolean isFull();
}

接口实现类

import java.util.Iterator;public class ArrayQueue1<E> implements Queue<E>,Iterable<E> {private final E[] array;private int head = 0;private int tail = 0;public ArrayQueue1(int capacity) {array = (E[])new Object[capacity+1];}// 从队列尾部加入元素@Overridepublic boolean offer(E e) {if (isFull()){return false;}array[tail] = e;tail = (tail + 1) % array.length;return true;}// 从队列头部移除元素@Overridepublic E poll() {if (isEmpty()){return null;}E value = array[head];head = (head + 1) % array.length;return value;}// 获取队列头部元素值@Overridepublic E peek() {if (isEmpty()){return null;}return array[head];}@Overridepublic boolean isEmpty() {return head == tail;}@Overridepublic boolean isFull() {return (tail+1) % array.length == head;}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int cursor = head;@Overridepublic boolean hasNext() {return cursor != tail;}@Overridepublic E next() {E value = array[cursor];cursor = (cursor + 1) % array.length;return value;}};}
}

测试类 

import org.junit.Test;import java.util.List;import static org.junit.jupiter.api.Assertions.*;
import static org.junit.jupiter.api.Assertions.assertIterableEquals;public class TestArrayQueue1 {// 向队列尾部插入值@Testpublic void offer() {ArrayQueue1<Integer> queue = new ArrayQueue1<>(5);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertIterableEquals(queue, List.of(1,2,3,4,5));}// 从队列头获取值,不移除@Testpublic void peek(){ArrayQueue1<Integer> queue = new ArrayQueue1<>(5);assertNull(queue.peek());queue.offer(1);assertEquals(1,queue.peek());queue.offer(2);assertEquals(1,queue.peek());queue.offer(3);assertEquals(1,queue.peek());}// 从队头获取值,并移除@Testpublic void poll() {ArrayQueue1<Integer> queue = new ArrayQueue1<>(5);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertEquals(1,queue.poll());assertEquals(2,queue.poll());assertEquals(3,queue.poll());assertEquals(4,queue.poll());assertEquals(5,queue.poll());assertNull(queue.poll());}// 向有限队列头部加入元素@Testpublic void offerLimit(){ArrayQueue1<Integer> queue = new ArrayQueue1<>(3);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertIterableEquals(queue,List.of(1,2,3));}
}

方式2

引入一个辅助变量size,记录队列中的元素个数,直接通过用数组长度和size变量比较,判断队列空还是满。

接口定义

public interface Queue<E> {/*向队列尾部插入值Params:value-待插入值Returns:插入成功返回true,插入失败返回false*/boolean offer(E e);/*从队列头获取值,并移除Returns:如果队列非空返回头部值,否则返回null*/E poll();/*从队列头获取值,不移除Returns:如果队列非空返回队头值,否则返回null*/E peek();/*检查队列是否为空Return:空返回true,否则返回false*/boolean isEmpty();/*检查队列是否为满Return:满返回true,否则返回false*/boolean isFull();
}

接口实现类

import java.util.Iterator;public class ArrayQueue2<E> implements Queue<E>,Iterable<E> {private final E[] array;private int head = 0;private int tail = 0;private int size = 0;public ArrayQueue2(int capacity) {array = (E[]) new Object[capacity];}// 从队列尾部加入元素@Overridepublic boolean offer(E e) {if (isFull()){return false;}array[tail] = e;tail = (tail + 1) % array.length;size++;return true;}// 从队列头部移除元素@Overridepublic E poll() {if (isEmpty()){return null;}E value = array[head];head = (head + 1) % array.length;size--;return value;}// 获取队列头部元素值@Overridepublic E peek() {if (isEmpty()){return null;}return array[head];}@Overridepublic boolean isEmpty() {return size == 0;}@Overridepublic boolean isFull() {return size == array.length;}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int cursor = head;int count = 0;@Overridepublic boolean hasNext() {return count < size;}@Overridepublic E next() {E value = array[cursor];cursor = (cursor + 1) % array.length;count++;return value;}};}
}

测试类

import org.junit.Test;import java.util.List;import static org.junit.jupiter.api.Assertions.*;
import static org.junit.jupiter.api.Assertions.assertIterableEquals;public class TestArrayQueue2 {// 向队列尾部插入值@Testpublic void offer() {ArrayQueue2<Integer> queue = new ArrayQueue2<>(5);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertIterableEquals(queue, List.of(1,2,3,4,5));}// 从队列头获取值,不移除@Testpublic void peek(){ArrayQueue2<Integer> queue = new ArrayQueue2<>(5);assertNull(queue.peek());queue.offer(1);assertEquals(1,queue.peek());queue.offer(2);assertEquals(1,queue.peek());queue.offer(3);assertEquals(1,queue.peek());}// 从队头获取值,并移除@Testpublic void poll() {ArrayQueue2<Integer> queue = new ArrayQueue2<>(5);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertEquals(1,queue.poll());assertEquals(2,queue.poll());assertEquals(3,queue.poll());assertEquals(4,queue.poll());assertEquals(5,queue.poll());assertNull(queue.poll());}// 向有限队列头部加入元素@Testpublic void offerLimit(){ArrayQueue2<Integer> queue = new ArrayQueue2<>(3);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertIterableEquals(queue,List.of(1,2,3));}
}

方法3

head和tail直接存储指针值,tail存储最后一个元素的指针值,计算tail存储指针值指向的索引,tail并不直接指向索引不把计算结果存入head和tail中

 接口定义

public interface Queue<E> {/*向队列尾部插入值Params:value-待插入值Returns:插入成功返回true,插入失败返回false*/boolean offer(E e);/*从队列头获取值,并移除Returns:如果队列非空返回头部值,否则返回null*/E poll();/*从队列头获取值,不移除Returns:如果队列非空返回队头值,否则返回null*/E peek();/*检查队列是否为空Return:空返回true,否则返回false*/boolean isEmpty();/*检查队列是否为满Return:满返回true,否则返回false*/boolean isFull();
}

接口实现类

import java.util.Iterator;public class ArrayQueue3<E> implements Queue<E>,Iterable<E> {private final E[] array;// head tail是两个不断递增的整数private int head = 0;private int tail = 0;@SuppressWarnings("all")public ArrayQueue3(int capacity) {// 初始化数组array = (E[]) new Object[capacity];}// 从队列尾部加入元素@Overridepublic boolean offer(E e) {// 判满if(isFull()){return false;}array[tail % array.length] = e;tail ++;return true;}// 从队列头部移除元素@Overridepublic E poll() {if (isEmpty()){return null;}// 找到索引位置E e = array[head % array.length];head ++;return e;}// 获取队列头部元素值@Overridepublic E peek() {if (isEmpty()){return null;}return array[head % array.length];}@Overridepublic boolean isEmpty() {return head == tail;}@Overridepublic boolean isFull() {return tail - head == array.length;}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int cursor = head;@Overridepublic boolean hasNext() {return cursor != tail;}@Overridepublic E next() {E e = array[cursor % array.length];cursor++;return e;}};}
}

测试类 

import org.junit.Test;import java.util.List;import static org.junit.jupiter.api.Assertions.*;
import static org.junit.jupiter.api.Assertions.assertIterableEquals;public class TestArrayQueue3 {// 向队列尾部插入值@Testpublic void offer() {ArrayQueue3<Integer> queue = new ArrayQueue3<>(5);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertIterableEquals(List.of(1, 2, 3, 4, 5), queue);}// 从队列头获取值,不移除@Testpublic void peek(){ArrayQueue3<Integer> queue = new ArrayQueue3<>(5);assertNull(queue.peek());queue.offer(1);assertEquals(1,queue.peek());queue.offer(2);assertEquals(1,queue.peek());queue.offer(3);assertEquals(1,queue.peek());}// 从队头获取值,并移除@Testpublic void poll() {ArrayQueue3<Integer> queue = new ArrayQueue3<>(5);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertEquals(1,queue.poll());assertEquals(2,queue.poll());assertEquals(3,queue.poll());assertEquals(4,queue.poll());assertEquals(5,queue.poll());assertNull(queue.poll());}// 向有限队列头部加入元素@Testpublic void offerLimit(){ArrayQueue3<Integer> queue = new ArrayQueue3<>(3);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);assertIterableEquals(List.of(1, 2, 3), queue);}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1548546.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Nginx配置及部署前端项目,安排!

哈喽小伙伴们大家好&#xff01;我是程序媛小李&#xff0c;一位正在往全栈方向发展的前端小姐姐&#xff0c;今天给大家分享一下在日常编码中我们是怎么使用nginx来部署前端项目的&#xff01; Nginx安装 浏览器输入nginx&#xff0c;来到官网 右边找到doewnload&#xff0c…

短剧向左,体育向右,快手前途未卜?

最近&#xff0c;辗转于多项业务的快手收到了来自于市场“寓褒于贬”的评价。 麦格理发表报告表示&#xff0c;短剧业务正成为快手近期新的增长动力&#xff0c;亦维持对快手的正面看法&#xff0c;给予“跑赢大市”评级&#xff0c;预期上市前投资者出售2%股份对基本面没有太…

掌握AI提示词的艺术:应用、防护与成为提示词专家的策略

掌握好提示词的编写&#xff0c;可以用来做的事情&#xff1a; 写简历、输出面试题、输出ppt、思维导图、提取摘要、翻译、总结会议纪要、总结审计报告、数据分析、写广告/营销/请假等跟文字相关的文案、爆款文章、小说、写周报/月报。 如何写提示词 4大原则 1、 指令要精简…

Python精选200Tips:176-180

针对图像的经典卷积网络结构进化史及可视化 P176--LeNet-5【1988】模型结构说明模型结构代码模型结构可视化 P177--AlexNet【2012】模型结构及创新性说明模型结构代码模型结构可视化 P178--VGGNet【2014】VGG19模型结构及创新性说明VGG19模型结构代码VGG19模型结构可视化 P179-…

广东自闭症寄宿学校:为大龄自闭症儿童提供全寄宿制教育

在广东这片温暖的土地上&#xff0c;有一类特殊的孩子&#xff0c;他们以自己独特的方式感知世界&#xff0c;却往往因为自闭症的障碍而在成长的道路上步履维艰。为了给予这些大龄自闭症儿童更加全面、专业的关怀与教育&#xff0c;广东地区涌现出了一批自闭症寄宿学校&#xf…

Java中的Junit、类加载时机与机制、反射、注解及枚举

目录 Java中的Junit、类加载时机与机制、反射、注解及枚举 Junit Junit介绍与使用 Junit注意事项 Junit其他注解 类加载时机与机制 类加载时机 类加载器介绍 获取类加载器对象 双亲委派机制和缓存机制 反射 获取类对象 获取类对象的构造方法 使用反射获取的构造方法创建对象 获…

从0-1搭建海外社媒矩阵,详细方案深度拆解

做买卖&#xff0c;好的产品质量固然是关键&#xff0c;但如何让更多的消费者知道&#xff1f;营销推广是必不可少的。在互联网时代&#xff0c;通过社交媒体推广已经成为跨境电商卖家常用的广告手段。 如何通过海外社交媒体矩阵扩大品牌影响力&#xff0c;实现营销目标&#…

【开源项目】数字孪生智慧停车场——开源工程及源码

飞渡科技数字孪生停车场管理平台&#xff0c;基于国产数字孪生3D渲染引擎&#xff0c;结合数字孪生、物联网IOT&#xff0c;以及车牌自动识别、视频停车诱导等技术&#xff0c;实现停车场的自动化、可视化和无人化值守管理。 以3D可视化技术为基础&#xff0c;通过三维场景完整…

240927-各种卷积最清晰易懂blender动画展示

240927-一些常用卷积清晰易懂的blender动画展示&#xff08;Conv、GConv、DWConv、1*1Conv、Shuffle&#xff09; 在几个月前&#xff0c;写过一篇关于卷积过程中输入图像维度变化的博客240627_关于CNN中图像维度变化问题_图像的尺寸为什么又四个维度-CSDN博客&#xff0c;但是…

猫鱼分干(模拟---拆分步骤)

算法分析&#xff1a; 注意&#xff1a;总是更新遍历方向上的元素&#xff08;eg. 左 i-1 和 i &#xff1a;更新i&#xff09;区分水平和分配量从左向右&#xff1a;只要右侧水平大于左侧&#xff0c;即右侧等于左侧值加一从右向左&#xff1a;若左侧水平大于右侧&#xf…

一次实践:给自己的手机摄像头进行相机标定

文章目录 1. 问题引入2. 准备工作2.1 标定场2.2 相机拍摄 3. 基本原理3.1 成像原理3.2 畸变校正 4. 标定解算4.1 代码实现4.2 详细解析4.2.1 解算实现4.2.2 提取点位 4.3 解算结果 5. 问题补充 1. 问题引入 不得不说&#xff0c;现在的计算机视觉技术已经发展到足够成熟的阶段…

c++day08

思维导图 栈 #include <iostream>using namespace std;template <typename T> class Stack { private:static const size_t MAX 100; // 定义固定容量T data[MAX]; // 存储栈元素的数组size_t len; // 当前栈的大小public:…

浅谈电气火灾监控系统在变电所的应用

摘要&#xff1a;阐述电气火灾监控系统在变电所的应用&#xff0c;电气火灾监控系统的管理措施&#xff0c;包括运行标准、运行模式、运行原则、警报阈值、监控显示。安科瑞叶西平1870*6160015 关键词:监控系统&#xff1b;警报阀值&#xff1b;运行模式&#xff1b;医院&…

高效免费!PDF秒变Word,在线免费转换工具推荐!!!

#创作灵感# 工作中&#xff0c;总是需要将pdf文件转换成word文件&#xff0c;便于后期编辑、处理、使用&#xff0c;但是又没有wps会员&#xff0c;虽然去淘宝买&#xff0c;一天也就8毛钱左右&#xff0c;但是转换文件的工作几乎每天都需要做&#xff0c;长此以往&#xff0c;…

7.字符串 Strings

作业系统链接 字符串文字可以使用单引号、双引号或三引号来定义&#xff0c;其中三引号特别适用于多行字符串。转义序列如\n&#xff08;换行&#xff09;和\t&#xff08;制表符&#xff09;在字符串中起到特殊作用。字符串方法如replace()、strip()、lower()和upper()提供了丰…

外国名人面孔识别系统源码分享

外国名人面孔识别检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer…

艺术作品风格识别系统源码分享

艺术作品风格识别检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer…

Java数据结构--List介绍

前言&#xff1a; 数据结构可以说是一门思想&#xff0c;当我们在对数据处理、储存的时候需要用到。 前面我用C语言写过数据结构的相关内容&#xff0c;在Java阶段的数据结构思想是一样的&#xff0c;就是有些地方实现的方式是有区别的。 因此在Java阶段前期的数据结构&#xf…

Python的包管理工具pip安装

Python的包管理工具pip安装 一、安装步骤1.检查 pip是否已安装2.安装 pip方法一&#xff1a;通过 ​ensurepip​ 模块安装(推荐)方法二&#xff1a;通过 ​get-pip.py​ 脚本安装&#xff08;经常应为网络域名问题连接不上&#xff09; 3.验证pip安装4.创建别名5.更新pip 二、常…

找不到msvcr100.dll怎么解决?总结6个有效的解决方法

在使用计算机的过程中&#xff0c;我们经常会遇到一些错误提示&#xff0c;其中之一就是“msvcr100.dll丢失”。这个问题可能会让我们感到困惑和无助&#xff0c;但是不用担心&#xff0c;本文将为大家介绍六种实用的解决方法&#xff0c;帮助你轻松解决这个问题。 一&#xff…