java多线程并发之旅-16-双端队列之 ArrayDeque

2023-10-22 05:32
文章标签 java 16 并发 多线程 队列 双端 之旅 arraydeque

本文主要是介绍java多线程并发之旅-16-双端队列之 ArrayDeque，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

ArrayDeque

ArrayDeque不是线程安全的。

ArrayDeque不可以存取null元素，因为系统根据某个位置是否为null来判断元素的存在。

当作为栈使用时，性能比Stack好；当作为队列使用时，性能比LinkedList好。

特性

  • 无容量大小限制，容量按需增长；

  • 非线程安全队列，无同步策略，不支持多线程安全访问；

  • 当用作栈时，性能优于Stack，当用于队列时，性能优于LinkedList

  • 两端都可以操作

  • 具有fail-fast特征

  • 不能存储null

  • 支持双向迭代器遍历

常用方法

1.添加元素

addFirst(E e)在数组前面添加元素

addLast(E e)在数组后面添加元素

offerFirst(E e) 在数组前面添加元素，并返回是否添加成功

offerLast(E e) 在数组后天添加元素，并返回是否添加成功

2.删除元素

removeFirst() 删除第一个元素，并返回删除元素的值,如果元素为null，将抛出异常

pollFirst() 删除第一个元素，并返回删除元素的值，如果元素为null，将返回null

removeLast() 删除最后一个元素，并返回删除元素的值，如果为null，将抛出异常

pollLast() 删除最后一个元素，并返回删除元素的值，如果为null，将返回null

removeFirstOccurrence(Object o) 删除第一次出现的指定元素

removeLastOccurrence(Object o) 删除最后一次出现的指定元素

3.获取元素

getFirst() 获取第一个元素,如果没有将抛出异常

getLast() 获取最后一个元素，如果没有将抛出异常

4.队列操作

add(E e) 在队列尾部添加一个元素

offer(E e) 在队列尾部添加一个元素，并返回是否成功

remove() 删除队列中第一个元素，并返回该元素的值，如果元素为null，将抛出异常(其实底层调用的是removeFirst())

poll() 删除队列中第一个元素，并返回该元素的值,如果元素为null，将返回null(其实调用的是pollFirst())

element() 获取第一个元素，如果没有将抛出异常

peek() 获取第一个元素，如果返回null

5.栈操作

push(E e) 栈顶添加一个元素

pop(E e) 移除栈顶元素,如果栈顶没有元素将抛出异常

6.其他

size() 获取队列中元素个数

isEmpty() 判断队列是否为空

iterator() 迭代器，从前向后迭代

descendingIterator() 迭代器，从后向前迭代

contain(Object o) 判断队列中是否存在该元素

toArray() 转成数组

clear() 清空队列

clone() 克隆(复制)一个新的队列

使用入门测试

public class DequeTest {public static void main(String[] args){// 初始化容量为4ArrayDeque<String> arrayDeque = new ArrayDeque<>(4);//添加元素arrayDeque.add("A");arrayDeque.add("B");arrayDeque.add("C");arrayDeque.add("D");arrayDeque.add("E");arrayDeque.add("F");arrayDeque.add("G");arrayDeque.add("H");arrayDeque.add("I");System.out.println(arrayDeque);// 获取元素String a = arrayDeque.getFirst();String a1 = arrayDeque.pop();String b = arrayDeque.element();String b1 = arrayDeque.removeFirst();String c = arrayDeque.peek();String c1 = arrayDeque.poll();String d = arrayDeque.pollFirst();String i = arrayDeque.pollLast();String e = arrayDeque.peekFirst();String h = arrayDeque.peekLast();String h1 = arrayDeque.removeLast();System.out.printf("a = %s, a1 = %s, b = %s, b1 = %s, c = %s, c1 = %s, d = %s, i = %s, e = %s, h = %s, h1 = %s", a,a1,b,b1,c,c1,d,i,e,h,h1);System.out.println();// 添加元素arrayDeque.push(e);arrayDeque.add(h);arrayDeque.offer(d);arrayDeque.offerFirst(i);arrayDeque.offerLast(c);arrayDeque.offerLast(h);arrayDeque.offerLast(c);arrayDeque.offerLast(h);arrayDeque.offerLast(i);arrayDeque.offerLast(c);System.out.println(arrayDeque);// 移除第一次出现的CarrayDeque.removeFirstOccurrence(c);System.out.println(arrayDeque);// 移除最后一次出现的CarrayDeque.removeLastOccurrence(c);System.out.println(arrayDeque);}
}
  • 输出日志
[A, B, C, D, E, F, G, H, I]
a = A, a1 = A, b = B, b1 = B, c = C, c1 = C, d = D, i = I, e = E, h = H, h1 = H
[I, E, E, F, G, H, D, C, H, C, H, I, C]
[I, E, E, F, G, H, D, H, C, H, I, C]
[I, E, E, F, G, H, D, H, C, H, I]

卡拉兹(Callatz)猜想

题目

对任何一个自然数n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把(3n+1)砍掉一半。这样一直反复砍下去，最后一定在某一步得到n=1。当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对n=3进行验证的时候，我们需要计算3、5、8、4、2、1，则当我们对n=5、8、4、2进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这4个数已经在验证3的时候遇到过了，我们称5、8、4、2是被3“覆盖”的数。我们称一个数列中的某个数n为“关键数”，如果n不能被数列中的其他数字所覆盖。

现在给定一系列待验证的数字，我们只需要验证其中的几个关键数，就可以不必再重复验证余下的数字。你的任务就是找出这些关键数字，并按从大到小的顺序输出它们。

输入格式：每个测试输入包含1个测试用例，第1行给出一个正整数K(<100)，第2行给出K个互不相同的待验证的正整数n(1<n<=100)的值，数字间用空格隔开。

输出格式：每个测试用例的输出占一行，按从大到小的顺序输出关键数字。数字间用1个空格隔开，但一行中最后一个数字后没有空格。

输入样例：

6
3 5 6 7 8 11

输出样例：

7 6

使用 Deque 来编码

import java.util.ArrayDeque; 
import java.util.ArrayList; 
import java.util.Deque; 
import java.util.List; 
import java.util.Queue; 
import java.util.Scanner; 
import java.util.SortedSet; 
import java.util.TreeSet; public class PAT1005 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int numSize=scanner.nextInt(); ArrayDeque<Integer> newArrayDeque=new ArrayDeque<Integer>(); ArrayDeque<Integer> closeArrayDeque=new ArrayDeque<Integer>(); int i; while (scanner.hasNext()) {           //读取键盘输入值 for (i = 0; i < numSize; i++) { newArrayDeque.add(scanner.nextInt()); } if (i>=numSize) { break; } } int temp; for (Integer integer : newArrayDeque) {    //将非关键数存入closeArrayDeque中 temp=integer;  while (temp!=1) { if (temp%2==0) { temp=temp/2; if (newArrayDeque.contains(temp)) { closeArrayDeque.add(temp); } }else { temp=(temp*3+1)/2; if (newArrayDeque.contains(temp)) { closeArrayDeque.add(temp); } } } } SortedSet<Integer> sortedSet=new TreeSet<Integer>(); //sortedSet用于存放关键数 for (Integer integer : newArrayDeque) { if (!closeArrayDeque.contains(integer)) { sortedSet.add(integer); } } int[] leftInt=new int[sortedSet.size()]; int j=sortedSet.size()-1; for (Integer integer : sortedSet) { leftInt[j]=integer; j--; } for (int j2 = 0; j2 < leftInt.length; j2++) {    //按照从大到小的顺序输出关键数 if (j2==leftInt.length-1) { System.out.println(leftInt[j2]); }else { System.out.print(leftInt[j2]+" "); } } } 
}

源码分析

jdk 版本: 1.8.0_191

接口

public class ArrayDeque<E> extends AbstractCollection<E>implements Deque<E>, Cloneable, Serializable

基础属性

    /*** The array in which the elements of the deque are stored.* The capacity of the deque is the length of this array, which is* always a power of two. The array is never allowed to become* full, except transiently within an addX method where it is* resized (see doubleCapacity) immediately upon becoming full,* thus avoiding head and tail wrapping around to equal each* other.  We also guarantee that all array cells not holding* deque elements are always null.*/transient Object[] elements; // non-private to simplify nested class access/*** The index of the element at the head of the deque (which is the* element that would be removed by remove() or pop()); or an* arbitrary number equal to tail if the deque is empty.*/transient int head;/*** The index at which the next element would be added to the tail* of the deque (via addLast(E), add(E), or push(E)).*/transient int tail;/*** The minimum capacity that we'll use for a newly created deque.* Must be a power of 2.*/private static final int MIN_INITIAL_CAPACITY = 8;

elements 用来存放元素对象，MIN_INITIAL_CAPACITY 是容器的最小初始值。

head、tail 分别是头尾指针。

构造器

/** * Constructs an empty array deque with an initial capacity* sufficient to hold 16 elements.*/
public ArrayDeque() {elements = new Object[16];
}/*** Constructs an empty array deque with an initial capacity* sufficient to hold the specified number of elements.** @param numElements  lower bound on initial capacity of the deque*/
public ArrayDeque(int numElements) {allocateElements(numElements);
}/*** Constructs a deque containing the elements of the specified* collection, in the order they are returned by the collection's* iterator.  (The first element returned by the collection's* iterator becomes the first element, or <i>front</i> of the* deque.)** @param c the collection whose elements are to be placed into the deque* @throws NullPointerException if the specified collection is null*/
public ArrayDeque(Collection<? extends E> c) {allocateElements(c.size());addAll(c);
}

allocateElements() 方法

/*** Allocates empty array to hold the given number of elements.** @param numElements  the number of elements to hold*/
private void allocateElements(int numElements) {elements = new Object[calculateSize(numElements)];
}
  • calculateSize()
private static int calculateSize(int numElements) {int initialCapacity = MIN_INITIAL_CAPACITY;// Find the best power of two to hold elements.// Tests "<=" because arrays aren't kept full.if (numElements >= initialCapacity) {initialCapacity = numElements;initialCapacity |= (initialCapacity >>>  1);initialCapacity |= (initialCapacity >>>  2);initialCapacity |= (initialCapacity >>>  4);initialCapacity |= (initialCapacity >>>  8);initialCapacity |= (initialCapacity >>> 16);initialCapacity++;if (initialCapacity < 0)   // Too many elements, must back offinitialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements}return initialCapacity;
}

位运算用的真熟练。参见 java 位运算

在这系列操作中，其他位只是配角，我们只需要关注第一个不为0的位即可，假设其为第n位，先右移一位然后进行或操作，得到的结果，第n位和第n-1位肯定为1，这样就有两个位为1了，然后进行右移两位，再进行或操作，那么第n位到第n-3位一定都为1，然后右移4位，依次类推。int为32位，因此，最后只需要移动16位即可。1+2+4+8+16 = 31，所以经过这一波操作，原数字对应的二进制，操作得到的结果将是从其第一个不为0的位开始，往后的位均为1。

元素的插入

    /*** Inserts the specified element at the front of this deque.** @param e the element to add* @throws NullPointerException if the specified element is null*/public void addFirst(E e) {if (e == null)throw new NullPointerException();elements[head = (head - 1) & (elements.length - 1)] = e;if (head == tail)doubleCapacity();}/*** Inserts the specified element at the end of this deque.** <p>This method is equivalent to {@link #add}.** @param e the element to add* @throws NullPointerException if the specified element is null*/public void addLast(E e) {if (e == null)throw new NullPointerException();elements[tail] = e;if ( (tail = (tail + 1) & (elements.length - 1)) == head)doubleCapacity();}/*** Inserts the specified element at the front of this deque.** @param e the element to add* @return {@code true} (as specified by {@link Deque#offerFirst})* @throws NullPointerException if the specified element is null*/public boolean offerFirst(E e) {addFirst(e);return true;}

元素的定位

elements[head = (head - 1) & (elements.length - 1)] = e 位运算定位元素。

因为列表的大小在申请时，是 2 的次幂。这里可以使用这种高性能的运算方式获取元素的位置。

扩容 doubleCapacity

因为elements.length是2的幂次方，所以减一后就变成了掩码，tail如果记录的是最后一个位置，即 elements.length - 1，tail + 1 则等于elements.length，与 elements.length - 1 做与操作后，就变成了0，嗯，没错，这样就变成了一个循环数组，如果tail与head相等，则表示没有剩余空间可以存放更多元素了，则调用doubleCapacity进行扩容：

当队列满的时候进行扩容。

扩容条件：if ( (tail = (tail + 1) & (elements.length - 1)) == head)

扩容大小：简单粗暴，直接翻倍。

扩容方式：创建一个双倍大小的数组，元素直接拷贝过来(分别放在首尾)。

/*** Doubles the capacity of this deque.  Call only when full, i.e.,* when head and tail have wrapped around to become equal.*/
private void doubleCapacity() {assert head == tail;int p = head;int n = elements.length;int r = n - p; // number of elements to the right of pint newCapacity = n << 1;if (newCapacity < 0)throw new IllegalStateException("Sorry, deque too big");Object[] a = new Object[newCapacity];System.arraycopy(elements, p, a, 0, r);System.arraycopy(elements, 0, a, r, p);elements = a;head = 0;tail = n;
}

删除元素

也是通过位运算获取指定位置的元素。

然后将元素置为 null。

如果元素不存在，则直接抛出异常：NoSuchElementException

    /*** @throws NoSuchElementException {@inheritDoc}*/public E removeFirst() {E x = pollFirst();if (x == null)throw new NoSuchElementException();return x;}/*** @throws NoSuchElementException {@inheritDoc}*/public E removeLast() {E x = pollLast();if (x == null)throw new NoSuchElementException();return x;}public E pollFirst() {int h = head;@SuppressWarnings("unchecked")E result = (E) elements[h];// Element is null if deque emptyif (result == null)return null;elements[h] = null;     // Must null out slothead = (h + 1) & (elements.length - 1);return result;}public E pollLast() {int t = (tail - 1) & (elements.length - 1);@SuppressWarnings("unchecked")E result = (E) elements[t];if (result == null)return null;elements[t] = null;tail = t;return result;}

获取元素

获取元素相对比较简单。

因为底层的存储结构是数组，直接指定元素位置获取即可。

如果从队列后面获取，则通过 (tail - 1) & (elements.length - 1) 获取元素的下标。

元素不存在：抛出异常 NoSuchElementException

    /*** @throws NoSuchElementException {@inheritDoc}*/public E getFirst() {@SuppressWarnings("unchecked")E result = (E) elements[head];if (result == null)throw new NoSuchElementException();return result;}/*** @throws NoSuchElementException {@inheritDoc}*/public E getLast() {@SuppressWarnings("unchecked")E result = (E) elements[(tail - 1) & (elements.length - 1)];if (result == null)throw new NoSuchElementException();return result;}@SuppressWarnings("unchecked")public E peekFirst() {// elements[head] is null if deque emptyreturn (E) elements[head];}@SuppressWarnings("unchecked")public E peekLast() {return (E) elements[(tail - 1) & (elements.length - 1)];}

后续学习

这个不是线程安全的类。

如果我们希望在多线程中使用，该怎么办呢？

见下一节：LinkedBlockingDeque

参考资料

ArrayDeque类的使用详解

【Java入门提高篇】Day32 Java容器类详解（十四）ArrayDeque详解

Java ArrayDeque使用方法详解

目录

java多线程并发之旅-01-并发概览

这篇关于java多线程并发之旅-16-双端队列之 ArrayDeque的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/259371。

相关文章

SpringBoot 获取请求参数的常用注解及用法

SpringBoot 获取请求参数的常用注解及用法

《SpringBoot获取请求参数的常用注解及用法》SpringBoot通过@RequestParam、@PathVariable等注解支持从HTTP请求中获取参数,涵盖查询、路径、请求体、头、C... 目录SpringBoot 提供了多种注解来方便地从 HTTP 请求中获取参数以下是主要的注解及其用法：1
阅读更多...
HTTP 与 SpringBoot 参数提交与接收协议方式

HTTP 与 SpringBoot 参数提交与接收协议方式

《HTTP与SpringBoot参数提交与接收协议方式》HTTP参数提交方式包括URL查询、表单、JSON/XML、路径变量、头部、Cookie、GraphQL、WebSocket和SSE,依据... 目录HTTP 协议支持多种参数提交方式，主要取决于请求方法(Method)和内容类型(Content-Ty
阅读更多...
深度解析Java @Serial 注解及常见错误案例

深度解析Java @Serial 注解及常见错误案例

《深度解析Java@Serial注解及常见错误案例》Java14引入@Serial注解,用于编译时校验序列化成员,替代传统方式解决运行时错误,适用于Serializable类的方法/字段,需注意签... 目录Java @Serial 注解深度解析1. 注解本质2. 核心作用(1) 主要用途(2) 适用位置3
阅读更多...
深入浅出Spring中的@Autowired自动注入的工作原理及实践应用

深入浅出Spring中的@Autowired自动注入的工作原理及实践应用

《深入浅出Spring中的@Autowired自动注入的工作原理及实践应用》在Spring框架的学习旅程中,@Autowired无疑是一个高频出现却又让初学者头疼的注解,它看似简单,却蕴含着Sprin... 目录深入浅出Spring中的@Autowired：自动注入的奥秘什么是依赖注入？@Autowired
阅读更多...
Spring 依赖注入与循环依赖总结

Spring 依赖注入与循环依赖总结

《Spring依赖注入与循环依赖总结》这篇文章给大家介绍Spring依赖注入与循环依赖总结篇,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. Spring 三级缓存解决循环依赖1. 创建UserService原始对象2. 将原始对象包装成工
阅读更多...
Java中如何正确的停掉线程

Java中如何正确的停掉线程

《Java中如何正确的停掉线程》Java通过interrupt()通知线程停止而非强制,确保线程自主处理中断,避免数据损坏,线程池的shutdown()等待任务完成,shutdownNow()强制中断... 目录为什么不强制停止为什么 Java 不提供强制停止线程的能力呢？如何用interrupt停止线程s
阅读更多...
SpringBoot请求参数传递与接收示例详解

SpringBoot请求参数传递与接收示例详解

《SpringBoot请求参数传递与接收示例详解》本文给大家介绍SpringBoot请求参数传递与接收示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录I. 基础参数传递i.查询参数（Query Parameters）ii.路径参数（Path Va
阅读更多...
SpringBoot路径映射配置的实现步骤

SpringBoot路径映射配置的实现步骤

《SpringBoot路径映射配置的实现步骤》本文介绍了如何在SpringBoot项目中配置路径映射,使得除static目录外的资源可被访问,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一... 目录SpringBoot路径映射补：springboot 配置虚拟路径映射 @RequestMapp
阅读更多...
Java MCP 的鉴权深度解析

Java MCP 的鉴权深度解析

《JavaMCP的鉴权深度解析》文章介绍JavaMCP鉴权的实现方式,指出客户端可通过queryString、header或env传递鉴权信息,服务器端支持工具单独鉴权、过滤器集中鉴权及启动时鉴权... 目录一、MCP Client 侧（负责传递，比较简单）（1）常见的 mcpServers json 配置
阅读更多...
GSON框架下将百度天气JSON数据转JavaBean

GSON框架下将百度天气JSON数据转JavaBean

《GSON框架下将百度天气JSON数据转JavaBean》这篇文章主要为大家详细介绍了如何在GSON框架下实现将百度天气JSON数据转JavaBean,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录前言一、百度天气jsON1、请求参数2、返回参数3、属性映射二、GSON属性映射实战1、类对象映
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2