欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java双端队列作用(java三种队列详解)

程序员文章站 2023-11-19 09:47:16
linkedblockingdeque概述linkedblockingdeque是由链表构成的界限可选的双端阻塞队列,支持o(1)的时间复杂度从两端插入和移除元素,如不指定边界,则为integer.m...

linkedblockingdeque概述

linkedblockingdeque是由链表构成的界限可选的双端阻塞队列,支持o(1)的时间复杂度从两端插入和移除元素,如不指定边界,则为integer.max_value。

由一个reentrantlock保证同步,使用conditions来实现等待通知。

java双端队列作用(java三种队列详解)

类图结构及重要字段

java双端队列作用(java三种队列详解)
public class linkedblockingdeque<e>
    extends abstractqueue<e>
    implements blockingdeque<e>, java.io.serializable {

    private static final long serialversionuid = -387911632671998426l;

    /** 双向链表节点 */
    static final class node<e> {
        e item;
        node<e> prev;
        node<e> next;
        node(e x) {
            item = x;
        }
    }

    /**
     * 指向第一个节点
     * invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient node<e> first;

    /**
     * 指向最后一个节点
     * invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient node<e> last;

    /** 节点数量 */
    private transient int count;

    /** 队列容量 */
    private final int capacity;

    /** 保证同步 */
    final reentrantlock lock = new reentrantlock();

    /** take操作发生的条件 */
    private final condition notempty = lock.newcondition();

    /** put操作发生的条件 */
    private final condition notfull = lock.newcondition();
    
}

linkfirst

尝试将节点加入到first之前,更新first,如果插入之后超出容量,返回false。

private boolean linkfirst(node<e> node) {
        // assert lock.isheldbycurrentthread();
        if (count >= capacity)
            return false;
        node<e> f = first;
        node.next = f;
        first = node;
        if (last == null)
            last = node;
        else
            f.prev = node;
        ++count;
        notempty.signal();
        return true;
    }
java双端队列作用(java三种队列详解)

linklast

在last节点后加入节点node,更新last。如果插入之后超出容量,返回false。

private boolean linklast(node<e> node) {
        // assert lock.isheldbycurrentthread();
        if (count >= capacity)
            return false;
        node<e> l = last;
        node.prev = l;
        last = node;
        if (first == null)
            first = node;
        else
            l.next = node;
        ++count;
        notempty.signal();// 满足notempty条件
        return true;
    }
java双端队列作用(java三种队列详解)

unlinkfirst

移除first节点,并返回其item值,如果队列为空,则返回full。

private e unlinkfirst() {
        // assert lock.isheldbycurrentthread();
        node<e> f = first;
        if (f == null)
            return null;
        node<e> n = f.next;
        e item = f.item;
        f.item = null;
        f.next = f; // help gc
        first = n;
        if (n == null)
            last = null;
        else
            n.prev = null;
        --count;
        notfull.signal();// 满足notfull条件
        return item;
    }
java双端队列作用(java三种队列详解)

unlinklast

移除last节点,并返回其item值,如果队列为空,则返回full。

private e unlinklast() {
        // assert lock.isheldbycurrentthread();
        node<e> l = last;
        if (l == null)
            return null;
        node<e> p = l.prev;
        e item = l.item;
        l.item = null;
        l.prev = l; // help gc
        last = p;
        if (p == null)
            first = null;
        else
            p.next = null;
        --count;
        notfull.signal(); // 满足notfull条件
        return item;
    }
java双端队列作用(java三种队列详解)

unlink

移除任意一个节点,注意这里并没有操作x本身的连接,因为它可能仍被iterator使用着。

void unlink(node<e> x) {
        // assert lock.isheldbycurrentthread();
        node<e> p = x.prev;
        node<e> n = x.next;
        // 移除的是first
        if (p == null) {
            unlinkfirst();
        // 移除的是last
        } else if (n == null) {
            unlinklast();
        } else {
            // 移除的是中间节点
            p.next = n;
            n.prev = p;
            x.item = null;
            // don't mess with x's links.  they may still be in use by
            // an iterator.
            // 这里x的prev和next指针都没有改变,因为他们可能在被iterator使用
            --count;
            notfull.signal();
        }
    }
java双端队列作用(java三种队列详解)

总结

linkedblockingdeque是由链表构成的界限可选的双端阻塞队列,支持o(1)的时间复杂度从两端插入和移除元素,如不指定边界,则为integer.max_value。

由一个reentrantlock保证同步,使用conditions来实现等待通知。

上面介绍的所有操作基本上就是核心方法啦,诸如putfirst、putlast、takefirst、takelast等方法都会调用上面的核心方法,而且实现上面也是比较简单的,就是双端链表的基本操作,不懂的可以画画图帮助理解哈。