快捷導(dǎo)航

java中PriorityBlockingQueue的入隊(duì)知識點(diǎn)總結(jié)

更新時(shí)間：2021年01月13日 08:28:02 作者：小妮淺淺

在本篇文章里小編給大家整理一篇關(guān)于java中PriorityBlockingQueue的入隊(duì)知識點(diǎn)總結(jié)內(nèi)容，有需要的朋友們可以學(xué)習(xí)下。

在PriorityBlockingQueue中添加元素同樣有四種方法，因?yàn)槭菢錉畹慕Y(jié)構(gòu)，所以在插入方法上也有所變化，是自下而上的操作過程。在入隊(duì)的規(guī)則上有三個(gè)要點(diǎn)需要我們注意。鑒于PriorityBlockingQueue入隊(duì)方法主要通過offer(E)實(shí)現(xiàn)，所以我們就這種方法作主要講解。

1.入隊(duì)規(guī)則

（1）默認(rèn)的插入規(guī)則中，新加入的元素可能會破壞小頂堆的性質(zhì)，因此需要進(jìn)行調(diào)整。

（2）調(diào)整的過程為：從尾部下標(biāo)的位置開始，將加入的元素逐層與當(dāng)前點(diǎn)的父節(jié)點(diǎn)的內(nèi)容進(jìn)行比較并交換，直到滿足父節(jié)點(diǎn)內(nèi)容都小于子節(jié)點(diǎn)的內(nèi)容為止。

（3）默認(rèn)的刪除調(diào)整中，首先獲取頂部下標(biāo)和最尾部的元素內(nèi)容，從頂部的位置開始，將尾部元素的內(nèi)容逐層向下與當(dāng)前點(diǎn)的左右子節(jié)點(diǎn)中較小的那個(gè)交換，直到判斷元素內(nèi)容小于或等于左右子節(jié)點(diǎn)中的任何一個(gè)為止。

2.入隊(duì)方法

入隊(duì)方法有：add(E), put(E), offer(E, timeout, TimeUnit), offer(E)

public void put(E e) {
  offer(e); // never need to block
}
public boolean offer(E e) {
  //判斷是否為空
  if (e == null)
    throw new NullPointerException();
  //顯示鎖
  final ReentrantLock lock = this.lock;
  lock.lock();
  //定義臨時(shí)對象
  int n, cap;
  Object[] array;
  //判斷數(shù)組是否滿了
  while ((n = size) >= (cap = (array = queue).length))
    //數(shù)組擴(kuò)容
    tryGrow(array, cap);
  try {
    //拿到比較器
    Comparator<? super E> cmp = comparator;
    //判斷是否有自定義比較器
    if (cmp == null)
      //堆上浮
      siftUpComparable(n, e, array);
    else
      //使用自定義比較器進(jìn)行堆上浮
      siftUpUsingComparator(n, e, array, cmp);
    //隊(duì)列長度 +1
    size = n + 1;
    //喚醒休眠的出隊(duì)線程
    notEmpty.signal();
  } finally {
    //釋放鎖
    lock.unlock();
  }
  return true;
}

可以看出前三個(gè)方法內(nèi)部都是通過 offer(e) 方法實(shí)現(xiàn)的。

您可能感興趣的文章: