Queue

Posted on | In |

[TOC]

Queue特性及方法

框架
queue_collection_framework.png

特性:
按元素添加的顺序排列（FIFO、FILO、优先级等）

queue添加的方法：
queue.png

添加一个元素进入队列

1
boolean offer (E e) // insert the given element if possible

取一个元素

若遇到栈空，会报错：

1
2
E element() // retrieve but do not remove the head element
E remove() // retrieve and remove the head element

若遇到栈空，会返回null：

1
2
E peek() // retrieve but do not remove the head element
E poll() // retrieve and remove the head element

所以尽量不要在队列中添加null元素（正常不让添加null，但在LinkedList实现下允许null）

不建议使用迭代器（因为在多线程会出问题，顺序也会变）

Queue接口实现

PriorityQueue

线程不安全
按自然顺序或者按比较器排序（底层堆排）

PriorityQueue构造

1
2
3
4
5
6
7
8
9
10
11
12
13
PriorityQueue() // natural ordering, default initial capacity (11)
PriorityQueue(Collection<? extends E> c)
// natural ordering of elements taken from c, unless
// c is a PriorityQueue or SortedSet, in which case
// copy c's ordering
PriorityQueue(int initialCapacity)
// natural ordering, specified initial capacity
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
// Comparator ordering, specified initial capacity
PriorityQueue(PriorityQueue<? extends E> c)
// ordering and elements copied from c
PriorityQueue(SortedSet<? extends E> c)
// ordering and elements copied from c

PriorityQueue实现原理

底层为二叉树（与普通二叉数有两点不同）

  • 上层元素大于下层元素
  • 除底层外其他层必须是满的
    添加时先左在右，添加后调整，如下：
    adding_to_a_priorityqueue.png
    出栈时，最后一个元素置顶，在调整，如下：
    adding_to_a_priorityqueue2.png

    多线程表现

    线程不安全，不适合并发下使用
    一个线程安全的版本：PriorityBlockingQueue

    性能

    入栈、出栈、移除 （需要堆排一次）：O（logn）
    查询 （ remove(Object) 和 contains）：O（n）
    查看栈顶元素：O（1）

    ConcurrentLinkedQueue

    无边界，线程安全，FIFO的有序队列
    基于volatile关键字、CAS的“wait－free”（常规无等待）来实现（硬件指令平台相关）线程安全
    链表结构
    插入在尾部，尾部指针与尾部元素相距hops距离时，重置尾部指针

    BlockingQueue接口

    大部分线程安全的queue都是实现该接口
    多用于生产者消费者模式，系统中常用的场景为打印缓存队列

    接口方法

    blockingdeque.png

    添加元素

    1
    2
    3
    boolean offer(E e, long timeout, TimeUnit unit)
    // insert e, waiting up to the timeout
    void put(E e) // add e, waiting as long as necessary

移除一个元素

1
2
3
4
E poll(long timeout, TimeUnit unit)
// retrieve and remove the head, waiting up to the timeout
E take() // retrieve and remove the head of this queue, waiting
// as long as necessary

查询queue中的内容

1
2
3
4
5
6
7
int drainTo(Collection<? super E> c)
// clear the queue into c
int drainTo(Collection<? super E> c, int maxElements)
// clear at most the specified number of elements into c
int remainingCapacity()
// return the number of elements that would be accepted
// without blocking, or Integer.MAX_VALUE if unboundeds

BlockingQueue保证实现类是线程安全的和原子性，但是不保证批量操作（继承自collection-addall，containsall，retainall，removeall——除非另外实现）

接口实现

LinkedBlockingQueue

原理：链表
构造：可以指定空间，没指定默认时为 Integer.MAX_VALUE
并发： 线程安全，FIFO队列、迭代器弱一致性
性能：添加，移除O(1),查询O(n)

ArrayBlockingQueue

原理：环形数组（原始实现是ArrayList）
构造：必须指定空间
并发： 线程安全，FIFO队列、迭代器弱一致性
性能：添加，移除O(1),查询O(n)

PriorityBlocingQueue

原理：优先级队列（安全版本）
构造：与 优先级队列 相同
并发： 线程安全，FIFO队列、迭代器快速失效（可手动转数组处理）
性能：与 优先级队列 相同

DelayQueue

原理：优先级队列
等待时间越久越前、若都在计时，poll返回null，peek返回第一个计时的数

1
2
3
interface Delayed extends Comparable<Delayed> {
long getDelay(TimeUnit unit);
}

构造：与 优先级队列 相同
并发： 线程安全，FIFO队列、迭代器快速失效（可手动转数组处理）
性能：与 优先级队列 相同

SynchronousQueue

原理：
公平——TransferQueue
非公平——TransferStack
一对一匹配模式
构造：

1
2
SynchronousQueue()
SynchronousQueue(boolean fair)

Deque接口

双端队列，不允许优先级排序
可以用作stack

接口方法

deque.png

类似collection的方法

1
2
3
4
5
6
7
8
void addFirst(E e) // insert e at the head if there is enough space
void addLast(E e) // insert e at the tail if there is enough space
void push(E e) // insert e at the head if there is enough space
boolean removeFirstOccurrence(Object o);// remove the first occurrence of o
boolean removeLastOccurrence(Object o);// remove the last occurrence of o
Iterator<E> descendingIterator()
// get an iterator, returning deque elements in
// reverse order

类似Queue的方法

1
2
boolean offerFirst(E e) // insert e at the head if the deque has space
boolean offerLast(E e) // insert e at the tail if the deque has space

以下方法在空队列时放回null：

1
2
3
4
E peekFirst() // retrieve but do not remove the first element
E peekLast() // retrieve but do not remove the last element
E pollFirst() // retrieve and remove the first element
E pollLast() // retrieve and remove the last element

以下方法在空队列时抛出异常：

1
2
3
4
5
E getFirst() // retrieve but do not remove the first element
E getLast() // retrieve but do not remove the last element
E removeFirst() // retrieve and remove the first element
E removeLast() // retrieve and remove the last element
E pop() // retrieve and remove the first element

Deque实现

ArrayDeque（推荐）

原理：环形队列(类似与ArrayBlockingQueue)
并发：迭代器快速失效
性能：添加移除O(1)

LinkedList（不推荐）

a_doubly_linkedlist.png
原理：跳表
并发：迭代器快速失效，线程不安全
性能：添加移除O(1)、随机访问O(n)

BlockingDeque接口

在BlockingQueue基础上体检的接口：
blockingdeque.png
原理:两个队列，前一个满载执行，消费者忙不过来；后一个空队列，消费者闲的，这时后队列的消费者去前一个队列尾部拿任务消费，从而提高效率

实现

LinkedBlockingDeque

原理：双向链表
并发：迭代器弱一致性，线程安全
性能：添加移除O(1)、查找O(n)

Queue实现对比

comparative.png

0%