/**
   * 鏈表的節(jié)點(diǎn)，同時(shí)也是通過(guò)它來(lái)實(shí)現(xiàn)一個(gè)單向鏈表
   */
  static class Node<E> {
    E item;

    // 指向鏈表的下一個(gè)節(jié)點(diǎn)
    Node<E> next;

    Node(E x) { item = x; }
  }

   /**
   * 它的next指向隊(duì)列頭，這個(gè)節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)
   */
  transient Node<E> head;

  /**
   * 隊(duì)列尾節(jié)點(diǎn)
   */
  private transient Node<E> last;

last = head = new Node<E>(null);

 /**
   * 向隊(duì)列尾插入節(jié)點(diǎn)
   */
  private void enqueue(Node<E> node) {
    // assert putLock.isHeldByCurrentThread(); // 當(dāng)前線程肯定獲取了putLock鎖
    // 將原隊(duì)列尾節(jié)點(diǎn)的next引用指向新節(jié)點(diǎn)node，然后再將node節(jié)點(diǎn)設(shè)置成隊(duì)列尾節(jié)點(diǎn)last
    // 這樣就實(shí)現(xiàn)了向隊(duì)列尾插入節(jié)點(diǎn)
    last = last.next = node;
  }

  // 移除隊(duì)列頭節(jié)點(diǎn)，并返回被刪除的節(jié)點(diǎn)數(shù)據(jù)
  private E dequeue() {
    // assert takeLock.isHeldByCurrentThread(); // 當(dāng)前線程肯定獲取了takeLock鎖
    // assert head.item == null;

    Node<E> h = head;
    // first節(jié)點(diǎn)中才存儲(chǔ)了隊(duì)列中第一個(gè)元素的數(shù)據(jù)
    Node<E> first = h.next;
    h.next = h; // help GC
    // 設(shè)置新的head值，相當(dāng)于刪除了first節(jié)點(diǎn)。因?yàn)閔ead節(jié)點(diǎn)本身不儲(chǔ)存數(shù)據(jù)
    head = first;
    // 隊(duì)列頭的數(shù)據(jù)
    E x = first.item;
    // 移除原先的數(shù)據(jù)
    first.item = null;
    return x;
  }

  /** 獨(dú)占鎖，用于處理插入隊(duì)列操作的并發(fā)問(wèn)題，即put與offer操作 */
  private final ReentrantLock putLock = new ReentrantLock();

  /** 隊(duì)列不滿的條件Condition，它是由putLock鎖生成的 */
  private final Condition notFull = putLock.newCondition();

  /** 獨(dú)占鎖，用于處理刪除隊(duì)列頭操作的并發(fā)問(wèn)題，即take與poll操作 */
  private final ReentrantLock takeLock = new ReentrantLock();

  /** 隊(duì)列不為空的條件Condition， 它使用takeLock鎖生成的 */
  private final Condition notEmpty = takeLock.newCondition();

  /** 隊(duì)列中元素的個(gè)數(shù)，這里使用AtomicInteger變量，保證并發(fā)安全問(wèn)題 */
  private final AtomicInteger count = new AtomicInteger();

  /**
   * 喚醒在notEmpty條件下等待的線程，即移除隊(duì)列頭時(shí)，發(fā)現(xiàn)隊(duì)列為空而被迫等待的線程。
   * 注意，因?yàn)橐{(diào)用Condition的signal方法，必須獲取對(duì)應(yīng)的鎖，所以這里調(diào)用了takeLock.lock()方法。
   * 當(dāng)隊(duì)列中插入元素(即put或offer操作)，那么隊(duì)列肯定不為空，就會(huì)調(diào)用這個(gè)方法。
   */
  private void signalNotEmpty() {
    final ReentrantLock takeLock = this.takeLock;
    takeLock.lock();
    try {
      notEmpty.signal();
    } finally {
      takeLock.unlock();
    }
  }

  /**
   * 喚醒在notFull條件下等待的線程，即隊(duì)列尾添加元素時(shí)，發(fā)現(xiàn)隊(duì)列已滿而被迫等待的線程。
   * 注意，因?yàn)橐{(diào)用Condition的signal方法，必須獲取對(duì)應(yīng)的鎖，所以這里調(diào)用了putLock.lock()方法
   * 當(dāng)隊(duì)列中刪除元素(即take或poll操作)，那么隊(duì)列肯定不滿，就會(huì)調(diào)用這個(gè)方法。
   */
  private void signalNotFull() {
    final ReentrantLock putLock = this.putLock;
    putLock.lock();
    try {
      notFull.signal();
    } finally {
      putLock.unlock();
    }
  }

  public void put(E e) throws InterruptedException {
    if (e == null) throw new NullPointerException();
    // 記錄插入操作前元素的個(gè)數(shù)
    int c = -1;
    // 創(chuàng)建新節(jié)點(diǎn)node
    Node<E> node = new Node<E>(e);
    final ReentrantLock putLock = this.putLock;
    final AtomicInteger count = this.count;
    putLock.lockInterruptibly();
    try {
      //表示隊(duì)列已滿，那么就要調(diào)用notFull.await方法，讓當(dāng)前線程等待
      while (count.get() == capacity) {
        notFull.await();
      }
      // 向隊(duì)列尾插入新元素
      enqueue(node);
      // 將當(dāng)前隊(duì)列元素個(gè)數(shù)加1，并返回加1之前的元素個(gè)數(shù)。
      c = count.getAndIncrement();
      // c + 1 < capacity表示隊(duì)列未滿，就喚醒可能等待插入操作的線程
      if (c + 1 < capacity)
        notFull.signal();
    } finally {
      putLock.unlock();
    }
    // c == 0表示插入之前，隊(duì)列是空的。隊(duì)列從空到放入一個(gè)元素時(shí)，
    // 才喚醒等待刪除的線程
    // 防止頻繁獲取takeLock鎖，消耗性能
    if (c == 0)
      signalNotEmpty();
  }

  public E take() throws InterruptedException {
    E x;
    int c = -1;
    final AtomicInteger count = this.count;
    final ReentrantLock takeLock = this.takeLock;
    takeLock.lockInterruptibly();
    try {
      //表示隊(duì)列為空，那么就要調(diào)用notEmpty.await方法，讓當(dāng)前線程等待
      while (count.get() == 0) {
        notEmpty.await();
      }
      // 刪除隊(duì)列頭元素，并返回它
      x = dequeue();
      // 返回當(dāng)前隊(duì)列個(gè)數(shù)，然后將隊(duì)列個(gè)數(shù)減一
      c = count.getAndDecrement();
      // c > 1表示隊(duì)列不為空，就喚醒可能等待刪除操作的線程
      if (c > 1)
        notEmpty.signal();
    } finally {
      takeLock.unlock();
    }
    /**
     * c == capacity表示刪除操作之前，隊(duì)列是滿的。只有從滿隊(duì)列中刪除一個(gè)元素時(shí)，
     * 才喚醒等待插入的線程
     * 防止頻繁獲取putLock鎖，消耗性能
     */
    if (c == capacity)
      signalNotFull();
    return x;
  }

  // 查看隊(duì)列頭元素
  public E peek() {
    // 隊(duì)列為空，返回null
    if (count.get() == 0)
      return null;
    final ReentrantLock takeLock = this.takeLock;
    takeLock.lock();
    try {
      // 獲取隊(duì)列頭節(jié)點(diǎn)first
      Node<E> first = head.next;
      // first == null表示隊(duì)列為空，返回null
      if (first == null)
        return null;
      else
        // 返回隊(duì)列頭元素
        return first.item;
    } finally {
      takeLock.unlock();
    }
  }

  // 從隊(duì)列中刪除指定元素o
  public boolean remove(Object o) {
    if (o == null) return false;
    // 因?yàn)椴皇莿h除列表頭元素，所以就涉及到head和last兩個(gè)變量，
    // putLock與takeLock都要加鎖
    fullyLock();
    try {
      // 遍歷整個(gè)隊(duì)列，p表示當(dāng)前節(jié)點(diǎn)，trail表示當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
      // 因?yàn)槭菃蜗蜴湵?，所以需要記錄兩個(gè)節(jié)點(diǎn)
      for (Node<E> trail = head, p = trail.next;
         p != null;
         trail = p, p = p.next) {
        // 如果找到了指定元素，那么刪除節(jié)點(diǎn)p
        if (o.equals(p.item)) {
          unlink(p, trail);
          return true;
        }
      }
      return false;
    } finally {
      fullyUnlock();
    }
  }

  // 刪除當(dāng)前節(jié)點(diǎn)p，trail代表p的前一個(gè)節(jié)點(diǎn)
  void unlink(Node<E> p, Node<E> trail) {
    // 將當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)設(shè)置為null
    p.item = null;
    // 這樣就在鏈表中刪除了節(jié)點(diǎn)p
    trail.next = p.next;
    // 如果節(jié)點(diǎn)p是隊(duì)列尾last，而它被刪除了，那么就要將trail設(shè)置為last
    if (last == p)
      last = trail;
    // 將元素個(gè)數(shù)減一，如果原隊(duì)列是滿的，那么就調(diào)用notFull.signal()方法
    // 其實(shí)這個(gè)不用判斷直接調(diào)用的，因?yàn)檫@里肯定獲取了putLock鎖
    if (count.getAndDecrement() == capacity)
      notFull.signal();
  }