用环形数组实现队列(多种高级方法,由浅入深)

news/2024/11/7 21:46:58/

同普通数组实现的队列相比,普通数组的头结点和尾节点都是固定的,在进行移除的时候如果移除了一个节点,后面所有节点都需要进行移除操作,需要的时间复杂度更高

在环形数组中,确定了头尾指针的环形数组很好地解决了这一点

我们来看具体思路

方法一:牺牲一个存储容量

有两个指针,在环形数组为空的时候它们都指向这个0索引

加入元素之后,尾指针后移一位,直到尾指针的 下一个和头指针重合,如图

在进行移除操作的时候,将头指针前进一位即可

 

 

 isfull:当尾指针的下一个位置与头指针重合时,说明环形数组已经满了

用索引来表示的话每次让移动让tail+1,和数组长度取模即可,再和head的值进行判断

isempty:当尾指针与头指针重合的时候,说明环形数组为空

为了使下标可以为0到4循环,我们需要控制tail和head,所以我们可以这么表示

进行head和tail的迭代

 head=(head+1)%array.length;tail=(tail+1)%array.length;

在迭代器中,将初始节点定位为p=head,循环条件为p!=tail,因为tail指的是下一个存入元素的数组位置 

我们来看方法实现

public class ArrayQueue1 <E>implements Queue<E>,Iterable<E>{private E[] array;private int head=0;private int tail=0;@SuppressWarnings("all")public ArrayQueue1(int capacity) {array = (E[]) new Object[capacity+1];}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int p=head;@Overridepublic boolean hasNext() {return p!=tail;}@Overridepublic E next() {E value=array[p];p=(p+1)%array.length;return value;}};}@Overridepublic boolean offer(E value) {if(isFull()){return false;}array[tail]=value;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;}
}

方法二:通过数组内元素个数进行判断

和之前的思路相近,我们多设置一个size记录元素个数,这个时候不需要牺牲一个存储容量,在isfull判断中直接通过比较size和数组长度,在非空判断中,判断size是否为0即可

关于迭代器遍历,我们需要再引入一个变量count,初始值赋值为0,循环条件是count<size,因为size代表元素个数

我们来看代码

ic class ArrayQueue2 <E>implements Queue<E>,Iterable<E>{private E[] array;private int head=0;private int tail=0;private int size=0;//队列中元素个数@SuppressWarnings("all")public ArrayQueue2(int capacity) {array = (E[]) new Object[capacity];}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int p=head;int count=0;@Overridepublic boolean hasNext() {return count<size;}@Overridepublic E next() {E value=array[p];p=(p+1)%array.length;count++;return value;}};}@Overridepublic boolean offer(E value) {if(isFull()){return false;}array[tail]=value;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;}
}

方法三:不通过牺牲元素和进行headtail处理

我们还是设置头尾指针,我们以上图为例子,有一个长度为3的环形数组

我们一直将head和tail进行移动的时候递增,不再通过head和tail做处理来代表索引,而是通过将递增的head和tail进行计算来求索引,我们不再通过array[head]或者array[tail]代表元素值,而是通过

array[head%array.length]和array[tail%array.length]

在进行非空判断的时候,思路还是tail=head

在进行非满判断的时候,思路则是通过tail-head等不等于数组长度,无需牺牲一个存储空间。

我们来看代码

public class ArrayQueue3<E> implements Queue<E>, Iterable<E>{private final E[] array;private int head = 0;private int tail = 0;@SuppressWarnings("all")public ArrayQueue3(int capacity) {array = (E[]) new Object[capacity];}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int p=head;@Overridepublic boolean hasNext() {return p!=tail;}@Overridepublic E next() {E value=array[head%array.length];p++;return value;}};}@Overridepublic boolean offer(E value) {if(isFull()){return false;}array[tail%array.length] = value;tail++;return true;}@Overridepublic E poll() {if (isEmpty()){return null;}E value=array[head%array.length];head++;return value;}@Overridepublic E peek() {if (isEmpty()){return null;}E vakue=array[head%array.length];return vakue;}@Overridepublic boolean isEmpty() {return head == tail;}@Overridepublic boolean isFull() {return tail-head == array.length;}
}

一些问题思考

在方法三中,我们不对head和tail进行处理,而是放任其递增,因为int是有范围的,再超过tail的最大范围之后会报错,所以我们思考处理方法

第一种方法,通过转成长整型long避免越界报错,强制转型

array[(int) (Integer.toUnsignedLong(tail)%array.length)]

但是所有涉及的数组都需要进行强制转型,会比较复杂

二进制中按位与运算

求模运算:

  • 如果除数是2的n次方
  • 那么被除数的后n位即为余数(模)
  • 求被除数的后n位方法:与2^n-1次方进行按位与运算
array[head&(array.length-1)];

修改如上

如果数组长度不是2的n次方,我们该如何应对呢

将数组长度根据传入参数设置成2的n次方

第一种方法直接抛出异常

2^n&2^n-1=0

我们可以根据这个规律直接抛出异常

public ArrayQueue3(int capacity) {//1.抛异常if((capacity&capacity-1)!=0){throw new IllegalArgumentException("capacity must be a power of 2");}array = (E[]) new Object[capacity];}

第二种方法是修改传入参数

我们先看思路,假设传进来的数值是30

我们需要将30改成32,也就是找到最近的2的n次方等于32,

我们可以看到log2(30)大约是等于4.几,为了使其变成5,我们可以将log(30)+1,并将其强制转型为整型

又因为idea java语言中的Math包里面只有log10,所以我们可以使用换底公式

但是如果说本来这个数字就是2的n次幂的话再+1就会修改它的值,所以我们可以给传入的参数值进行-1处理,这样就可以很好的避免

在我们得到了n次幂的基础上,我们只需要对1进行左移即可(2^0=1)

代码如下

public static void main(String[] args) {int c=30;int n=(int)(Math.log10(c-1)/Math.log10(2))+1;System.out.println(1<<n);}

或者我们也可以直接利用一个公式

求离C最近,比C大的2^n次幂

c-=1;
c|=c>>1;
c|=c>>2;
c|=c>>4;
c|=c>>8;
c|=c>>16;
c+=1;

代码如下

 @SuppressWarnings("all")public ArrayQueue3(int c) {c-=1;c|=c>>1;c|=c>>2;c|=c>>4;c|=c>>8;c|=c>>16;c+=1;array = (E[]) new Object[c];}


http://www.ppmy.cn/news/1545174.html

相关文章

js下载excel示例demo

<Buttontype{"primary"}key"out"onClick{async ()>{const ExportJsonExcel require("js-export-excel");const datas selectedRowsState //确保勾到的数据是一个列表&#xff0c;列表中每个值是字典const option {};const dataTable […

私有化视频平台EasyCVR海康大华宇视视频平台视频诊断技术是如何实时监测视频质量的?

在现代视频监控系统中&#xff0c;确保视频流的质量和稳定性至关重要。随着技术的进步&#xff0c;视频诊断技术已经成为实时监测视频质量的关键工具。这种技术通过智能分析算法对视频流进行实时评估和处理&#xff0c;能够自动识别视频中的各种质量问题&#xff0c;并给出相应…

stable diffusion图生图

本节内容&#xff0c;给大家带来的是stable diffusion的图生图课程&#xff0c;我们在midjourney的课程中有学习过midjourney的图生图功能&#xff0c;即使用垫图的方式来引导AI绘制图片。图生图是AI绘图程序一个非常重要的功能&#xff0c;stable diffusion同样提供了类似的功…

MYSQL作业五

1.触发器 准备工作 作业 建立触发器&#xff0c;订单表中增加订单数量后&#xff0c;商品表商品数量同步减少对应的商品订单的数量&#xff0c;并测试 建立触发器&#xff0c;实现功能&#xff1a;客户取消订单&#xff0c;恢复商品表对应商品的数量 建立触发器&#xff0…

JAVA日期加减运算 JsonObject 转换对象List

1.用java.util.Calender来实现 Calendar calendarCalendar.getInstance(); calendar.setTime(new Date());System.out.println(calendar.get(Calendar.DAY_OF_MONTH));//今天的日期calendar.set(Calendar.DAY_OF_MONTH,calendar.get(Calendar.DAY_OF_MONTH)1);//让日期加1 Sy…

qt QStandardItemModel详解

1、概述 QStandardItemModel是Qt框架中提供的一个基于项的模型类&#xff0c;用于存储和管理数据&#xff0c;这些数据可以以表格的形式展示在视图控件&#xff08;如QTableView、QTreeView等&#xff09;中。QStandardItemModel支持丰富的数据操作&#xff0c;包括添加、删除…

Linux-socket详解

Linux-socket详解_socket linux-CSDN博客

智能编码企业级方案与实践

大家好&#xff0c;我是袁庭新。今天分享一篇关于企业如何高效落地研发智能化的过程的相关内容。 作为未来的软件开发工程师&#xff0c;我们不光要学习这些先进的AIGC生产力工具&#xff0c;还得深入了解企业里智能编程的那些实际做法和应用情况。只有这样&#xff0c;咱们才…