【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

 

目录
相关文章
|
15天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
24天前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
41 1
|
26天前
|
存储 Java
告别混乱!用Java Map优雅管理你的数据结构
【10月更文挑战第17天】在软件开发中,随着项目复杂度增加,数据结构的组织和管理至关重要。Java中的Map接口提供了一种优雅的解决方案,帮助我们高效、清晰地管理数据。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,有效提升了代码质量和维护性。
80 2
|
26天前
|
存储 Java 开发者
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
57 2
|
9天前
|
缓存 算法 Java
本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制
在现代软件开发中,性能优化至关重要。本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制。通过调整垃圾回收器参数、优化堆大小与布局、使用对象池和缓存技术,开发者可显著提升应用性能和稳定性。
30 6
|
15天前
|
存储 Java 索引
Java中的数据结构:ArrayList和LinkedList的比较
【10月更文挑战第28天】在Java编程世界中,数据结构是构建复杂程序的基石。本文将深入探讨两种常用的数据结构:ArrayList和LinkedList,通过直观的比喻和实例分析,揭示它们各自的优势与局限,帮助你在面对不同的编程挑战时做出明智的选择。
|
18天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
23天前
|
存储 算法 Java
Java 中常用的数据结构
【10月更文挑战第20天】这些数据结构在 Java 编程中都有着广泛的应用,掌握它们的特点和用法对于提高编程能力和解决实际问题非常重要。
24 6
|
24天前
|
存储 Java 开发者
Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中,随着项目复杂度的增加,数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,帮助开发者告别混乱,提升代码质量。
26 1
|
1月前
|
存储 算法 Java
Java常用的数据结构
【10月更文挑战第3天】 在 Java 中,常用的数据结构包括数组、链表、栈、队列、树、图、哈希表和集合。每种数据结构都有其特点和适用场景,如数组适用于快速访问,链表适合频繁插入和删除,栈用于实现后进先出,队列用于先进先出,树和图用于复杂关系的表示和查找,哈希表提供高效的查找性能,集合用于存储不重复的元素。合理选择和组合使用这些数据结构,可以显著提升程序的性能和效率。