Welcome to github.com/hsfxuebao/j… , hope to help you, if you feel ok, please click on the Star
preface
LinkedBlockingDeque a two-way blocking queue consisting of a linked list structure. Elements can be added to and removed from the head and tail of the queue. Multiple threads can be concurrent to reduce lock contention by half.
The queue to create
BlockingDeque<String> deque = new LinkedBlockingDeque<String>(); Copy the codeCopy the codeApplication scenarios
Generally used in the producer-consumer model.
Let’s look at an example that uses LinkedBlockingQueue to mimic producer and consumer threads for data production and consumption.
package com.niuh.deque; import java.util.concurrent.BlockingQueue; import java.util.concurrent.LinkedBlockingDeque; /** * <p> * LinkedBlockingQueue example, Producers to consumers * < / p > * / public class LinkedBlockingQueueRunner {public static void main (String [] args) { BlockingQueue<Integer> shareQueue = new LinkedBlockingDeque<>(); Producer P = new Producer(shareQueue); Consumer C = new Consumer(shareQueue); P.start(); C.start(); } /** */ class Producer extends Thread {private BlockingQueue<Integer> sharedQueue; public Producer(BlockingQueue<Integer> shareQueue) { super("PRODUCER"); this.sharedQueue = shareQueue; } public void run() { //no synchronization needed for (int i = 0; i < 10; i++) { try { System.out.println(getName() + " produced " + i); sharedQueue.put(i); Thread.sleep(2000); } catch (InterruptedException e) { e.printStackTrace(); }}}} /** * Consumer */ class Consumer extends Thread {private BlockingQueue<Integer> shareQueue; public Consumer(BlockingQueue<Integer> shareQueue) { super("CONSUMER"); this.shareQueue = shareQueue; } public void run() { try { while (true) { Integer item = shareQueue.take(); System.out.println(getName() + " consumed " + item); } } catch (InterruptedException e) { e.printStackTrace(); }}} copy the codeCopy the codeThe working principle of
LinkedBlockingDeque data structure, as shown below:
Description:
- LinkedBlockingDeque descends from AbstractQueue, which is essentially a bidirectional queue with FIFO and FILO support.
- LinkedBlockingDeque implements the BlockingDeque interface, which supports multithreaded concurrency. When multiple threads compete for the same resource, after one thread gets the resource, other threads need to block and wait.
- LinkedBlockingDeque is implemented via a two-way linked list.
- First is the head of a bidirectional list.
- Last is the end of a bidirectional list.
- Count is the actual size of LinkedBlockingDeque, which is the current number of nodes in the bidirectional list.
- Capacity is the capacity of the LinkedBlockingDeque, which is specified when the LinkedBlockingDeque is created.
- Lock is the mutex that controls the LinkedBlockingDeque. When multiple threads compete to access the LinkedBlockingDeque at the same time, one thread obtains the mutex lock, and the other thread blocks until the thread releases the lock. Other threads have the opportunity to acquire the lock and thus CPU execution.
- NotEmpty and notFull are “non-empty conditions” and “notFull conditions” respectively. They allow for more nuanced concurrency control.
— If the queue is empty when A thread (thread A) wants to retrieve data, the thread will wait notempty.await (); When some other thread (thread B) has inserted data into the queue, notempty.signal () is called to wake up the waiting thread on notEmpty. At this point, thread A is woken up and allowed to continue running. In addition, thread A fetches The takeLock before performing the fetch operation, and releases the takeLock after the fetch operation is complete.
— If the queue is full when a thread (thread H) wants to insert data, the thread will wait by executing notfull.await (); When some other thread (thread I) retrieves data, it calls notFull.signal() to wake up the “waiting thread on notFull.” At this point, thread H will wake up and continue running. In addition, thread H gets the putLock before the insert operation and releases the putLock after the insert operation is complete.
Source code analysis
define
LinkedBlockingDeque class inheritance is as follows:
The BlockingDeque interface
BlockingDeque extends BlockingQueue and Deque.
The main methods are as follows:
Member attribute
There is only one lock inside the LinkedBlockingDeque and the two conditions associated with that lock, so it can be inferred that only one thread can join or unjoin at the head or tail of a queue at any one time. You can see that this is different from a LinkedBlockingQueue, which can have two threads running on both ends.
// Queue head Node TRANSIENT Node<E> first; // Queue end Node TRANSIENT Node<E> last; Private TRANSIENT int count; Private final int capacity; Final ReentrantLock lock = new ReentrantLock(); Private final Condition notEmpty = lock. NewCondition (); Private final Condition notFull = lock.newCondition(); Copy the codeCopy the codeThe inner class Node
A Node object represents a linked list Node. The item attribute represents the element saved by the current Node (if item is null, the current Node has been deleted), the next attribute represents the successor nodes of the current Node, and the prev attribute represents the precursor nodes of the current Node.
Static final class Node<E> {// Node data E item; // Node<E> prev; // Next Node Node<E> next; Node(E x) { item = x; }} Copy the codeCopy the codeThe constructor
Three constructors are provided, LinkedBlockingDeque(int) being its main constructor, which mainly involves initialization of queue capacity. When using the no-argument constructor, the blocking queue has a capacity of integer.max_value, which is infinite.
After initialization, if the queue does not contain any elements, the head node and the tail node are null. See that the structure of the three constructors is the same as LinkedBlockingQueue. However, there is a sentinel node in the LinkedBlockingQueue that maintains the head node, whereas there is no sentinel node in LinkedBlockingDeque.
public LinkedBlockingDeque() { this(Integer.MAX_VALUE); } public LinkedBlockingDeque(int capacity) {if (capacity <= 0) throw new IllegalArgumentException(); this.capacity = capacity; } public LinkedBlockingDeque(Collection<? extends E> c) { this(Integer.MAX_VALUE); final ReentrantLock lock = this.lock; lock.lock(); // Never contended, but necessary for visibility try { for (E e : c) { if (e == null) throw new NullPointerException(); if (! linkLast(new Node<E>(e))) throw new IllegalStateException("Deque full"); } } finally { lock.unlock(); }} Copy the codeCopy the codeAdd elements
Add elements at the end of the queue
Methods like PUT Offer add Offer add an element at the end of the queue. They delegate the core implementation to putLast, offerLast, and addLast implementations
public void put(E e) throws InterruptedException { putLast(e); } public boolean offer(E e) { return offerLast(e); } public boolean add(E e) { addLast(e); return true; } public boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException { return offerLast(e, timeout, unit); } Duplicate codeCopy the codeputLast(E e)
PutLast adds elements at the end of the queue
PutLast obtains the lock lock(lock.lock()), then tries to add a new node (linkLast(node)) at the end of the queue, if the link to the new node fails, (notful.await ()) sleeps until “notFull” is notified.
public void putLast(E e) throws InterruptedException { if (e == null) throw new NullPointerException(); Node<E> node = new Node<E>(e); final ReentrantLock lock = this.lock; lock.lock(); try { while (! linkLast(node)) notFull.await(); } finally {lock.unlock(); }} Copy the codeCopy the codeLinkLast attempts to add a new node at the end of the queue. Main logic:
-
If the queue is full, return false(new nodes cannot be linked);
-
Add node to join the team as a new tail node to the team (last = node) and update the related link relationship;
-
Element count increment by 1(++count);
-
Wakes up a thread waiting for a non-empty condition (notempty.signal ()) and returns true.
private boolean linkLast(Node node) { // assert lock.isHeldByCurrentThread(); If (count >= capacity)// The queue is full and the new node cannot be connected return false; Node l = last; node.prev = l; Last = node; // Set last = node; If (first == null) // There is no node in the queue, last first is not initialized, // There is only one node (element) in the queue, First and last specify the same node. else l.next = node; // The successor of l is the new tail node (node) ++count; Notempty.signal (); // Tell a thread waiting for a “non-empty” condition to return true; } Duplicate code
offerLast(E e)
OfferLast is similar to putLast in that offerLast returns false when it detects that the queue is full and does not block the wait.
public boolean offerLast(E e) { if (e == null) throw new NullPointerException(); Node<E> node = new Node<E>(e); final ReentrantLock lock = this.lock; lock.lock(); try { return linkLast(node); } finally { lock.unlock(); }} Copy the codeCopy the codeofferLast(e, timeout, unit)
The multi-parameter offerLast method, which can be thought of as a timeout version of putLast.
public boolean offerLast(E e, long timeout, TimeUnit unit) throws InterruptedException { if (e == null) throw new NullPointerException(); Node<E> node = new Node<E>(e); long nanos = unit.toNanos(timeout); final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { while (! LinkLast (node)) {if (nanos <= 0) return false; nanos = notFull.awaitNanos(nanos); } return true; } finally { lock.unlock(); }} Copy the codeCopy the codeaddLast(E e)
AddLast adds elements to the end of the queue and throws an exception if the queue is full.
public void addLast(E e) { if (! offerLast(e)) throw new IllegalStateException("Deque full"); } Duplicate codeCopy the codeAdd an element at the head of the team
push(E e)
Push inserts an element at the head of the queue, calling addFirst
public void push(E e) { addFirst(e); } Duplicate codeCopy the codeaddFirst(E e)
Inserts an element at the head of the queue and throws an IllegalStateException if the queue is full
public void addFirst(E e) { if (! offerFirst(e)) throw new IllegalStateException("Deque full"); } Duplicate codeCopy the codeputFirst(E e)
PutLast inserts elements at the head of the queue and blocks if capacity is full
-
Lock (lock.lock())
-
Then try adding a new node (linkFirst(node)) at the head of the queue.
-
If linking to a new node fails, (notfull.await ()) sleeps until “notFull” is notified.
public void putFirst(E e) throws InterruptedException { if (e == null) throw new NullPointerException(); Node node = new Node(e); final ReentrantLock lock = this.lock; lock.lock(); try { while (! linkFirst(node)) notFull.await(); } finally { lock.unlock(); }} Copy the code
LinkLast attempts to link a new node at the head of the queue. Main logic:
-
If the queue is full, return false(new nodes cannot be linked);
-
Add node to the team as the new head node (first = node) and update the related link relationship;
-
Element count increment by 1(++count);
-
Notify a thread waiting for a non-empty condition (notempty.signal ()) and return true.
private boolean linkFirst(Node node) { // assert lock.isHeldByCurrentThread(); If (count >= capacity) // The queue is full and the new node cannot be connected return false; Node f = first; node.next = f; // Set the successor of node to the original head node first = node; //// The new tail node is the newly added node node // Update the precursor node of the original head node f if (last == null)// There is no node in the queue, last first is not initialized // There is only one node (element) in the queue, First and last specify the same node. Node last = node; else f.prev = node; // the first node of f is the new head node (node) ++count; Notempty.signal (); // Tell a thread waiting for a “non-empty” condition to return true; } Duplicate code
offerFirst(E e)
The offerFirst method is similar to putFirst, but offerFirst returns false when it detects that the queue is full and does not block the wait.
public boolean offerFirst(E e) { if (e == null) throw new NullPointerException(); Node<E> node = new Node<E>(e); final ReentrantLock lock = this.lock; lock.lock(); try { return linkFirst(node); } finally { lock.unlock(); }} Copy the codeCopy the codeofferFirst(E e, long timeout, TimeUnit unit)
The multi-parameter offerFirst method, which can be thought of as a timeout version of putFirst.
public boolean offerFirst(E e, long timeout, TimeUnit unit) throws InterruptedException { if (e == null) throw new NullPointerException(); Node<E> node = new Node<E>(e); long nanos = unit.toNanos(timeout); final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { while (! LinkFirst (node)) {if (nanos <= 0) return false; nanos = notFull.awaitNanos(nanos); } return true; } finally { lock.unlock(); }} Copy the codeCopy the codeRemove elements
Delete the element at the head of the queue
Methods like remove Pop Poll Take add elements to the end of the queue. They delegate core implementations to removeFirst, pollFirst, takeFirst, and so on
public E take() throws InterruptedException { return takeFirst(); } public E poll() { return pollFirst(); } public E poll(long timeout, TimeUnit unit) throws InterruptedException { return pollFirst(timeout, unit); } public E remove() { return removeFirst(); } public E pop() { return removeFirst(); } Duplicate codeCopy the codetakeFirst()
-
TakeLast obtains the lock lock(lock.lock());
-
Then try unlinking a node at the end of the queue (unlinkLast());
-
If unlinking fails (queue empty), (notempty.await ()) sleeps until a “notEmpty” notification is received.
public E takeLast() throws InterruptedException { final ReentrantLock lock = this.lock; lock.lock(); try { E x; while ( (x = unlinkLast()) == null) notEmpty.await(); return x; } finally { lock.unlock(); }} Copy the code
UnlinkLast () attempts to unlink the last node in the list
-
If the queue is empty, return NULL (cannot unlink);
-
Take the precursor Node of the original tail Node (Node P = L.rev) as the new tail Node (last = p) and update the related link relationship;
-
Element count decrement by 1(–count);
-
Wake up a thread waiting for the “notFull” condition (notfull.signal ()), finally returning the element from the original tail node (E item = l.tem).
private E unlinkLast() { // assert lock.isHeldByCurrentThread(); Node l = last; If (l == null) // The list is not initialized, there are no elements in the queue, return null; Node p = l.prev; E item = l.item; L.tem = null; // Save the item of the trailing node. // the prevn attribute can be used to indicate that the item has been deleted. // help GC last = p; If (p == null)// If (p == null)// If (p == null)// If (p == null) Else there are at least two nodes (elements) in the linked list before deleting the last node. // Set next for the new tail node to null(tail node has no successors) –count; // Number of elements minus 1 notfull.signal (); // Wake up a thread waiting for “not full” condition return item; } Duplicate code
pollLast()
The pollLast method is similar to takeLast, but pollLast returns NULL when it detects that the queue is empty and does not block the wait.
public E pollLast() { final ReentrantLock lock = this.lock; lock.lock(); try { return unlinkLast(); } finally { lock.unlock(); }} Copy the codeCopy the codepollLast(long timeout, TimeUnit unit)
A version of takeLast that can be thought of as timeout returns NULL if it cannot exit the queue before timeout.
public E pollLast(long timeout, TimeUnit unit) throws InterruptedException { long nanos = unit.toNanos(timeout); final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { E x; while ( (x = unlinkLast()) == null) { if (nanos <= 0) return null; nanos = notEmpty.awaitNanos(nanos); } return x; } finally { lock.unlock(); }} Copy the codeCopy the coderemoveLast()
RemoveLast delegates the pollLast implementation directly and throws NoSuchElementException if the queue is empty.
public E removeLast() { E x = pollLast(); if (x == null) throw new NoSuchElementException(); return x; } Duplicate codeCopy the codeDeletes the specified element
The remove and removeFirstOccurrence methods both look backwards from the head of the queue and remove a given element at its first occurrence. RemoveLastOccurrence looks forward from the end of the queue and deletes a given element at its first occurrence.
remove(Object o)
public boolean remove(Object o) { return removeFirstOccurrence(o); } Duplicate codeCopy the coderemoveFirstOccurrence(Object o)
public boolean removeFirstOccurrence(Object o) { if (o == null) return false; final ReentrantLock lock = this.lock; lock.lock(); try { for (Node<E> p = first; p ! = null; P = p.ext) {// Start from the queue head and look back if (o.edquals (p.item)) {unlink(p); Return true; } } return false; } finally { lock.unlock(); }} Copy the codeCopy the coderemoveLastOccurrence(Object o)
public boolean removeLastOccurrence(Object o) { if (o == null) return false; final ReentrantLock lock = this.lock; lock.lock(); try { for (Node<E> p = last; p ! = null; P = p.rev) {// The end of the queue starts to look forward if (o.quals (p.tem)) {unlink(p); return true; } } return false; } finally { lock.unlock(); }} Copy the codeCopy the codeUnlink () removes a node from the linked list
void unlink(Node<E> x) { // assert lock.isHeldByCurrentThread(); Node<E> p = x.prev; Node<E> n = x.next; If (p == null) {// If the node to be deleted is the head node, unlinkFirst(); } else if (n == null) {// If unlinkLast() is the last node; } else {// The node to be deleted is the middle node without the head and tail. // By next and prev attributes, the precursor node P of the node to be deleted and the successor node N of the node to be deleted are directly linked together. The node x to be deleted has been excluded from the linked list. // Set the next attribute of the precursor node of the node to be deleted to the successor node of the node to be deleted. // Set the prev attribute of the successor node of the node to null. They may still be in use by // an iterator. --count; notFull.signal(); }} Copy the codeCopy the codeGets the first and last elements of the queue
Gets the team leader element
-
Element and getFirst return the first element of the queue but do not delete it. NoSuchElementException is thrown if the queue is empty.
-
Peek and peekFirst return the first element of the queue without deleting it, or null if the queue is empty.
public E element() { return getFirst(); }
public E getFirst() { E x = peekFirst(); if (x == null) throw new NoSuchElementException(); return x; }
public E peek() { return peekFirst(); }
public E peekFirst() { final ReentrantLock lock = this.lock; lock.lock(); try { return (first == null) ? null : first.item; } finally { lock.unlock(); }} Copy the code
Gets the end of the queue element
-
GetLast returns the last element of the queue without deleting it, or throws NoSuchElementException if the queue is empty.
-
PeekLast returns the last element of the queue without deleting it, or null if the queue is empty
public E getLast() { E x = peekLast(); if (x == null) throw new NoSuchElementException(); return x; } public E peekLast() { final ReentrantLock lock = this.lock; lock.lock(); try { return (last == null) ? null : last.item; } finally { lock.unlock(); }} Copy the code
Other methods
contains(Object o)
Contains method, which walks through the list and looks for the element in the queue
public boolean contains(Object o) { if (o == null) return false; final ReentrantLock lock = this.lock; lock.lock(); try { for (Node<E> p = first; p ! = null; p = p.next) if (o.equals(p.item)) return true; return false; } finally { lock.unlock(); }} Copy the codeCopy the codesize()
The size method returns the number of elements in the queue
public int size() { final ReentrantLock lock = this.lock; lock.lock(); try { return count; } finally { lock.unlock(); }} Copy the codeCopy the codeclear()
Clear Clears all elements in the queue. Its main logic:
-
Clear all link relationships from start to finish (f.rev = null; f.next = null;) ;
-
First = last = null;
-
Element count set to 0(count = 0);
-
Wake up all threads waiting for the “notFull” condition (notfull.signalall ()).
public void clear() { final ReentrantLock lock = this.lock; lock.lock(); try { for (Node f = first; f ! = null; ) { f.item = null; Node n = f.next; f.prev = null; f.next = null; f = n; } first = last = null; count = 0; notFull.signalAll(); } finally { lock.unlock(); }} Copy the code
The iterator
AbstractItr
AbstractItrIs to realize theIteratorInterface that provides many default implementations of iterators, which are pre-iteratorsItrAnd a post-order traversal iteratorDescendingItrThe parent class. 支那
Member variables
Node<E> next; // Next iteration node E nextItem; // Next () return element private Node<E> lastRet; // Copy the code from the last iterationCopy the codeA constructor
The constructor initializes the next and nextItem properties
AbstractItr() { // set to initial position final ReentrantLock lock = LinkedBlockingDeque.this.lock; lock.lock(); try { next = firstNode(); nextItem = (next == null) ? null : next.item; } finally { lock.unlock(); }} Copy the codeCopy the codeAbstract methods
The abstract methods firstNode and nextNode return the first and nextNode iterated by the iterator, respectively
abstract Node<E> firstNode(); abstract Node<E> nextNode(Node<E> n); Copy the codeCopy the codehasNext()
HasNext () determines whether there are any subsequent elements based on whether the next attribute is empty
public boolean hasNext() { return next ! = null; } Duplicate codeCopy the codenext()
Next () returns the next element
public E next() { if (next == null) throw new NoSuchElementException(); lastRet = next; // Next as the node of the last iteration E x = nextItem; advance(); // Update next and nextItem properties return x; } Duplicate codeCopy the codeadvance()
The advance() method is used to update next and nextItem properties
void advance() { final ReentrantLock lock = LinkedBlockingDeque.this.lock; lock.lock(); try { // assert next ! = null; next = succ(next); nextItem = (next == null) ? null : next.item; } finally { lock.unlock(); }} Copy the codeCopy the codesucc()
Succ returns the successor node of the specified node
private Node<E> succ(Node<E> n) { // Chains of deleted nodes ending in null or self-links // are possible if multiple interior nodes are removed. for (;;) { Node<E> s = nextNode(n); If (s == null) return null; if (s == null) return null; if (s == null) return null; else if (s.item ! = null) // item of s is not null, return s; Else if (s ==n) // s.tem ==null and n.ext ==n //item is empty, next attribute is self-indicating, indicating that the original head (tail) node n has been logically deleted, // Get the latest first(last) return firstNode(); else //s.item==null && n.next! =n // if item is empty but next is not self-referential, it means that the node S is in the middle of the list (not the head and tail) and has been deleted on logic S, // (it is possible that the remove(Object) method removed the element in the middle of the queue). }} Copy the codeCopy the coderemove()
The remove method removes the elements of the current iteration, similar to the remove method of an external class.
public void remove() { Node<E> n = lastRet; if (n == null) throw new IllegalStateException(); lastRet = null; / / set to null lastRet, may indicate the element node to be deleted final already lock = LinkedBlockingDeque. Enclosing the lock; lock.lock(); try { if (n.item ! = null) unlink(n); } finally {lock.unlock(); }} Copy the codeCopy the codeItr and DescendingItr
Both Itr and DescendingItr implement abstract methods of type firstNode and nextNode. Itr stands for antecedent iterator, iterating backwards from the beginning node, firstNode returning the firstNode, and nextNode returning the successors of the specified node. DescendingItr represents the DescendingItr iterator, iterating forward from the last node, firstNode returning the last node, and nextNode returning the firstNode of the specified node
/** Forward iterator */ private class Itr extends AbstractItr { Node<E> firstNode() { return first; } Node<E> nextNode(Node<E> n) { return n.next; } } /** Descending iterator */ private class DescendingItr extends AbstractItr { Node<E> firstNode() { return last; } Node<E> nextNode(Node<E> n) { return n.prev; }} Copy the codeCopy the codeThe sample Demo
package com.niuh.deque;
import java.util.Iterator;
import java.util.concurrent.LinkedBlockingDeque;
/**
* <p>
* LinkedBlockingDeque示例
* </p>
*/
public class LinkedBlockingDequeDemo {
public static void main(String[] args) {
/**
* 1.1、LinkedBlockingDeque():
* 创建一个容量为 Integer.MAX_VALUE 的 LinkedBlockingDeque。
* 1.2、LinkedBlockingDeque(int capacity):
* 创建一个具有给定（固定）容量的 LinkedBlockingDeque。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque = new LinkedBlockingDeque<>();
/**
* 1、add(E e):在不违反容量限制的情况下，将指定的元素插入此双端队列的末尾，返回值为Boolean。
*/
Boolean addBoolean = linkedBlockingDeque.add(5);
System.out.println("是否添加成功：" + addBoolean);
/**
* 2、addFirst(E e)：如果立即可行且不违反容量限制，则将指定的元素插入此双端队列的开头；
* 如果当前没有空间可用，则抛出 IllegalStateException。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque1 = new LinkedBlockingDeque<>();
linkedBlockingDeque1.addFirst(1);
linkedBlockingDeque1.addFirst(2);
linkedBlockingDeque1.addFirst(3);
/**
* 3、iterator()：返回在此双端队列元素上以恰当顺序进行迭代的迭代器。
*/
Iterator<Integer> iterator = linkedBlockingDeque1.iterator();
while (iterator.hasNext()) {
System.out.println("Iterator的addFirst结果：" + iterator.next());
}
/**
* 4、addLast(E e) ：如果立即可行且不违反容量限制，则将指定的元素插入此双端队列的末尾；
* 如果当前没有空间可用，则抛出 IllegalStateException
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque2 = new LinkedBlockingDeque<>();
linkedBlockingDeque2.addLast(1);
linkedBlockingDeque2.addLast(2);
linkedBlockingDeque2.addLast(3);
Iterator<Integer> iterator1 = linkedBlockingDeque2.iterator();
while (iterator1.hasNext()) {
System.out.println("Iterator的addLast结果：" + iterator1.next());
}
/**
* 5、clear()：以原子方式 (atomically) 从此双端队列移除所有元素。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque3 = new LinkedBlockingDeque<>();
linkedBlockingDeque3.add(1);
linkedBlockingDeque3.add(2);
linkedBlockingDeque3.add(3);
linkedBlockingDeque3.clear();
System.out.println("================");
Iterator<Integer> iterator2 = linkedBlockingDeque3.iterator();
while (iterator2.hasNext()) {
System.out.println("Iterator的clear结果：" + iterator2.next());
}
System.out.println("================");
/**
* 6、contains(Object o) ：如果此双端队列包含指定的元素，则返回 true
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque4 = new LinkedBlockingDeque<>();
linkedBlockingDeque4.add(1);
linkedBlockingDeque4.add(2);
linkedBlockingDeque4.add(3);
Boolean contains3Boolean = linkedBlockingDeque4.contains(3);
Boolean contains4Boolean = linkedBlockingDeque4.contains(4);
System.out.println("是否包含3：" + contains3Boolean + " 是否包含4：" + contains4Boolean);
/**
* 7、element()：获取但不移除此双端队列表示的队列的头部
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque5 = new LinkedBlockingDeque<>();
linkedBlockingDeque5.add(1);
linkedBlockingDeque5.add(2);
linkedBlockingDeque5.add(3);
Integer elementResult = linkedBlockingDeque5.element();
System.out.println("队列的头部: " + elementResult);
/**
* 8、getFirst() ：获取，但不移除此双端队列的第一个元素。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque6 = new LinkedBlockingDeque<>();
linkedBlockingDeque6.add(1);
linkedBlockingDeque6.add(2);
linkedBlockingDeque6.add(3);
Integer firstResult = linkedBlockingDeque6.getFirst();
System.out.println("双端队列的第一个元素: " + firstResult);
/**
* 9、 getLast() :获取，但不移除此双端队列的最后一个元素
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque7 = new LinkedBlockingDeque<>();
linkedBlockingDeque7.add(3);
linkedBlockingDeque7.add(4);
linkedBlockingDeque7.add(5);
Integer lastResult = linkedBlockingDeque7.getLast();
System.out.println("双端队列的最后一个元素: " + lastResult);
/**
* 10.1、offer(E e) :如果立即可行且不违反容量限制，
* 则将指定的元素插入此双端队列表示的队列中（即此双端队列的尾部），
* 并在成功时返回 true；如果当前没有空间可用，则返回 false
*
* 10.2、offer(E e, long timeout, TimeUnit unit) :
* 将指定的元素插入此双端队列表示的队列中（即此双端队列的尾部），
* 必要时将在指定的等待时间内一直等待可用空间,返回值为Boolean。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque8 = new LinkedBlockingDeque<>();
linkedBlockingDeque8.offer(1);
linkedBlockingDeque8.offer(2);
linkedBlockingDeque8.offer(3);
Iterator<Integer> iterator3 = linkedBlockingDeque8.iterator();
while (iterator3.hasNext()) {
System.out.println("Iterator的offer结果：" + iterator3.next());
}
/**
* 11.1、offerFirst(E e) ：
* 如果立即可行且不违反容量限制，则将指定的元素插入此双端队列的开头，
* 并在成功时返回 true；如果当前没有空间可用，则返回 false。
* 11.2、fferFirst(E e, long timeout, TimeUnit unit)：
* 将指定的元素插入此双端队列的开头，必要时将在指定的等待时间内等待可用空间。
* 返回值为Boolean。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque9 = new LinkedBlockingDeque<>();
linkedBlockingDeque9.offerFirst(1);
linkedBlockingDeque9.offerFirst(2);
linkedBlockingDeque9.offerFirst(3);
Iterator<Integer> iterator4 = linkedBlockingDeque9.iterator();
while (iterator4.hasNext()) {
System.out.println("Iterator的offerFirst结果：" + iterator4.next());
}
/**
* 12.1、offerLast(E e):
* 如果立即可行且不违反容量限制，则将指定的元素插入此双端队列的末尾，并在成功时返回 true；如果当前没有空间可用，则返回 false。
* 12.2、offerLast(E e, long timeout, TimeUnit unit):
* 将指定的元素插入此双端队列的末尾，必要时将在指定的等待时间内等待可用空间。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque10 = new LinkedBlockingDeque<>();
linkedBlockingDeque10.offerLast(1);
linkedBlockingDeque10.offerLast(2);
linkedBlockingDeque10.offerLast(3);
Iterator<Integer> iterator5 = linkedBlockingDeque10.iterator();
while (iterator5.hasNext()) {
System.out.println("Iterator的offerLast结果：" + iterator5.next());
}
/**
* 13、peek():获取但不移除此双端队列表示的队列的头部（即此双端队列的第一个元素）；
* 如果此双端队列为空，则返回 null
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque11 = new LinkedBlockingDeque<>();
linkedBlockingDeque11.add(1);
linkedBlockingDeque11.add(2);
linkedBlockingDeque11.add(3);
Integer peekResult = linkedBlockingDeque11.peek();
System.out.println("peekResult的结果：" + peekResult);
/**
* 14、peekFirst():获取，但不移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque12 = new LinkedBlockingDeque<>();
linkedBlockingDeque12.add(3);
linkedBlockingDeque12.add(4);
linkedBlockingDeque12.add(5);
Integer peekFirstResult = linkedBlockingDeque12.peekFirst();
System.out.println("peekFirstResult的结果：" + peekFirstResult);
/**
* 15、peekLast() ：获取，但不移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque13 = new LinkedBlockingDeque<>();
linkedBlockingDeque13.add(6);
linkedBlockingDeque13.add(7);
linkedBlockingDeque13.add(8);
Integer peekLastResult = linkedBlockingDeque13.peekLast();
System.out.println("peekLastResult的结果：" + peekLastResult);
/**
* 16.1、poll() :获取并移除此双端队列表示的队列的头部（即此双端队列的第一个元素）；
* 如果此双端队列为空，则返回 null。
* 16.2、poll(long timeout, TimeUnit unit)：
* 获取并移除此双端队列表示的队列的头部（即此双端队列的第一个元素），
* 如有必要将在指定的等待时间内等待可用元素。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque14 = new LinkedBlockingDeque<>();
linkedBlockingDeque14.add(9);
linkedBlockingDeque14.add(10);
linkedBlockingDeque14.add(11);
Integer pollResult = linkedBlockingDeque14.poll();
System.out.println("peekLastResult的结果：" + pollResult);
System.out.println("linkedBlockingDeque14是否还包含9：" + linkedBlockingDeque14.contains(9));
/**
* 17.1、pollFirst() ：
* 获取并移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。
* 17.2、pollFirst(long timeout, TimeUnit unit) :
* 获取并移除此双端队列的第一个元素，必要时将在指定的等待时间等待可用元素。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque15 = new LinkedBlockingDeque<>();
linkedBlockingDeque15.addFirst(9);
linkedBlockingDeque15.addFirst(10);
linkedBlockingDeque15.addFirst(11);
Integer pollFirstResult = linkedBlockingDeque15.pollFirst();
System.out.println("pollFirstResult的结果：" + pollFirstResult);
System.out.println("linkedBlockingDeque15是否还包含11：" + linkedBlockingDeque15.contains(11));
/**
* 18.1、pollLast()
* 获取并移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。
* 18.2、pollLast(long timeout, TimeUnit unit)
* 获取并移除此双端队列的最后一个元素，必要时将在指定的等待时间内等待可用元素。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque16 = new LinkedBlockingDeque<>();
linkedBlockingDeque16.add(9);
linkedBlockingDeque16.add(10);
linkedBlockingDeque16.add(11);
Integer pollLastResult = linkedBlockingDeque16.pollLast();
System.out.println("pollLastResult的结果：" + pollLastResult);
System.out.println("linkedBlockingDeque16是否还包含11：" + linkedBlockingDeque16.contains(11));
/**
* 19、 pop() :从此双端队列所表示的堆栈中弹出一个元素（移除效果）
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque17 = new LinkedBlockingDeque<>();
linkedBlockingDeque17.addFirst(1);
linkedBlockingDeque17.addFirst(2);
linkedBlockingDeque17.addFirst(3);
Integer pop1Result = linkedBlockingDeque17.pop();
System.out.println("pop2Result的结果：" + pop1Result);
Integer pop2Result = linkedBlockingDeque17.pop();
System.out.println("pop2Result的结果：" + pop2Result);
System.out.println("linkedBlockingDeque17是否还包含2：" + linkedBlockingDeque17.contains(2));
/**
* 20、push(E e) ：将元素推入此双端队列表示的栈。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque18 = new LinkedBlockingDeque<>();
linkedBlockingDeque18.push(1);
linkedBlockingDeque18.push(2);
linkedBlockingDeque18.push(3);
Iterator<Integer> iterator6 = linkedBlockingDeque18.iterator();
while (iterator6.hasNext()) {
System.out.println("Iterator的push结果：" + iterator6.next());
}
/**
* 21、put(E e) :将指定的元素插入此双端队列表示的队列中（即此双端队列的尾部），
* 必要时将一直等待可用空间。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque19 = new LinkedBlockingDeque<>();
try {
linkedBlockingDeque19.put(1);
linkedBlockingDeque19.put(2);
linkedBlockingDeque19.put(3);
} catch (InterruptedException e) {
e.printStackTrace();
}
Iterator<Integer> iterator7 = linkedBlockingDeque19.iterator();
while (iterator7.hasNext()) {
System.out.println("Iterator的put结果：" + iterator7.next());
}
/**
* 22、putFirst(E e) :将指定的元素插入此双端队列的开头，必要时将一直等待可用空间。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque20 = new LinkedBlockingDeque<>();
try {
linkedBlockingDeque20.putFirst(1);
linkedBlockingDeque20.putFirst(2);
linkedBlockingDeque20.putFirst(3);
} catch (InterruptedException e) {
e.printStackTrace();
}
Iterator<Integer> iterator8 = linkedBlockingDeque20.iterator();
while (iterator8.hasNext()) {
System.out.println("Iterator的putFirst结果：" + iterator8.next());
}
/**
* 23、putLast(E e) :将指定的元素插入此双端队列的末尾，必要时将一直等待可用空间。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque21 = new LinkedBlockingDeque<>();
try {
linkedBlockingDeque21.putLast(1);
linkedBlockingDeque21.putLast(2);
linkedBlockingDeque21.putLast(3);
} catch (InterruptedException e) {
e.printStackTrace();
}
Iterator<Integer> iterator9 = linkedBlockingDeque21.iterator();
while (iterator9.hasNext()) {
System.out.println("Iterator的putLast结果：" + iterator9.next());
}
/**
* 24、remove():获取并移除此双端队列表示的队列的头部。返回一个E
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque22 = new LinkedBlockingDeque<>();
linkedBlockingDeque22.addFirst(1);
linkedBlockingDeque22.addFirst(2);
linkedBlockingDeque22.addFirst(3);
Integer removeResult = linkedBlockingDeque22.remove();
System.out.println("removeResult的结果：" + removeResult);
System.out.println("linkedBlockingDeque22是否还包含3：" + linkedBlockingDeque22.contains(3));
/**
* 25、remove(Object o) :从此双端队列移除第一次出现的指定元素,返回值为Boolean。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque23 = new LinkedBlockingDeque<>();
linkedBlockingDeque23.addFirst(1);
linkedBlockingDeque23.addFirst(2);
linkedBlockingDeque23.addFirst(3);
Boolean removeBoolean = linkedBlockingDeque23.remove(3);
System.out.println("是否remove了3 ：" + removeBoolean);
/**
* 26、removeFirst():获取并移除此双端队列第一个元素。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque24 = new LinkedBlockingDeque<>();
linkedBlockingDeque24.addLast(1);
linkedBlockingDeque24.addLast(2);
linkedBlockingDeque24.addLast(3);
Integer removeFirstResult = linkedBlockingDeque24.removeFirst();
System.out.println("removeFirstResult：" + removeFirstResult);
System.out.println("linkedBlockingDeque24是否还包含1：" + linkedBlockingDeque24.contains(1));
/**
* 27、 removeLast():获取并移除此双端队列的最后一个元素。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque25 = new LinkedBlockingDeque<>();
linkedBlockingDeque25.addLast(4);
linkedBlockingDeque25.addLast(5);
linkedBlockingDeque25.addLast(6);
Integer removeLastResult = linkedBlockingDeque25.removeLast();
System.out.println("removeLastResult：" + removeLastResult);
System.out.println("linkedBlockingDeque25是否还包含6：" + linkedBlockingDeque25.contains(6));
/**
* 28、take():获取并移除此双端队列表示的队列的头部（即此双端队列的第一个元素），
* 必要时将一直等待可用元素。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque26 = new LinkedBlockingDeque<>();
linkedBlockingDeque26.push(4);
linkedBlockingDeque26.push(5);
linkedBlockingDeque26.push(6);
Integer takeResult = null;
try {
takeResult = linkedBlockingDeque26.take();
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("takeResult：" + takeResult);
System.out.println("linkedBlockingDeque26是否还包含6：" + linkedBlockingDeque26.contains(6));
/**
* 29、takeFirst() :获取并移除此双端队列的第一个元素，必要时将一直等待可用元素。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque27 = new LinkedBlockingDeque<>();
linkedBlockingDeque27.push(7);
linkedBlockingDeque27.push(8);
linkedBlockingDeque27.push(9);
Integer takeFirstResult = null;
try {
takeFirstResult = linkedBlockingDeque27.takeFirst();
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("takeFirst：" + takeFirstResult);
System.out.println("linkedBlockingDeque27是否还包含9：" + linkedBlockingDeque27.contains(9));
/**
* 30、takeLast():获取并移除此双端队列的最后一个元素，必要时将一直等待可用元素。
*/
LinkedBlockingDeque<Integer> linkedBlockingDeque28 = new LinkedBlockingDeque<>();
linkedBlockingDeque28.push(10);
linkedBlockingDeque28.push(11);
linkedBlockingDeque28.push(12);
Integer takeLastResult = null;
try {
takeLastResult = linkedBlockingDeque28.takeLast();
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("takeLastResult：" + takeLastResult);
System.out.println("linkedBlockingDeque28是否还包含10：" + linkedBlockingDeque28.contains(10));
}
}
复制代码
Copy the codeconclusion
- The internal data structure of LinkedBlockingDeque is a two-way linked list. It can insert and remove nodes (elements) at the beginning and end, and it can walk through the list in both directions because each node holds references to its predecessor and its successor. It can also be used in job-stealing algorithms because it can be outqueued in both its head and tail positions.
- LinkedBlockingDeque is null and uninitialized after constructor initialization. After the constructor initializes LinkedBlockingQueue, the first and last nodes are initialized and point to the same node (item null).
- First, the header of LinkedBlockingDeque, holds elements. First. Item is never empty; First, the header of LinkedBlockingQueue, does not hold elements, first.item is always empty, and first.next, the successor of the header, holds the first element in the list.
- As with LinkedBlockingQueue, LinkedBlockingDeque uses the next (prev) attribute to self-index that the node has been logically removed after the original header (tail) has left the queue;
LinkedBlockingDeque is different from LinkedList
package com.niuh.deque; import java.util.Iterator; import java.util.LinkedList; import java.util.Queue; import java.util.concurrent.LinkedBlockingDeque; /* * LinkedBlockingDeque is a "thread-safe" queue, while LinkedList is a non-thread-safe queue. * * Here is an example of "multiple threads operating at the same time and traversing a queue" * (1) The program works when queue is LinkedBlockingDeque. * (2) when the queue is a LinkedList object, the program will produce abnormal ConcurrentModificationException. * * / public class LinkedBlockingDequeRunner {/ / TODO: when the queue is LinkedList object, the program will go wrong. // private static Queue<String> queue = new LinkedList<String>(); private static Queue<String> queue = new LinkedBlockingDeque<String>(); Public static void main(String[] args) {public static void main(String[] args) { new MyThread("A").start(); new MyThread("B").start(); } private static void printAll() { String value; Iterator iter = queue.iterator(); while (iter.hasNext()) { value = (String) iter.next(); System.out.print(value + ", "); } System.out.println(); } private static class MyThread extends Thread { MyThread(String name) { super(name); } @Override public void run() { int i = 0; While (I ++ < 6) {String = thread.currentThread ().getName(); queue.add(val); // Iterate through the queue through "Iterator". printAll(); }}}} Copy codeCopy the codeOutput result:
A1, A1, A2, A1, A2, A3, A1, A2, A3, A4, A1, A2, A3, A4, A5, A1, A2, A3, A4, A5, A6, A1, A2, A3, A4, A5, A6, B1, A1, A2, A3, A4, A5, A6, B1, B2, A1, A2, A3, A4, A5, A6, B1, B2, B3, A1, A2, A3, A4, A5, A6, B1, B2, B3, B4, A1, A2, A3, A4, A5, A6, B1, B2, B3, B4, B5, A1, A2, A3, A4, A5, A6, B1, B2, B3, B4, B5, B6, copy the codeCopy the codeThe result: In the sample application, two threads (thread A and thread B) are started to act on LinkedBlockingDeque:
- In the case of thread A, it takes the “thread name” + “Ordinal number” and adds that string to LinkedBlockingDeque;
- Next, iterate through and output all the elements in the LinkedBlockingDeque.
- Thread B does the same as thread A, except that thread B has A different name than thread A.
- When queue is LinkedBlockingDeque, the program works.
- If change the queue to LinkedList, the program produces ConcurrentModificationException anomalies.
Reference:
Block queue – LinkedBlockingDeque source code analysis