新手读源码__JAVA中的Stack、Queue、Deque、PriorityQueue实现

「爱情、让人受尽委屈。」 2022-05-24 00:11 144阅读 0赞

## 前景 ##

继续昨天安装UML插件，构建了大概的Queue类图，今天好好研究下细节

## 类图 ##

![这里写图片描述][70]

## Queue ##

所有的关于Queue的类都实现了Queue这个接口，我们先看看最基本的Queue都包含哪些内容

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>作用</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>add(E)</td> 
   <td>入队</td> 
  </tr> 
  <tr> 
   <td>element()</td> 
   <td>返回队列头</td> 
  </tr> 
  <tr> 
   <td>offer(E)</td> 
   <td>入队</td> 
  </tr> 
  <tr> 
   <td>peek()</td> 
   <td>返回队列头</td> 
  </tr> 
  <tr> 
   <td>poll()</td> 
   <td>返回队列头并且移除它</td> 
  </tr> 
  <tr> 
   <td>remove()</td> 
   <td>返回队列头并且移除它</td> 
  </tr> 
 </tbody> 
</table>

这些方法的作用有重复的部分，比如基本的实现功能就是三个，入队，出队，返回队头，但是每一种都有两种实现，下面进行一下对比

add 和offer

> this method is generally  
> \* preferable to \{@link \#add\}, which can fail to insert an element only  
> \* by throwing an exception.

引用源码上的一句话，offer比add好一点的地方在于，add当队列满的时候会抛出异常，而offer只是会返回false

--------------------

element 和 peek

element和peek的区别在于队列为空的时候peek返回null，element返回异常

> @throws NoSuchElementException if this queue is empty

--------------------

poll 和 remove

poll和remove的区别差不多，poll返回null，remove返回异常

--------------------

小总结：

*  offer+element+poll是不会返回异常的
 *  add+peek+remove是返回异常的

## AbstractQueue ##

关于它我们一笔带过，实现的方法如下  
![这里写图片描述][70 1]  
抛出异常也只是用调用相对应的方法，然后再抛出异常，比如

public boolean add(E e) {
            if (offer(e))
                return true;
            else
                throw new IllegalStateException("Queue full");
        }

## BolckQueue ##

阻塞的队列用于并发中，都在java.util.concurrent这个包里面，让我们先偷偷lou一眼  
![这里写图片描述][70 2]  
为啥是偷偷lou一眼呢？因为笔者进度还在集合，并非到并发，等到了并发我们再回过头来好好看看

## PriorityQueue ##

优先级队列相信学过数据结构的小朋友都不陌生了把～如果你还不知道优先级队列，是时候去补一下功课啦～引用源码中的第一句话作为我们的开篇

> An unbounded priority \{@linkplain Queue queue\} based on a priority heap.

一个基于优先堆的无限大的优先队列，很明显了，它是一个没有队列大小，底层是堆的队列

### 维护的属性 ###

private static final int DEFAULT_INITIAL_CAPACITY = 11; //初始容量11
    transient Object[] queue;                               // 数组
    int size;                                               //大小
    private final Comparator<? super E> comparator;         // 比较器

### 构造器 ###

public PriorityQueue() {
            this(DEFAULT_INITIAL_CAPACITY, null);
    
        public PriorityQueue(int initialCapacity) {
            this(initialCapacity, null);
        }
    
        public PriorityQueue(int initialCapacity,
                             Comparator<? super E> comparator) {
            // Note: This restriction of at least one is not actually needed,
            // but continues for 1.5 compatibility
            if (initialCapacity < 1)
                throw new IllegalArgumentException();
            this.queue = new Object[initialCapacity];
            this.comparator = comparator;
        }
    
            @SuppressWarnings("unchecked")
        public PriorityQueue(Collection<? extends E> c) {
            if (c instanceof SortedSet<?>) {
                SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
                this.comparator = (Comparator<? super E>) ss.comparator();
                initElementsFromCollection(ss);
            }
            else if (c instanceof PriorityQueue<?>) {
                PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
                this.comparator = (Comparator<? super E>) pq.comparator();
                initFromPriorityQueue(pq);
            }
            else {
                this.comparator = null;
                initFromCollection(c);
            }
        }

基础的三种构造器，分别对应了容量、比较器的选择与否,从一个集合中生成优先级队列

### 如何从集合中生成优先级队列 ###

初始化，两个方法

private void initFromCollection(Collection<? extends E> c) {
            initElementsFromCollection(c);
            heapify();
        }
    
        // 负责集合->数组转变
        private void initElementsFromCollection(Collection<? extends E> c) {
            Object[] a = c.toArray();
            // If c.toArray incorrectly doesn't return Object[], copy it.
            if (a.getClass() != Object[].class)
                a = Arrays.copyOf(a, a.length, Object[].class);
            int len = a.length;
            if (len == 1 || this.comparator != null)
                for (Object e : a)
                    if (e == null)
                        throw new NullPointerException();
            this.queue = a;
            this.size = a.length;
        }
    
        // 将转变过来的数组构建成堆
        @SuppressWarnings("unchecked")
        private void heapify() {
            final Object[] es = queue;
            int i = (size >>> 1) - 1;
            if (comparator == null)
                for (; i >= 0; i--)
                    siftDownComparable(i, (E) es[i]);
            else
                for (; i >= 0; i--)
                    siftDownUsingComparator(i, (E) es[i]);
        }

这个构建堆的过程，如果不熟悉，是要去好好复习一下的，这里做简述，从叶子节点的上一层开始，一层一层构建小堆，同时构建的时候维护下堆顶的大小做一次向下筛选，如此循环直到顶层。

### add ###

public boolean add(E e) {
            return offer(e);
        }
    
        public boolean offer(E e) {
            if (e == null)
                throw new NullPointerException();
            modCount++;
            int i = size;
            if (i >= queue.length)
                grow(i + 1);
            siftUp(i, e);
            size = i + 1;
            return true;
        }

add做的操作主要是，数组满扩容，和向上筛选的动作，向上筛选是数据结构的部分，不做探讨，看看扩容

### 扩容 ###

private void grow(int minCapacity) {
            int oldCapacity = queue.length;
            // Double size if small; else grow by 50%
            int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                             (oldCapacity + 2) :
                                             (oldCapacity >> 1));
            // overflow-conscious code
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            queue = Arrays.copyOf(queue, newCapacity);
        }

优先级队列的扩容比较有意思，当旧容量小于64的时候，新容量=旧容量×2+2，否则就是1.5×旧容量

## peek ##

@SuppressWarnings("unchecked")
        public E peek() {
            return (size == 0) ? null : (E) queue[0];
        }

数组的尾部作为了队列的头

## poll ##

@SuppressWarnings("unchecked")
        public E poll() {
            if (size == 0)
                return null;
            int s = --size;
            modCount++;
            E result = (E) queue[0];
            E x = (E) queue[s];
            queue[s] = null;
            if (s != 0)
                siftDown(0, x);
            return result;
        }

poll移除队列头，并返回，将数组的最后一个元素取出作为堆顶，然后做向下筛选，维持堆序列

### 总结 ###

由于PriorityQueue使用的是数组，数据结构是堆，所以描述的部分不详细，如果对堆的内容还不清楚，需要去好好看看的，我们总结一下几点

*   PriorityQueue，底层是数组构建的堆，没有限制的容量大小

*   三种方法offer、pee、poll都不会抛出异常

*   扩容机制1.5倍，如果小于64 2倍+1

## Deque ##

Deque俗称双端队列，之前知道有这样一个东西存在，但是没有真正接触到它，今天正好借机会来学习一下。

### 数据结构 ###

ArrayDeque顾名思义，是基于数组的一个双端队列，基本的数组结构是这样的

![这里写图片描述][70 3]

head：是队列头的index，每次index往前移动一次，比如1 -> 0，head永远指向队列的头部，PS，是有元素的

tail： 队尾的index，永远指向null，区别head的指向头元素

### 维护的属性 ###

transient Object[] elements;
    transient int head;
    transient int tail;

维护的属性很简单，只有3个，一个数组，一个头，一个尾

### 当做普通的队列使用 ###

之前的时候，正如上文所言，没有Queue的实现，只有Deque和PriorityQueue，这两种，所以Deque里面实现了Queue的所有功能，回顾一下Queue中的几种方法

#### Queue-入队 ####

入队有add和offer这两种方法，但是在这里，它们最终都是同一个方法实现的，所以说它们没有区别，看看源代码

public boolean add(E e) {
            addLast(e);
            return true;
        }
    
        public boolean offer(E e) {
            return offerLast(e);
        }
    
        public boolean offerLast(E e) {
            addLast(e);
            return true;
        }

可以看到它们的最底层都是addLast实现的

分析addLast：

public void addLast(E e) {
            if (e == null)
                throw new NullPointerException();
            final Object[] es = elements;
            es[tail] = e;
            if (head == (tail = inc(tail, es.length)))
                grow(1);
        }

刚才我们已经提到过，tail永远指向队列尾部元素的下一个位置null，所以直接`es[tail] = e;`下面一句话是关键，做了两个操作

tail = inc(tail, es.length)

tail指针移动：

static final int inc(int i, int modulus) {
            if (++i >= modulus) i = 0;
            return i;
        }

首先++i将tail的index+1，之后判断是否超出了数组的最大索引，超出了直接设置为0，等于就是形成了一个循环

队列满的调节及扩容：

if (head == (tail = inc(tail, es.length)))
                grow(1);

if语句看head和tail是否重合，重合即扩容,双端队列的扩容比较厉害，笔者佩服

private void grow(int needed) {
            // overflow-conscious code
            final int 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;
            }
        }

private int newCapacity(int needed, int jump) {
            final int oldCapacity = elements.length, minCapacity;
            if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
                if (minCapacity < 0)
                    throw new 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;
        }

首先，当满的时候，1传入扩容方法grow，作为needed，总的来说，扩容和PriorityQueue一样，小于64 2倍+1，不然就是1.5倍，复制操作，是将原来的数组先如数拷贝进新数组，之后在新数组上，将数组进行拷贝，如下图  
![这里写图片描述][70 4]  
第一次复制，从0-5复制进新数组，第二次复制从0-5复制到6-11，并且重置head和将0-5全部清空

#### 出队 ####

public E poll() {
            return pollFirst();
        }
        public E pollFirst() {
            final Object[] es;
            final int h;
            E e = elementAt(es = elements, h = head);
            if (e != null) {
                es[h] = null;
                head = inc(h, es.length);
            }
            return e;
        }

这个操作简单，head指针后移，返回head指向的元素，之后再清空null，poll和remove方法一样的

#### 返回队头 ####

peek和elment都很简单，返回head指向的元素就结束了

### 当做栈使用 ###

Deque接口也实现了栈相关的操作

#### 入栈push ####

public void push(E e) {
            addFirst(e);
        }
    
        public void addFirst(E e) {
            if (e == null)
                throw new NullPointerException();
            final Object[] es = elements;
            es[head = dec(head, es.length)] = e;
            if (head == tail)
                grow(1);
        }
    
        static final int dec(int i, int modulus) {
            if (--i < 0) i = modulus - 1;
            return i;
        }

从源码我们可以分析出几点  
1、head 作为栈顶来使用的

2、入栈首先将head前移一个指向新的元素，并且判断是否小于0，小于0 则在数组的尾部放入新的元素

3、由于tail指向最后一个元素的后一个位置，所以head和tail重合的时候，它先存入元素再判断head和tail的关系并不会导致新元素覆盖旧元素的问题。

### 出栈 ###

public E pollFirst() {
            final Object[] es;
            final int h;
            E e = elementAt(es = elements, h = head);
            if (e != null) {
                es[h] = null;
                head = inc(h, es.length);
            }
            return e;
        }

出栈就比较好理解了，移除head元素，并且head后移

### 双端队列 ###

在理解了一端队列使用的情况下，我们很容易理解双端的含义，即head和tail的作用变成了差不多，既可以在左添加也可以在右边添加。如此而已，略过

## 总结 ##

此次学习的重点是，我们可以看到队列的数组构建，里面的逻辑部分，对于熟悉的队列，java的优先级队列是基于堆的，堆呢又是基于数组的。最重要的还是复习巩固如何通过数组来实现队列。

[70]: /images/20220524/aa93c84dd6db4197a54de2715eb9fa4c.png
[70 1]: /images/20220524/1c3b136a6bc047e6a3f015528afe69c1.png
[70 2]: /images/20220524/8d01878c0cd94ec9bfdd773fc43330c0.png
[70 3]: /images/20220524/ccef9b204db34a8ab3da09a4d8b05acd.png
[70 4]: /images/20220524/7421477acc284582bbd3d36113311cf3.png