【Java 数据结构及算法实战】系列 014:Java队列08——数组实现的双端队列ArrayDeque

简介: 【Java 数据结构及算法实战】系列 014:Java队列08——数组实现的双端队列ArrayDeque

ArrayDeque是基于数组实现的无界双端队列。ArrayDeque中的数组没有容量限制,它们能根据需要增长以支持使用。需要注意的是ArrayDeque不是线程安全的,因此在没有外部同步的情况下,它们不支持多线程并发访问。

ArrayDeque用作栈时可能比Stack更快,用作队列时可能比LinkedList更快。

ArrayDeque禁止插入空元素。

ArrayDeque及其迭代器实现了Collection和Iterator接口的所有可选方法。

ArrayDeque是Java Collections Framework的一个成员。

1.   ArrayDeque的声明

ArrayDeque的接口和继承关系如下

publicclass ArrayDeque<E> extends AbstractCollection<E>

     implements Deque<E>, Cloneable, Serializable

  …

}

完整的接口继承关系如下图所示。

image.gif编辑

从上述代码可以看出,ArrayDeque既实现了java.util.Deque<E> 、java.lang.Cloneable、java.io.Serializable接口,又继承了java.util.AbstractCollection<E>。

2.   ArrayDeque的成员变量和构造函数

以下是ArrayDeque的构造函数和成员变量。

// 元素数组

   transient Object[] elements;

// 队列头索引

   transientint head;

// 队列尾索引

   transientint tail;

// 数组最大容量

   privatestaticfinalintMAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

public ArrayDeque() {

       elements = new Object[16 + 1];

   }

   public ArrayDeque(int numElements) {

       elements =

           new Object[(numElements < 1) ? 1 :

                      (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :

                      numElements + 1];

   }

   public ArrayDeque(Collection<? extends E> c) {

       this(c.size());

       copyElements(c);

}

从上述代码可以看出,构造函数有3种。构造函数中的参数含义如下

l  numElements用于设置队列中内部数组的元素总数。如果没有指定,则会使用默认元素总数16。需要注意的是,实际数组的大小,是numElements+1。

l  c用于设置最初包含给定集合的元素,按集合迭代器的遍历顺序添加

类成员elements是一个数组,用于存储队列中的元素。head和tail分别表示队头索引和队尾索引。

思考:为什么实际数组的实际数组的大小,是numElements+1?

3.   ArrayDeque的核心方法

以下对ArrayDeque常用核心方法的实现原理进行解释。

3.1.     addLast(e)

执行addLast(e)方法后有两种结果

l  队列未达到容量时,直接插入,没有返回值

l  队列达到容量时,先扩容,再插入,没有返回值

ArrayDeque的addLast(e)方法源码如下:

   publicvoid addLast(E e) {

       if (e == null)  // 判空

           thrownew NullPointerException();

       final Object[] es = elements;

       es[tail] = e;

       if (head == (tail = inc(tail, es.length)))

           grow(1);  // 扩容

   }

从上面代码可以看出,addLast(e)方法会先进行判空处理,而后再将元素插入。如果插入前判断容量不够,则会执行grow()方法进行扩容。

grow()方法源码如下:

privatevoid grow(int needed) {

       // overflow-conscious code

       finalint oldCapacity = elements.length;

       int newCapacity;

       // Double capacity if small; else grow by 50%

       int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);

       if (jump < needed

           || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)

           newCapacity = newCapacity(needed, jump);

       final Object[] es = elements = Arrays.copyOf(elements, newCapacity);

       // Exceptionally, here tail == head needs to be disambiguated

       if (tail < head || (tail == head && es[head] != null)) {

           // wrap around; slide first leg forward to end of array

           int newSpace = newCapacity - oldCapacity;

           System.arraycopy(es, head,

                            es, head + newSpace,

                            oldCapacity - head);

           for (int i = head, to = (head += newSpace); i < to; i++)

               es[i] = null;

       }

   }

   /** Capacity calculation for edge conditions, especially overflow. */

   privateint newCapacity(int needed, int jump) {

       finalint oldCapacity = elements.length, minCapacity;

       if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {

           if (minCapacity < 0)

               thrownew IllegalStateException("Sorry, deque too big");

           return Integer.MAX_VALUE;

       }

       if (needed > jump)

           return minCapacity;

       return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)

           ? oldCapacity + jump

           : MAX_ARRAY_SIZE;

   }

3.2.     offerLast(e)

执行offerLast(e)方法后有两种结果

l  队列未达到容量时,返回 true

l  队列达到容量时,先扩容,再返回 true

ArrayDeque的offerLast(e)方法源码如下:

publicboolean offerLast(E e) {

       addLast(e);

       returntrue;

   }

从上面代码可以看出,执行offerLast(e)方法直接调用的是addLast(e)

3.3.     addLast(e)

执行addFirst(e)方法后有两种结果

l  队列未达到容量时,直接插入,没有返回值

l  队列达到容量时,先扩容,再插入,没有返回值

ArrayDeque的addFirst(e)方法源码如下:

   publicvoid addFirst(E e) {

       if (e == null)  // 判空

           thrownew NullPointerException();

       final Object[] es = elements;

       es[head = dec(head, es.length)] = e;

       if (head == tail)

           grow(1);  // 扩容

   }

从上面代码可以看出,addFirst(e)方法会先进行判空处理,而后再将元素插入。如果插入前判断容量不够,则会执行grow()方法进行扩容。

3.4.     pollFirst()

执行pollFirst()方法后有两种结果:

l  队列不为空时,返回队首值并移除

l  队列为空时,返回 null

ArrayDeque的pollFirst()方法源码如下:

public E pollFirst() {

       final Object[] es;

       finalint h;

       E e = elementAt(es = elements, h = head);

       if (e != null) {

           es[h] = null;

           head = inc(h, es.length);

       }

       return e;

}

从上面代码可以看出,执行pollFirst()方法时,分为以下几个步骤:

l  先取队列的队首元素。

l  如果队首元素不存在,直接返回null。

l  如果队首元素存在,则返回该元素同时移除元素。

3.5.     removeFirst()

执行removeFirst()方法后有两种结果:

l  队列不为空时,返回队首值并移除

l  队列为空时,抛出异常

ArrayDeque的removeFirst()方法源码如下:

public E removeFirst() {

       E e = pollFirst();

       if (e == null)

           thrownew NoSuchElementException();

       return e;

}

从上面代码可以看出,removeFirst()方法直接调用了pollFirst()方法。如果pollFirst()方法返回结果为null,则抛出NoSuchElementException异常。

pollFirst()方法此处不再赘述。

3.6.     peekFirst()

执行peekFirst()方法后有两种结果:

l  队列不为空时,返回队首值但不移除

l  队列为空时,返回null

peekFirst()方法源码如下:

public E peekFirst() {

       returnelementAt(elements, head);

}

staticfinal <E> E elementAt(Object[] es, int i) {

       return (E) es[i];

}

从上面代码可以看出,peekFirst()方法比较简单,直接就是获取了数组里面的索引为head的元素。

3.7.     getFirst()

执行getFirst()方法后有两种结果:

l  队列不为空时,返回队首值但不移除

l  队列为空时,抛出异常

getFirst()方法源码如下:

public E getFirst() {

       E e = elementAt(elements, head);

       if (e == null)

           thrownew NoSuchElementException();

       return e;

}

从上面代码可以看出,执行getFirst()方法时,先是获取了数组里面的索引为head的元素。如果结果是null,则抛出NoSuchElementException异常。

4.   ArrayDeque的单元测试

ArrayDeque的单元测试如下:

package com.waylau.java.demo.datastructure;

importstatic org.junit.jupiter.api.Assertions.assertEquals;

importstatic org.junit.jupiter.api.Assertions.assertNull;

importstatic org.junit.jupiter.api.Assertions.assertThrows;

importstatic org.junit.jupiter.api.Assertions.assertTrue;

import java.util.ArrayDeque;

import java.util.Deque;

import java.util.NoSuchElementException;

import org.junit.jupiter.api.Test;

/**

* ArrayDeque Tests

*

* @since 1.0.0 2020年5月3日

* @author <a href="https://waylau.com">Way Lau</a>

*/

class ArrayDequeTests {

   @Test

   void testAddLast() {

       // 初始化队列

       Deque<String> queue = new ArrayDeque<String>(3);

       // 测试队列未满时,直接插入没有返回值;

       queue.addLast("Java");

       // 测试队列满则扩容

       queue.addLast("C");

       queue.addLast("Python");

       queue.addLast("C++"); // 扩容

   }

   @Test

   void testOfferLast() {

       // 初始化队列

       Deque<String> queue = new ArrayDeque<String>(3);

       // 测试队列未满时,返回 true

       boolean resultNotFull = queue.offerLast("Java");

       assertTrue(resultNotFull);

       // 测试队列达到容量时,会自动扩容

       queue.offerLast("C");

       queue.offerLast("Python");

       boolean resultFull = queue.offerLast("C++"); // 扩容

       assertTrue(resultFull);

   }

   @Test

   void testAddFirst() {

       // 初始化队列

       Deque<String> queue = new ArrayDeque<String>(3);

       // 测试队列未满时,直接插入没有返回值;

       queue.addFirst("Java");

       // 测试队列满则扩容

       queue.addFirst("C");

       queue.addFirst("Python");

       queue.addFirst("C++"); // 扩容

   }

   @Test

   void testPollFirst() throws InterruptedException {

       // 初始化队列

       Deque<String> queue = new ArrayDeque<String>(3);

       // 测试队列为空时,返回 null

       String resultEmpty = queue.pollFirst();

       assertNull(resultEmpty);

       // 测试队列不为空时,返回队首值并移除

       queue.addLast("Java");

       queue.addLast("C");

       queue.addLast("Python");

       String resultNotEmpty = queue.pollFirst();

       assertEquals("Java", resultNotEmpty);

   }

   @Test

   void testRemoveFirst() throws InterruptedException {

       // 初始化队列

       Deque<String> queue = new ArrayDeque<String>(3);

       // 测试队列为空时,抛出异常

       Throwable excpetion = assertThrows(NoSuchElementException.class, () -> {

           queue.removeFirst();// 抛异常

       });

       assertEquals(null, excpetion.getMessage());

       // 测试队列不为空时,返回队首值并移除

       queue.addLast("Java");

       queue.addLast("C");

       queue.addLast("Python");

       String resultNotEmpty = queue.removeFirst();

       assertEquals("Java", resultNotEmpty);

   }

   @Test

   void testPeekFirst() throws InterruptedException {

       // 初始化队列

       Deque<String> queue = new ArrayDeque<String>(3);

       // 测试队列不为空时,返回队首值并但不移除

       queue.add("Java");

       queue.add("C");

       queue.add("Python");

       String resultNotEmpty = queue.peekFirst();

       assertEquals("Java", resultNotEmpty);

       resultNotEmpty = queue.peekFirst();

       assertEquals("Java", resultNotEmpty);

       resultNotEmpty = queue.peekFirst();

       assertEquals("Java", resultNotEmpty);

       // 测试队列为空时,返回null

       queue.clear();

       String resultEmpty = queue.peek();

       assertNull(resultEmpty);

   }

   @Test

   void testGetFirst() throws InterruptedException {

       // 初始化队列

       Deque<String> queue = new ArrayDeque<String>(3);

       // 测试队列不为空时,返回队首值并但不移除

       queue.add("Java");

       queue.add("C");

       queue.add("Python");

       String resultNotEmpty = queue.getFirst();

       assertEquals("Java", resultNotEmpty);

       resultNotEmpty = queue.getFirst();

       assertEquals("Java", resultNotEmpty);

       resultNotEmpty = queue.getFirst();

       assertEquals("Java", resultNotEmpty);

       // 测试队列为空时,抛出异常

       queue.clear();

       Throwable excpetion = assertThrows(NoSuchElementException.class, () -> {

           queue.getFirst();// 抛异常

       });

       assertEquals(null, excpetion.getMessage());

   }

}

5.    ArrayDeque的应用案例:工作窃取

双端队列的一个经典使用场景就是工作窃取。ForkJoinPool线程池就利用了双端队列支持工作窃取。

线程池中每个线程都有一个互不影响的任务队列(双端队列),线程每次都从自己的任务队列的队头中取出一个任务来运行;如果某个线程对应的队列已空并且处于空闲状态,而其他线程的队列中还有任务需要处理但是该线程处于工作状态,那么空闲的线程可以从其他线程的队列的队尾取一个任务来帮忙运行 —— 感觉就像是空闲的线程去偷人家的任务来运行一样,所以叫 “工作窃取”。这是保证LB的一个重要思路。

6.   参考引用

本系列归档至《Java 数据结构及算法实战》:https://github.com/waylau/java-data-structures-and-algorithms-in-action

《数据结构和算法基础(Java 语言实现)》(柳伟卫著,北京大学出版社出版):https://item.jd.com/13014179.html

 

目录
相关文章
|
16天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
50 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
8天前
|
存储 Java 开发者
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
28 2
|
14天前
|
存储 消息中间件 安全
JUC组件实战:实现RRPC(Java与硬件通过MQTT的同步通信)
【10月更文挑战第9天】本文介绍了如何利用JUC组件实现Java服务与硬件通过MQTT的同步通信(RRPC)。通过模拟MQTT通信流程,使用`LinkedBlockingQueue`作为消息队列,详细讲解了消息发送、接收及响应的同步处理机制,包括任务超时处理和内存泄漏的预防措施。文中还提供了具体的类设计和方法实现,帮助理解同步通信的内部工作原理。
JUC组件实战:实现RRPC(Java与硬件通过MQTT的同步通信)
|
20天前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
18 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
20天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
18 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
19小时前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
13天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
29 4
|
11天前
|
开发框架 Java 程序员
揭开Java反射的神秘面纱:从原理到实战应用!
本文介绍了Java反射的基本概念、原理及应用场景。反射允许程序在运行时动态获取类的信息并操作其属性和方法,广泛应用于开发框架、动态代理和自定义注解等领域。通过反射,可以实现更灵活的代码设计,但也需注意其性能开销。
29 1
|
20天前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
14 0
数据结构与算法学习十四:常用排序算法总结和对比
|
20天前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
19 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列