时间:2021-05-19
问题
(1)什么是双端队列?
(2)ArrayDeque是怎么实现双端队列的?
(3)ArrayDeque是线程安全的吗?
(4)ArrayDeque是有界的吗?
简介
双端队列是一种特殊的队列,它的两端都可以进出元素,故而得名双端队列。
ArrayDeque是一种以数组方式实现的双端队列,它是非线程安全的。
继承体系
通过继承体系可以看,ArrayDeque实现了Deque接口,Deque接口继承自Queue接口,它是对Queue的一种增强。
public interface Deque<E> extends Queue<E> { // 添加元素到队列头 void addFirst(E e); // 添加元素到队列尾 void addLast(E e); // 添加元素到队列头 boolean offerFirst(E e); // 添加元素到队列尾 boolean offerLast(E e); // 从队列头移除元素 E removeFirst(); // 从队列尾移除元素 E removeLast(); // 从队列头移除元素 E pollFirst(); // 从队列尾移除元素 E pollLast(); // 查看队列头元素 E getFirst(); // 查看队列尾元素 E getLast(); // 查看队列头元素 E peekFirst(); // 查看队列尾元素 E peekLast(); // 从队列头向后遍历移除指定元素 boolean removeFirstOccurrence(Object o); // 从队列尾向前遍历移除指定元素 boolean removeLastOccurrence(Object o);// *** 队列中的方法 *** // 添加元素,等于addLast(e) boolean add(E e); // 添加元素,等于offerLast(e) boolean offer(E e); // 移除元素,等于removeFirst() E remove(); // 移除元素,等于pollFirst() E poll(); // 查看元素,等于getFirst() E element(); // 查看元素,等于peekFirst() E peek();// *** 栈方法 ***// 入栈,等于addFirst(e) void push(E e); // 出栈,等于removeFirst() E pop();// *** Collection中的方法 *** // 删除指定元素,等于removeFirstOccurrence(o) boolean remove(Object o); // 检查是否包含某个元素 boolean contains(Object o); // 元素个数 public int size(); // 迭代器 Iterator<E> iterator(); // 反向迭代器 Iterator<E> descendingIterator();}Deque中新增了以下几类方法:
(1)*First,表示从队列头操作元素;
(2)*Last,表示从队列尾操作元素;
(3)push(e),pop(),以栈的方式操作元素的方法;
源码分析
主要属性
从属性我们可以看到,ArrayDeque使用数组存储元素,并使用头尾指针标识队列的头和尾,其最小容量是8。
主要构造方法
通过构造方法,我们知道默认初始容量是16,最小容量是8。
入队
入队有很多方法,我们这里主要分析两个,addFirst(e)和addLast(e)。
// 从队列头入队public void addFirst(E e) { // 不允许null元素 if (e == null) throw new NullPointerException(); // 将head指针减1并与数组长度减1取模 // 这是为了防止数组到头了边界溢出 // 如果到头了就从尾再向前 // 相当于循环利用数组 elements[head = (head - 1) & (elements.length - 1)] = e; // 如果头尾挨在一起了,就扩容 // 扩容规则也很简单,直接两倍 if (head == tail) doubleCapacity();}// 从队列尾入队public void addLast(E e) { // 不允许null元素 if (e == null) throw new NullPointerException(); // 在尾指针的位置放入元素 // 可以看到tail指针指向的是队列最后一个元素的下一个位置 elements[tail] = e; // tail指针加1,如果到数组尾了就从头开始 if ( (tail = (tail + 1) & (elements.length - 1)) == head) doubleCapacity();}(1)入队有两种方式,从队列头或者从队列尾;
(2)如果容量不够了,直接扩大为两倍;
(3)通过取模的方式让头尾指针在数组范围内循环;
(4)x & (len - 1) = x % len,使用&的方式更快;
扩容
扩容这里迁移元素可能有点绕,请看下面这张图来理解。
出队
出队同样有很多方法,我们主要看两个,pollFirst()和pollLast()。
// 从队列头出队public E pollFirst() { int h = head; @SuppressWarnings("unchecked") // 取队列头元素 E result = (E) elements[h]; // 如果队列为空,就返回null if (result == null) return null; // 将队列头置为空 elements[h] = null; // Must null out slot // 队列头指针右移一位 head = (h + 1) & (elements.length - 1); // 返回取得的元素 return result;}// 从队列尾出队public E pollLast() { // 尾指针左移一位 int t = (tail - 1) & (elements.length - 1); @SuppressWarnings("unchecked") // 取当前尾指针处元素 E result = (E) elements[t]; // 如果队列为空返回null if (result == null) return null; // 将当前尾指针处置为空 elements[t] = null; // tail指向新的尾指针处 tail = t; // 返回取得的元素 return result;}(1)出队有两种方式,从队列头或者从队列尾;
(2)通过取模的方式让头尾指针在数组范围内循环;
(3)出队之后没有缩容哈哈^^
栈
前面我们介绍Deque的时候说过,Deque可以直接作为栈来使用,那么ArrayDeque是怎么实现的呢?
public void push(E e) { addFirst(e);}public E pop() { return removeFirst();}是不是很简单,入栈出栈只要都操作队列头就可以了。
总结
(1)ArrayDeque是采用数组方式实现的双端队列;
(2)ArrayDeque的出队入队是通过头尾指针循环利用数组实现的;
(3)ArrayDeque容量不足时是会扩容的,每次扩容容量增加一倍;
(4)ArrayDeque可以直接作为栈使用;
彩蛋
双端队列与双重队列?
双端队列(Deque)是指队列的两端都可以进出元素的队列,里面存储的是实实在在的元素。
双重队列(Dual Queue)是指一种队列有两种用途,里面的节点分为数据节点和非数据节点,它是LinkedTransferQueue使用的数据结构。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
Java集合ArrayDeque类实例分析前言ArrayDeque类是双端队列的实现类,类的继承结构如下面,继承自AbastractCollection(该类实
详解Java中Comparable和Comparator接口的区别本文要来详细分析一下Java中Comparable和Comparator接口的区别,两者都有比
本文以实例详细分析了Java中重载与重写的区别,感兴趣的朋友可以参考一下。一、重载(Overloading):(1)方法重载是让类以统一的方式处理不同类型数据的
后面会详细分析jQuery.event.add/jQuery.event.remove/jQuery.event.trigger。虽然事件模块代码很难读,但其提
本文通过实例给大家详细分析了JS中事件循环机制的原理和用法,以下是全部内容:varstart=newDate()setTimeout(function(){va