I left an Easter egg in the 21 Diagrams for Thread-unsafe Collections article, which left out queues, but this time we’re going to focus on the Java Queue family. There are 18 queues. This is probably the most comprehensive and detailed account of Queue on the market.

The main contents of this paper are as follows:

To summarize the blocking queue for you:

Introduction to Queue

1.1 Queue

Hi, everyone. My English name is Queue, and my Chinese name is Queue. I play an important role both in real life and in the computer world

I’m a data structure, you can think of me as an array, and elements come in at one end of me and go out at the other, called the FIFO principle.

I also have two brothers: List and Set, who are sons of Collection, and a distant relative: Map. They are all part of the java.util family

1.2 Real-life scenarios

  • Haidilao row number (the first row number has priority to enter the restaurant)
  • Postmen send letters (box is a queue)

1.3 Scenes in the computer world

  • Message queue RabbitMQ
  • UDP protocol (receivers store messages in a queue and read data from the queue)

Two, from a hillhouse, overview of the overall situation

The 18 types of queues are divided into three categories: interface, abstract, and generic.

Understanding the following inheritance implementation relationships will help you understand the 18 types of queues.

  • Queueinterfaceinheritance CollectionInterface,Collectioninterfaceinheritance 可迭代interface
  • BlockingQueueInterfaces,Dequeinterfaceinheritance Queueinterface
  • AbstractQueueAn abstract classimplementation Queueinterface
  • BlockingDequeInterfaces,TransferQueueinterfaceinheritance BlockingQueueinterface
  • BlockingDequeInterface inheritanceDequeinterface
  • LinkedBlockingDequeclassimplementation BlockingDequeinterface
  • LinkedTransferQueueThe class interfaceimplementation TransferQueueinterface
  • LinkedListClass,ArrayDequeClass,ConcurrentLinkedDequeclassimplementation 了Dequeinterface
  • ArrayBlockingQueueClass,LinkendBlockingQueueClass,LinkedBlockingDequeClass,LinkedTransferQueueClass,SynchronousQueueClass,PriorityBlockQueueClass,DelayQueue classinheritance 了AbstractQueueAbstract classes andimplementationThe BlockingQueue interface
  • PriorityQueueClasses andConcurrentLinkedQueueclassinheritance 了AbstractQueueAn abstract class

Note:

  • Deque: Indicates a double-ended queue.
  • Class implements the interface, using Implements
  • An interface extends an interface, using extends
  • Class extends class, using extends

3. Everything belongs to the Queue interface

2.1 Understand the nature of the Queue interface

  • The Queue interface is a Collection designed to work with elements that have previously been temporarily stored somewhere.

  • In addition to the basic Collection operations, queues provide additional insert, extract, and check operations. Each operation has two forms: if the operation fails, an exception is thrown; If the operation fails, a special value (null or false, depending on the operation) is returned.

  • Queues usually sort elements on a FIFO (first in, first out) basis, but this is not required.

  • Only the priority queue can sort the elements according to the supplied comparator or with normal sort. Regardless of the order, the head of the queue will be removed by calling the remove() or poll() methods. In a FIFO queue, all new elements are inserted at the end of the queue. Other kinds of queues may use different layouts to store elements.

  • Each Queue must specify the sort attribute.

2.2 Core methods of the Queue interface

There are three sets of methods, two for each set of methods. As shown in the figure below:

action Throw exceptions Return special values
Insert add(e) offer(e)
Remove remove() poll
Examine element() peek()

  • (1) For example, the action of adding (Insert) elements, there are two ways: add(e) and offer(e). If the add(e) method fails, an exception is thrown, and if the offer(e) method fails, false is returned. The offer method is used in situations where exceptions are normal, such as bounded queues, where the offer method is preferred. If the queue is full and no element can be added, the offer method returns false, so we know that the queue is full, not the exception thrown by the handle runtime.

  • (2) Similarly, the Remove method throws an exception when the queue is empty, and the poll method returns null. If the removal of the header element is successful, the removed element is returned.

  • (3) Similarly, Examine the (Examine) element action, return the header element(the element originally added), but do not delete the element. If the queue is empty, the element() method throws an exception, and peek() returns false.

  • (4) The Queue interface does not define methods to block the Queue. These methods are defined in the BlockQueue interface.

  • (5) Queue implementations generally do not allow the insertion of null elements. Although some implementations, such as LinkedList, do not prohibit the insertion of null, it is not recommended because null is also used in the special return value of the poll method to indicate that the Queue contains no elements.

Deque interface is available for both ends

4.1 Deeply understand the principle of Deque interface

(1) The concept of Deque: a linear set that supports the insertion and removal of elements at both ends. The name deque is short for double-ended queue and is usually pronounced as deck. Most classes that implement deques have no fixed limit on the number of elements they can contain, and support both bounded and unbounded.

(2) Deque method description:

** Description: **

  • The list contains methods for accessing elements at both ends of the deque, providing methods for inserting, removing, and checking elements.

  • Each of these methods comes in two forms: it throws an exception if the operation fails, and the other method returns a special value (null or false, depending on the operation).

  • The latter form of the insert operation is specifically designed for use in capacity-limited Deque implementations. In most implementations, the insert operation cannot fail, so the latter form of the insert operation can be used.

  • The Deque interface extends the Queue interface to act as a FIFO when using a Deque as a Queue. The element is added to the end of the deque and removed from scratch.

  • A FIFO is equivalent to a Queue as shown in the following table:

For example, the add method of Queue is equivalent to the addLast method of Deque.

  • A Deque can also be used as a LIFO (last in, first out) Stack, an interface that is superior to the traditional Stack class. When used as a stack, the element is pushed to the head of the deque queue, and pop comes out of the head of the queue, pop.

  • The Stack method is the same as the Deque method:

Note: The peek method, whether used as a stack or queue, detects the head of the queue from the queue and returns the first element added. If the first put is 100 and the second put is 200, peek returns 100. As shown in the figure below:

4.1 Which classes implement the Deque interface

  • LinkedList class
  • ArrayDeque class
  • ConcurrentLinkedDeque class
  • LinkedBlockingDeque class

4.2 Which classes inherit the Deque interface

  • The BlockingDeque interface

AbstractQueue abstract class

5.1 In-depth understanding of AbstractQueue abstract class

AbstractQueue is an abstract class that inherits the Queue interface and provides a skeleton implementation of Queue operations.

The add, remove, and Element methods are based on offer, poll, and peek. That is, if it doesn’t work properly, it throws an exception. So let’s see how the AbstactQueue does that.

  • AbstractQueue’s Add method
public boolean add(E e) {
    if (offer(e))
        return true;
    else
        throw new IllegalStateException("Queue full");
}
Copy the code
  • The Remove method of AbstractQueue
public E remove(a) {
    E x = poll();
    if(x ! =null)
        return x;
    else
        throw new NoSuchElementException();
}
Copy the code
  • Element method of AbstractQueue
public E element(a) {
    E x = peek();
    if(x ! =null)
        return x;
    else
        throw new NoSuchElementException();
}
Copy the code

Note:

  • If you inherit from the AbstractQueue abstract class, you must ensure that the offer method does not allow null values to be inserted.

5.2 Which classes inherit from AbstractQueue abstract class

  • ArrayBlockingQueueClass,LinkendBlockingQueueClass,LinkedBlockingDequeClass,LinkedTransferQueueClass,SynchronousQueueClass,PriorityBlockQueueClass,DelayQueue classinheritance 了AbstractQueueAn abstract class
  • PriorityQueueClasses andConcurrentLinkedQueueclassinheritance 了AbstractQueueAn abstract class

Block buffer BlockingQueue interface

BlockingQueue (BlockingQueue)

  • The BlockQueue is full and the PUT operation is blocked

  • The BlockQueue is empty and the Take operation is blocked

BlockingQueue is also a queue that supports blocking insert and remove methods.

(3) Blocked insertion: When the queue is full, the queue blocks the thread that inserted the element until the queue is dissatisfied.

(4) Block removal: When the queue is empty, the thread that gets the element waits for the queue to become non-empty.

(5) Application scenario: producer and consumer. The producer thread adds elements to the queue, the consumer thread removes elements from the queue, and the container for obtaining and storing elements when blocking the queue.

(6) Why to use blocking queue: the rate of producer production is different from that of consumer consumption, so we need to use queue to solve the problem of rate difference. When the queue is full or empty, we need to block production or consumption action to solve the problem of full or empty queue.

6.2 Case Analysis

Thread A adds elements to the Blocking Queue, and thread B removes elements from the Blocking Queue.

  • When the blocking queue is empty(none), fetching elements from the queue will be blocked.
    • Life case: when I went to Haidilao to eat hot pot, no one came to eat hot pot at 8 o ‘clock in the morning, so I had to wait for guests to come.
    • Now there are no elements to add, and the blocking queue is empty, so thread B does not need to take the element out of the queue, so the operation of thread B to get the element is blocked.
  • When the blocking queue is full(all locations have elements), adding elements from the queue will be blocked.
    • The case in the life: when eating hotpot to haidilao, the person is too much, need platoon number, wait for other table to empty out ability to go in.
    • Thread A adds elements to the blocking queue, and the queue is full. Thread B is busy and cannot remove the elements from the blocking queue, so there is no room for the elements to be placed in the blocking queue

6.3 Using BlockingQueue interface

The 10 core methods of the BlockingQueue interface:

The 10 core methods are summarized as follows:

There are three categories of operations: insert, remove, and check.

  • There are four ways to insert:Add, Offer, PUT, offer timeout version.
    • The add method is used specifically to throw exceptions on failure to add. There are four types of exceptions:
      • IllegalStateException– The queue is full
      • ClassCastException– The added element type does not match
      • NullPointerException– The added element is null
      • IllegalArgumentException– Some attributes of the added element do not match
    • The offer method is special for returning false only on an add failure
    • The put method is particularly useful when a blocking queue is full and a producer puts an element into the queue, the queue will block the producer thread until the queue is available or the response interrupts and exits
    • The offer timeout method is particularly useful when the blocking queue is full. If a producer inserts an element into the queue, the queue will block the producer thread for a certain period of time. If the queue is full, the producer thread will exit and return false.
  • There are four ways to remove:Remove, poll, Take, poll timeout version
    • The remove method is special for raising an exception when the removal fails
      • NoSuchElementException– If the queue is empty
    • The poll method is specifically used to return null on a removal failure
    • The take method is used specifically when the blocking queue is empty and the consumer thread removes an element from the queue, the queue will block the consumer thread until the queue is no longer empty
    • In particular, the poll timeout method is used when the blocking queue is empty. If the consumer removes an element from the queue, the queue will block the consumer thread for a long time. If the time exceeds the specified time, the consumer thread will exit and return NULL
  • There are two ways to check:Element, peek,
    • The element method is used to detect the existence of the header element and throws an exception if the queue is empty, otherwise returns the header element.
    • The peek method is used to detect the presence of the header element and returns the special value null if the queue is empty, otherwise the header element is returned.

6.4 What does BlockingQueue do to block inserts and removals?

  • When inserting an element into a queue, if the queue is not available, the blocking producer is mainly done by locksupport.park (this).
  • The park method blocks the current thread and returns only if one of four things happens.
    • When unpark corresponding to park is executed or has been executed. “Executed” means that unpark is executed first, and then park is executed.
    • When the thread is interrupted.
    • Wait for the number of milliseconds specified by the time parameter.
    • When an anomaly occurs, there is no reason for the anomaly.

6.5 Which classes inherit the BlockingQueue interface?

  • BlockingDeque interface – Double end blocking queue
  • TransferQueue interface – TransferQueue

6.6 Which classes implement the BlockingQueue interface?

  • ArrayBlockingQueue class – Bounded blocking queue made up of arrays
  • LinkedBlockingQueue – A bounded blocking queue consisting of linked lists. The default bound size is integer.max_value (2^31-1). The value is very large and is equivalent to unbounded.
  • LinkedBlockingDeque class – a two-way blocking queue consisting of a linked list
  • LinkedTransferQueue class – An unbounded blocking queue made up of linked lists
  • SynchronousQueue – a blocking queue that does not store elements, only one element passes data.
  • LinkedTransferQueue class – An unbounded blocking TransferQueue consisting of a linked list
  • DelayQueue class – A delayed unbounded blocking queue using a priority queue

6.6 Which interfaces the BlockingQueue interface inherits

  • The BlockingQueue interface inherits from the Queue interface and can be used as a Queue

Dual-end BlockingDeque interface

7.1 Understanding BlockDeque from a Schematic diagram

  • The BlockQueue is full and the Take operations on both ends are blocked

  • The BlockQueue is empty and the Take operations on both ends are blocked

7.2 BlockingDeque interface method

BlockingQueue is a combination of BlockingQueue and Deque interface. There are ways to do this:

Example:

Try the following:

LinkedBlockingDeque queue = new LinkedBlockingDeque();
queue.addFirst("test1");
queue.addFirst(300);
queue.addLast("400");
Copy the code

The order of the elements in the final queue is as follows:

300, test1, 400.

I added test1 to the head of the queue, and then I put 300 in front of the head, so 300 is at the top, that’s the head, and then I put 400 at the bottom of the queue, so I get 300, test1, 400.

7.3 BlockDeque and BlockQueue peer methods

7.4 BlockingDeque features

  • Thread safe.
  • Null elements are not allowed.
  • Both unbounded and bounded.

7.5 What interfaces does BlockingDeque inherit?

  • Queue interface, which has the Queue function
  • The Deque interface has the function of dual-end queue
  • BlockingQueue interface that can be used as a BlockingQueue

7.6 Which classes implement the BlockDeque interface?

  • LinkedBlockingDeque

Mission bound TransferQueue interface

8.1 How to understand Transfer?

If a consumer is fetching an element, the element in the queue is passed to the consumer. If there are no consumers, wait for them to spend. I call it the mission imperative queue, and you can’t return until the task is complete.

8.2 Cases in life

  • ** Transfer method for TransferQueue **
    • Yto Courier wants to deliver Xiao Ming’s two express deliveries to the door, and Yunda Courier also wants to deliver Xiao Ming’s two express deliveries to the door. Xiao Ming can only take one at a time, and the Courier must wait for him to take one before continuing to give the second one.
  • TryTransfer method for the TransferQueue
    • Yto Courier wants to deliver Xiao Ming’s two express deliveries to the door, and Yunda Courier also wants to deliver Xiao Ming’s two express deliveries to the door. Finding Xiao Ming not at home, I put the express directly to the rookie station.
  • TryTransfer timeout method for the TransferQueue
    • Yto Courier wants to deliver Xiao Ming’s two express deliveries to the door, and Yunda Courier also wants to deliver Xiao Ming’s two express deliveries to the door. Found that Xiaoming was not at home, so the first five minutes, found that Xiaoming has not come back, put the express directly to the rookie post.

8.3 TransferQueue Mechanism

  • transfer(E e)

    The principle is shown in the figure below:

    • Schematic explanation: The Producer Thread tries to pass element B to the consumer Thread. If there is no consumer Thread, the Producer Thread puts element B into the tail node. And the producer thread waits for element B to be consumed. When element B is consumed, the producer thread returns.
    • If a consumer is currently waiting to receive an element (when the consumer uses the take method or the time-out poll method), the Transfer method can immediately transfer the element passed in by the producer to the consumer.
    • If there are no consumers waiting to receive the element, the Transfer method puts the element on the tail node of the queue and returns until the element has been consumed by the consumer.

  • tryTransfer(E e)

    • Test whether the incoming elements from the producer can be passed directly to the consumer.
    • Returns false if there are no consumers waiting to receive the element.
    • The difference between the method and the Transfer method is that the method returns immediately whether the consumer receives it or not.

  • tryTransfer(E e, long timeout, TimeUnit unit)

    • The tryTransfer method with a time limit.
    • Attempts to pass elements passed in by the producer directly to the consumer.
    • If no consumer consumes the element, wait for the specified time before returning.
    • If no element has been consumed after the timeout, return false.
    • Returns true if the element was consumed within the timeout period.

  • getWaitingConsumerCount()

    • Gets the number of consumers waiting to receive an element through the BlockingQueue.take() method or timeout limit poll method. Approximation.
    • Returns the number of consumers waiting to receive an element.

  • hasWaitingConsumer()

    • Gets whether there is a consumer waiting to receive an element through the BlockingQueue.tabke() method or timeout limit poll method.
    • Returning true means there is at least one waiting consumer.

8.3 Which interfaces does the TransferQueue Interface inherit?

  • BlockingQueue interface that can be used as a BlockingQueue
  • Queue interface, which can be used as a Queue

8.4 Which classes implement the TransferQueue interface?

  • LinkedTranferQueue interface

Priority is given to your PriorityQueue class

9.1 Understanding PriorityQueue

  • It should have been sorted in ascending order

  • In reverse order

  • PriorityQueue is an unbounded blocking queue that supports priority.

  • The default natural order is ascending.

  • You can sort elements by constructing the Comparator parameter.

public PriorityQueue(Comparator<? super E> comparator) {
     this(DEFAULT_INITIAL_CAPACITY, comparator);
}
Copy the code
  • Custom implementation of the comapreTo() method to specify element collation rules.
public Comparator<? super E> comparator() {
    return comparator;
}
Copy the code
  • Null elements are not allowed.
  • Classes that implement the PriorityQueue interface are not guaranteed to be thread safe unless it is PriorityBlockingQueue.
  • The iterator for PriorityQueue is not guaranteed to traverse elements in any particular order, so consider using it if ordered traversal is requiredArrays.sort(pq.toArray).
  • Into the column,offer,add) and listing (poll,remove()Of order log(n)).
  • Remove (Object) and Contains (Object) algorithm time complexity O(n).
  • The algorithm time complexity of PEEK, Element and size is O(1).

9.2 What classes does the PriorityQueue class inherit?

  • AbstractQueue is an abstract class with queue functionality

9.2 What interfaces does the PriorityQueue class implement?

  • Queue interface, which can be used as a Queue.

10, two-way LinkedList class

10.1 Structure of LinkedList

  • LinkedList implements the List and Deque interfaces, so it is a double-linked List structure that can be used as a stack, queue, or bidirectional queue.
  • Each element of a bidirectional list has three integer values: element, backward nodal link, and forward nodal link

Let’s look at the Node class Node

private static class Node<E> {
    E item; / / element
    Node<E> next; // Backward node link
    Node<E> prev; // Link forward nodes

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev; }}Copy the code

10.2 Differences with ArrayList

  • 1. The efficiency of adding and deleting a LinkedList is relatively high, while the efficiency of finding and modifying a LinkedList is relatively low.

  • 2. You are advised to use ArrayList in the following situations

    • Frequently access an element in a list.
    • Add elements only at the beginning and end of the list.

  • Use a LinkedList for the following situations

    • Frequently add and remove elements at the beginning, middle, and end of the list.
    • You need to iterate through the list to access the elements.

10.3 LinkedList is not thread safe

LinkedList is not thread-safe, so you can make it thread-safe in the following ways.

List list = Collections.synchronizedList(new LinkedList<>());
Copy the code

10.4 Linkedin List family relationship

  • LinkedList inherits from AbstractSequentialList class.

  • LinkedList implements the Queue interface and can be used as a Queue.

  • LinkedList inherits the AbstractQueue abstract class and has the functionality of a queue.

  • LinkedList implements the List interface to perform list-related operations.

  • LinkedList implements the Deque interface and can be used as a bidirectional queue.

  • LinkedList implements the Cloneable interface for cloning.

  • LinkedList implements the Java.io.Serializable interface to support serialization, which can be serialized to transport.

11. Concurrent security ConcurrentLinkedQueue class

11.1 understand ConcurrentLinkedQueue

  • ConcurrentLinked is a thread-safe fifO unbounded queue composed of a linked list structure.
  • ConcurrentLinkedQueue is a good choice when multiple threads want to share access collections.
  • Null elements are not allowed
  • Support concurrent non-blocking access security queue, don’t throw ConcurrentModifiationException anomalies.
  • The size method is not accurate because the queue may be adding elements while the collection is being counted, resulting in inaccurate statistics.
  • AddAll, removeAll, retainAll, containsAll, equals, and toArray in batches are not guaranteed to be atomic.
  • Add the element happen-before other threads remove the element.
  • The usage is as follows:
ConcurrentLinkedQueue queue = new ConcurrentLinkedQueue();
BuildingBlockWithName buildingBlock = new BuildingBlockWithName("Triangle"."A");
concurrentLinkedQueue.add(buildingBlock);
Copy the code

11.2 What classes does the ConcurrentLinkedQueue class inherit?

  • AbstractQueue is an abstract class with queue functionality

11.3 What interfaces does the ConcurrentLinkedQueue class implement?

  • Queue interface, which can be used as a Queue

ArrayDeque class

12.1 understand ArrayDeque

  • A double-ended queue consisting of arrays.
  • There is no capacity limit. Expand the capacity as required.
  • It’s not thread safe.
  • Inserting null elements is disallowed.
  • When used as a stack, it is faster than a stack and when used as a queue, it is faster than a LinkList.
  • The algorithm time complexity of most methods is O(1).
  • Remove, removeFirstOccurrence, removeLastOccurrence, Contains, Remove and batch operation algorithm time complexity O(n)

12.2 Usage

Create an ArrayDeque and add elements to the end of the ArrayDeque team.

ArrayDeque arrayDeque = new ArrayDeque();
for (int i = 0; i < 50; i++) {
    arrayDeque.add(buildingBlock); The add method is equivalent to the addLast method
}
Copy the code

12.3 What interfaces are implemented by ArrayDeque

  • Deque interface – Can be used for dual-end queues

Bidirectional concurrent ConcurrentLinkedDeque class

13.1 Understand ConcurrentLinkedDeque

  • A two-way unbounded blocking queue consisting of a linked list structure
  • A thread-safe class where insert, delete, and access operations can be performed concurrently
  • Null elements are not allowed
  • In concurrent scenarios, it is not accurate to calculate the size of the queue because elements may be added to the queue during the calculation.
  • AddAll, removeAll, retainAll, containsAll, equals, and toArray in batches are not guaranteed to be atomic.

13.2 ConcurrentLinkedDeque Example

Create two blocks: triangle, quadrilateral, and add to the queue:

BuildingBlockWithName buildingBlock1 = new BuildingBlockWithName("Triangle"."A");
BuildingBlockWithName buildingBlock2 = new BuildingBlockWithName(Quadrilateral."B");
ConcurrentLinkedDeque concurrentLinkedDeque = new ConcurrentLinkedDeque();
concurrentLinkedDeque.addFirst(buildingBlock1);
concurrentLinkedDeque.addLast(buildingBlock2);
// Result: order: triangle, quadrilateral
Copy the code

13.3 Which interfaces are implemented by ConcurrentLinkedDeque

  • Deque interface – Can be used for dual-end queues

ArrayBlockingQueue ArrayBlockingQueue

14.1 understand ArrayBlockingQueue

  • ArrayBlockingQueue is a bounded blocking queue implemented as an array.
  • The insertion operation is blocked when the queue is slow, and the removal operation is blocked when the queue is empty.
  • Elements are sorted on a first-in, first-out (FIFO) basis.
  • Thread fair access to queues is not guaranteed by default.
  • Fair access queue: Access the queue according to the blocking order, that is, the first blocked line first access the queue.
  • Unfairness is unfair to threads that wait first. When a queue is available, blocked threads can compete for access to the queue. The thread that might block first is the last to access the access queue.
  • Fairness reduces throughput.

14.2 Example of ArrayBlockingQueue

Create two blocks: triangle, quadrilateral, and add to the queue:

BuildingBlockWithName buildingBlock1 = new BuildingBlockWithName("Triangle"."A");
BuildingBlockWithName buildingBlock2 = new BuildingBlockWithName(Quadrilateral."B");
ArrayBlockingQueue arrayBlockingQueue = new ArrayBlockingQueue(100.true);
arrayBlockingQueue.add(buildingBlock1);
arrayBlockingQueue.add(buildingBlock2);
Copy the code

14.3 What interfaces do ArrayBlockQueue implement

  • Deque interface – Can be used for dual-end queues

Linked lists block the LinkedBlockingQueue class

15.1 understand LinkedBlockingQueue

  • LinkedBlockingQueue has both a single linked list and a bounded blocking queue.
  • The insertion operation is blocked when the queue is slow, and the removal operation is blocked when the queue is empty.
  • The default and maximum length are integer.max_value, equivalent to unbounded (values are very large: 2^31-1).

15.2 LinkedBlockingQueue Example

LinkedList linkedList1 = new LinkedList();
linkedList1.add("A");
linkedList1.add("B");
linkedList1.add("C");
Copy the code

15.3 LinkedBlockingQueue

  • Throughput is usually higher than ArrayBlockingQueue. When creating a thread pool, the runnableTaskQueue parameter is used, and the blocking queue that holds the pending tasks can be selected as LinkedBlockingQueue. Static factory methods Executors. NewFixedThreadPool () using the queue.

15.4 What interfaces are implemented by LinkedBlockingQueue

  • LinkedBlockingQueue inherits from the BlockingQueue class and can be used as a BlockingQueue
  • LinkedBlockingQueue inherits the AbstractQueue abstract class and has queue functionality.
  • LinkedBlockingQueue implements the Java.io.Serializable interface to support serialization, which can be serialized to transport.

LinkedBlockingDeque class

Understand the LinkedBlockingDeque class

  • Block queue + LinkedBlockingDeque = block queue + LinkedBlockingDeque + double end access
  • Thread safe.
  • When multiple threads join the queue at the same time, the competition is reduced by half because there is an extra access point.
  • The default capacity is integer.max_value. The capacity can be specified.

16.2 LinkedBlockingDeque application scenarios

LinkedBlockingDeque can be used in “work steal” mode.

Job stealing algorithm: When a thread is idle, it steals tasks from the back of the queue of other threads to help it execute.

16.3 What interfaces are implemented by LinkedBlockingDeque

  • LinkedBlockingDeque inherits from the BlockingDeque class and can be used as a blocking queue
  • LinkedBlockingDeque inherits AbstractQueue abstract class and has queue functionality.
  • LinkedBlockingDeque implements the Java.io.Serializable interface to support serialization, and can be serialized to transport.

Linked lists block LinkedTransferQueue class

17.1 Understanding the LinkedTransferQueue class

LinkedTransferQueue = Blocking queue + linked list structure +TransferQueue

The LinkedTransferQueue interface is similar to the TransferQueue interface, except that it has the ability to block inserts and removes, and the structure is a linked list structure.

The TransferQueue show you three examples of how TransferQueue works, and you can look back at TransferQueue.

17.2 The LinkedTransferQueue interface has five more methods than other blocking queues

  • transfer(E e)
  • tryTransfer(E e)
  • tryTransfer(E e, long timeout, TimeUnit unit)
  • getWaitingConsumerCount()
  • hasWaitingConsumer()

17.3 LinkedTransferQueue code example

  • Create A LinkedTransferQueue, and producer 1 adds A, B, and C to the queue in turn

  • Producer 2 adds D, E, and F to the queue one by one

  • Consumers in turn consume elements from the head of the queue. Before each consumption, sleep 2s to demonstrate whether the transfer method waits.

  • The results
producers1Transfer A Producer2After transfer D 2S... Consumers take A producer1Put B 2s... Consumer TAKE D producer2Transfer E 2s after... A consumer B producer1     transfer C 
Copy the code
  • Code execution result analysis

(1) First, producer threads 1 and 2 call the transfer method to transfer A and D, and find that there is no consumer thread to receive them, so they are blocked.

(2) The consumer line takes away A after 2s, and then the producer 1 is released to continue the execution and transfer element B. It finds that there is no consumer consumption again, so it waits.

(3) After the consumer line passes 2 seconds, the D element at the top of the queue is taken away, and the producer 2 continues to execute and transmit the element E, but finds that there is no consumer, so it waits.

(4) After the consumer line passes 2s, the B element at the top of the queue is taken away, and the producer 1 transmits THE C element, waiting for the consumer to take it away.

(5) The consumer is no longer consuming, so both producer 1 and producer 2 are blocked, neither element C nor element E has been taken away, and the transmission of element F of producer 2 has not started because it is waiting for element D to be taken away.

(6) Check that there are C and E elements in the queue, and that E is at the top of the queue.

17.4 What interfaces are implemented by LinkedTransferQueue

  • LinkedBlockingDeque inherits from the BlockingQeque class and can be used as a blocking queue
  • LinkedBlockingDeque inherits AbstractQueue abstract class and has queue functionality.

18. Passer SynchronousQueue class

18.1 Understanding SynchronousQueue

  • I call SynchronousQueue a “passer.” Imagine this scene: Ming holds a basketball and wants to pass it to Floret. If floret doesn’t take the ball away, Ming can’t take another ball.

  • SynchronousQueue is responsible for passing the producer-generated data to the consumer thread.

  • The SynchronousQueue itself does not store data, and the queue is empty when put is called.

  • Every PUT operation must wait for a take operation to complete, or elements cannot be added.

  • Suitable for transitive scenarios.

  • Performance is higher than ArrayBlockingQueue and LinkedBlockingQueue.

18.2 SynchronousQueue will sample

We created two threads, one for production and one for consumption

  • The production thread puts the values A, B, and C in sequence

  • The consuming thread uses take to consume the contents of the blocking queue, waiting 5 seconds before each consumption

  • The results
t1     put A 
t2     take A 

5Seconds later... t1 put B t2 take B5Seconds later... t1 put C t2 take CCopy the code

Summary: After putting the first element “A”, the production thread needs to wait for the consumer thread to take “A” before proceeding with code execution.

18.3 Application scenarios of SynchronousQueue

  • Throughput is usually higher than LinkedBlockingQueue. When creating a thread pool, the runnableTaskQueue (task queue) parameter is used, and the blocking queue used to hold tasks waiting to be executed can be selected SynchronousQueue. Static factory methods Executors. NewCachedThreadPool () using the queue

18.4 Differences between SynchronousQueue and LinkedTransferQueue

  • SynchronousQueue does not store elements, while LinkedTransferQueue stores elements.
  • A SynchronousQueue has no elements in it, whereas a LinkedTransferQueue can have multiple stores in the queue waiting for transmission.
  • LinkedTransferQueue also supports dropping to the queue if it cannot be transferred.
  • LinkedTransferQueue also supports that if the transfer fails after a certain period of time, it will be thrown into the queue.

Class PriorityBlockingQueue

19.1 Understanding the PriorityBlockQueue class

  • PriorityBlockQueue = PriorityQueue + BlockingQueue
  • We also talked about the principle of a PriorityQueue, which supports ordering elements.
  • Elements are naturally sorted by default.
  • The CompareTo() method can be customized to specify element collation rules.
  • You can use the constructor to construct the parameter Comparator to sort elements.

19.2 What interfaces are implemented by PriorityBlockQueue

  • LinkedBlockingQueue inherits the BlockingQueue interface and can be used as a BlockingQueue
  • LinkedBlockingQueue inherits the AbstractQueue abstract class and has queue functionality.
  • LinkedBlockingQueue implements the Java.io.Serializable interface to support serialization, which can be serialized to transport.

DelayQueue class

20.1 understand DelayQueue

  • DelayQueue = Delayed + BlockingQueue. Elements in the queue must implement the Delayed interface.
public class DelayQueue<E extends Delayed> extends AbstractQueue<E>
    implements BlockingQueue<E> {
Copy the code
  • When creating an element, you can specify how long it will take to get the current element from the queue. The current element is retrieved from the queue only after the delay expires.

20.2 Source code parsing

  • When adding an element, specify how long it will take to get the element from the queue
public boolean offer(E e, long timeout, TimeUnit unit) {
    return offer(e);
}
Copy the code
  • The poll method that gets the element waits for the delay to pass before getting the element
if (first == null || first.getDelay(NANOSECONDS) > 0)
    return null;
else
    return q.poll();
Copy the code

20.3 Application Scenarios

  • The design of the cache system: you can use a DelayQueue to hold the expiration dates of cached elements. We then query the DelayQueue with a thread loop. Once we can retrieve the elements from the DelayQueue, the cache expires.

  • Scheduled task scheduling: The DelayQueue is used to store the tasks to be executed on the day and the execution time. Once the tasks are obtained from the DelayQueue, the tasks are executed. For example, the TimerQueue in Java is implemented using DelayQueue.

20.4 What interfaces are implemented by DelayQueue

  • DelayQueue implements the BlockingQueue interface, which can be used as a BlockingQueue

This article spent a lot of thought in the above, look at the official English documents, drawing schematic diagrams, writing demo code, typesetting. This is probably the most comprehensive and detailed description of Queue on the market.

❝

Hello, I am Wukong Brother, “7 years of project development experience, full stack engineer, development team leader, love schematic programming underlying principles”. I am writing two PDFS, which are 1, Spring Cloud Practical project (best must pass), 2, Java concurrency must know must be. I also handwritten 2 small program, Java brush small program, PMP brush small program, click on my public number menu to open! In addition, there are 111 architect documents and 1000 Java interview questions, which are all organized into PDF. You can follow the public account “Wukong Chat architecture” and reply to Wukong to get quality information.

❞

“Retweet -> Look -> Like -> Favorites -> Comment!!” Is the biggest support for me!

Java Concurrency Must Know must be series:

1. Counter the interviewer | | 14 zhang diagram is no longer afraid of being asked a volatile!

2. Programmer was despised by his wife in the middle of the night because CAS principle was too simple?

3. The principle of with blocks on ABA | wife incredibly understand again!

4. Cut the finest | 21 picture with you appreciate collection thread unsafe

5.5000 word | 24 picture show you thoroughly understand the 21 kinds of locks in Java