This article has been included at github.com/vipstone/al… Algorithmic diagrams series.
Through the study of the previous article “a detailed explanation of the” queue “, 3 methods of the queue! We know that Queue is first in first out (FIFO), and we can use arrays, linked lists and lists to implement custom queues, so this article we will systematically learn how to implement queues.
Java has many queues, such as ArrayBlockingQueue, LinkedBlockingQueue, PriorityQueue, DelayQueue, SynchronousQueue, etc. What are their functions? How is it classified?
In fact, these queues in Java can be classified from different dimensions, such as blocking and non-blocking, bounded and unbounded, and this paper will be classified from the function of queues, such as priority queues, ordinary queues, double-endian queues, delay queues and so on.
While the focus of this article is on interpreting queues functionally, other categories are also important concepts in Java, so let’s take a look at them first.
Blocking queues and non-blocking queues
Blocking queues provide Blocking put and take methods that are equivalent to offer and poll that can be timed. If the queue is full, the PUT method blocks until there is space to insert elements; If the queue is empty, the take method also blocks until an element is available. The PUT and take methods never block when the queue is never full.
We can tell if the queue is a BlockingQueue from its name, which contains the BlockingQueue keyword, such as the following:
- ArrayBlockingQueue
- LinkedBlockingQueue
- PriorityBlockingQueue
- .
Blocking queue function demonstration
Let’s show what happens when the blocking queue becomes full, using the following code:
import java.util.Date;
import java.util.concurrent.ArrayBlockingQueue;
public class BlockingTest {
public static void main(String[] args) throws InterruptedException {
// Create a blocking queue of length 5
ArrayBlockingQueue q1 = new ArrayBlockingQueue(5);
// Create a new thread to perform the column entry
new Thread(() -> {
// Loop 10 times
for (int i = 0; i < 10; i++) {
try {
q1.put(i);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(new Date() + " | ArrayBlockingQueue Size:" + q1.size());
}
System.out.println(new Date() + " | For End.");
}).start();
// Create a new thread to execute the column
new Thread(() -> {
for (int i = 0; i < 5; i++) {
try {
/ / sleep 1 s
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
if(! q1.isEmpty()) {try {
q1.take(); / / dequeue
} catch(InterruptedException e) { e.printStackTrace(); } } } }).start(); }}Copy the codeThe result of the above code is as follows:
Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:1
Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:2
Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:3
Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:4
Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:5
Mon Oct 19 20:16:13 CST 2020 | ArrayBlockingQueue Size:5
Mon Oct 19 20:16:14 CST 2020 | ArrayBlockingQueue Size:5
Mon Oct 19 20:16:15 CST 2020 | ArrayBlockingQueue Size:5
Mon Oct 19 20:16:16 CST 2020 | ArrayBlockingQueue Size:5
Mon Oct 19 20:16:17 CST 2020 | ArrayBlockingQueue Size:5
Mon Oct 19 20:16:17 CST 2020 | For End.
As you can see from the above results, the ArrayBlockingQueue blocks when the queue is full, and a second passes before a new element is added to the queue after it has been removed from the queue.
Non-blocking queue
A non-blocking queue is a normal queue and will not be included in its nameBlockingQueueKeyword, and it will not containput 和 takeWhen the queue is full, if there are new elements added to the column, it will return an error, and will not block waiting to add elements, as shown in the following figure:
ConcurrentLinkedQueue 和 PriorityQueue.
Bounded and unbounded queues
Bounded queue: refers to a queue that has a fixed size, such as a fixed sizeArrayBlockingQueueOr size zeroSynchronousQueue.
Unbounded queue: Integer.MAX_VALUE is the default value for a queue that is not set to a fixed size, but the default value is integer. MAX_VALUE. So from the user’s point of view, it’s kind of “unbounded.”
Classification by function
Next is the focus of this article, we divide the queue by function, it can be divided into: ordinary queue, priority queue, double-endian queue, delay queue, other queues, etc., next we see separately.
1. Common queue
Queues are basic queues that implement fifO, such as ArrayBlockingQueue and LinkedBlockingQueue, where ArrayBlockingQueue is a normal Queue implemented with arrays, as shown in the figure below:
LinkedBlockingQueueIs a normal queue implemented using a linked list, as shown below:
Commonly used method
Common methods in a normal queue are the following:
- Offer () : adds elements, returns false if the queue is full, inserts and returns true if the queue is not full;
- Poll () : deletes and returns the header element, or null if the queue is empty;
- Add () : Adds elements, which is a simple wrapper around the Offer method and throws an IllegalStateException if the queue is full;
- Remove () : directly remove the header element;
- Put () : adds elements and blocks for insertion if the queue is full;
- Take () : removes and returns the queue head element. When the queue is empty, it blocks waiting.
- Peek () : queries header elements but does not delete them;
- Element () : Simply wraps the peek method. If the header element exists, it is removed without removing it. If not, NoSuchElementException is thrown.
Note: Generally, offer() and poll() methods are used together, put() and take() blocking methods are used together, add() and remove() methods are used together, and offer() and poll() methods are commonly used in programs, so these two methods are friendly. No errors will be reported.
Let’s use LinkedBlockingQueue as an example to demonstrate the use of a normal queue:
import java.util.concurrent.LinkedBlockingQueue;
static class LinkedBlockingQueueTest {
public static void main(String[] args) {
LinkedBlockingQueue queue = new LinkedBlockingQueue();
queue.offer("Hello");
queue.offer("Java");
queue.offer("Chinese Community");
while(! queue.isEmpty()) { System.out.println(queue.poll()); }}}Copy the codeThe result of the above code is as follows:
Hello
Java
The Chinese community
2. Dual-end queues
A Deque is a data structure in which both the head and tail of a queue can join and leave the queue at the same time, as shown in the following figure:
LinkedBlockingDequeThe use of:
import java.util.concurrent.LinkedBlockingDeque;
/** * example of a double-ended queue */
static class LinkedBlockingDequeTest {
public static void main(String[] args) {
// Create a double-ended queue
LinkedBlockingDeque deque = new LinkedBlockingDeque();
deque.offer("offer"); // Insert the first element
deque.offerFirst("offerFirst"); // The header inserts the element
deque.offerLast("offerLast"); // Insert elements at the end of the queue
while(! deque.isEmpty()) {// Iterate over the printSystem.out.println(deque.poll()); }}}Copy the codeThe result of the above code is as follows:
offerFirst
offer
offerLast
3. Priority queue
A PriorityQueue is a special kind of queue. It is not first-in, first-out, but the element with the highest priority gets out first.
Priority queues are implemented based on binary heaps, whose data structure is shown in the following figure:
Because a priority queue is implemented based on a binary heap, it can queue the elements with the highest priority first.
Let’s demonstrate the use of priority queues:
import java.util.PriorityQueue;
public class PriorityQueueTest {
// A custom entity class
static class Viper {
private int id; // id
private String name; / / name
private int level; / / level
public Viper(int id, String name, int level) {
this.id = id;
this.name = name;
this.level = level;
}
public int getId(a) {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName(a) {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getLevel(a) {
return level;
}
public void setLevel(int level) {
this.level = level; }}public static void main(String[] args) {
PriorityQueue queue = new PriorityQueue(10.new Comparator<Viper>() {
@Override
public int compare(Viper v1, Viper v2) {
// Set priority rules (in reverse order, the higher the level, the more permissions)
returnv2.getLevel() - v1.getLevel(); }});// Build the entity class
Viper v1 = new Viper(1."Java".1);
Viper v2 = new Viper(2."MySQL".5);
Viper v3 = new Viper(3."Redis".3);
/ / loaded
queue.offer(v1);
queue.offer(v2);
queue.offer(v3);
while(! queue.isEmpty()) {// Iterate over the name
Viper item = (Viper) queue.poll();
System.out.println("Name：" + item.getName() +
"Level."+ item.getLevel()); }}}Copy the codeThe result of the above code is as follows:
Name: MySQL Level: 5
Name: Redis Level: 3
Name: Java Level: 1
As can be seen from the above results, the priority queue is dequeued regardless of the order of joining the queue. It always follows that the element with higher priority is dequeued first.
4. Delay queue
DelayQueue is implemented based on PriorityQueue, which can be regarded as a PriorityQueue measured in time. The queued elements can not be queued until they reach the specified delay time.
Let’s demonstrate the use of delay queues:
import lombok.Getter;
import lombok.Setter;
import java.text.DateFormat;
import java.util.Date;
import java.util.concurrent.DelayQueue;
import java.util.concurrent.Delayed;
import java.util.concurrent.TimeUnit;
public class CustomDelayQueue {
// Delay the message queue
private static DelayQueue delayQueue = new DelayQueue();
public static void main(String[] args) throws InterruptedException {
producer(); // Call the producer
consumer(); // Call the consumer
}
/ / producer
public static void producer(a) {
// Add a message
delayQueue.put(new MyDelay(1000."1"));
delayQueue.put(new MyDelay(3000."2"));
}
/ / consumer
public static void consumer(a) throws InterruptedException {
System.out.println("Start execution time:" +
DateFormat.getDateTimeInstance().format(new Date()));
while(! delayQueue.isEmpty()) { System.out.println(delayQueue.take()); } System.out.println("End execution time:" +
DateFormat.getDateTimeInstance().format(new Date()));
}
static class MyDelay implements Delayed {
// Delay cutoff time (milliseconds)
long delayTime = System.currentTimeMillis();
// With lombok
@Getter
@Setter
private String msg;
/** * initialize *@paramDelayTime delayTime *@paramMSG Executed message */
public MyDelay(long delayTime, String msg) {
this.delayTime = (this.delayTime + delayTime);
this.msg = msg;
}
// Get the remaining time
@Override
public long getDelay(TimeUnit unit) {
return unit.convert(delayTime - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
}
// The order of the elements in the queue
@Override
public int compareTo(Delayed o) {
if (this.getDelay(TimeUnit.MILLISECONDS) > o.getDelay(TimeUnit.MILLISECONDS)) {
return 1;
} else if (this.getDelay(TimeUnit.MILLISECONDS) < o.getDelay(TimeUnit.MILLISECONDS)) {
return -1;
} else {
return 0; }}@Override
public String toString(a) {
return this.msg; }}}Copy the codeThe result of the above code is as follows:
Start time: 2020-10-20 20:17:28
Message 1
Message 2
End Time: 2020-10-20 20:17:31
As you can see from the above end and start times, message 1 and message 2 both implement delayed execution properly.
5. Other queues
Java has a special queue, SynchronousQueue, that has no internal container. Each time a thread puts () data, it must wait for another thread to take it. This is used as an example:
import java.util.concurrent.SynchronousQueue;
public class SynchronousQueueTest {
public static void main(String[] args) {
SynchronousQueue queue = new SynchronousQueue();
/ / team
new Thread(() -> {
for (int i = 0; i < 3; i++) {
try {
System.out.println(new Date() + "Element in team");
queue.put("Data " + i);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}).start();
/ / out of the team
new Thread(() -> {
while (true) {
try {
Thread.sleep(1000);
System.out.println(new Date() + ", element out of line:" + queue.take());
} catch(InterruptedException e) { e.printStackTrace(); } } }).start(); }}Copy the codeThe result of the above code is as follows:
Mon Oct 19 21:00:21 CST 2020, element in the team
Mon Oct 19 21:00:22 CST 2020, element out: Data 0
Mon Oct 19 21:00:22 CST 2020, element in the team
Mon Oct 19 21:00:23 CST 2020, element out: Data 1
Mon Oct 19 21:00:23 CST 2020, element in the team
Mon Oct 19 21:00:24 CST 2020, element out: Data 2
As you can see from the above results, when an element is enqueued, the new element cannot be enqueued again until another thread has enqueued the element.
conclusion
This article looked at five types of queues in Java: normal queues, dual-endian queues, priority queues, delay queues, and other queues. The typical representatives of common queues are ArrayBlockingQueue and LinkedBlockingQueue, the representatives of dual-ended queues are LinkedBlockingDeque, and the representatives of priority queues are PriorityQueue. The DelayQueue is represented by the DelayQueue, and finally the synchronousQueues that have no internal containers.
Bonus: search the public account “Java Chinese Community” and send “interview” to receive the latest interview materials.