Deep understanding of Java series | Queue usage explanation

This article has participated in the Denver Nuggets Creators Camp 3 “More Productive writing” track, see details: Digg project | creators Camp 3 ongoing, “write” personal impact.

Hi everyone, I am MAO Yefan, a back-end engineer who loves technology, thank you for your attention!

Welcome to understanding Java in Depth. The purpose of this series of articles is to review basic concepts, data structures, multithreading, locking, JUC, and more.

In this article we’ll take a look at the use of Queue in Java. Let’s get started!

1. What is a Queue?

A Queue, or Queue, is a basic linear data structure, like arrays, linked lists, stacks, and so on.

A Queue is a collection of data that follows FIFO: First In, First Out (FIFO: First In, First Out). The flow of data In a Queue is one-way, from the end of the Queue to the First.

As shown in the figure below, element insertion occurs at the end of the queue and deletion occurs at the head of the queue. Normally when an element is removed from the Queue, it is removed from the Queue. Elements that are not the head of the queue cannot be read directly.

Queues are very common in the real world, such as queuing passengers waiting to buy tickets and get on the bus, and products waiting to be processed one by one on the assembly line. Queues are also widely used in the world of programming: tasks waiting to be processed in multiple threads, threads queuing to acquire a lock, etc.

Let’s take a look at the main uses and principles of Queue in Java.

2. Queue interface in Java

2.1 Queue Interface Definition

In Java, queues are a basic collection type that provides the Queue interface, defined in the java.util package; The Queue interface inherits the base Collection interface Collection.

The Queue interface is defined as follows:

public interface Queue<E> extends Collection<E> {
    
    boolean add(E e);
    
    boolean offer(E e);

    E remove(a);

    E poll(a);

    E element(a);

    E peek(a);
}
Copy the code

In the Queue interface, the basic methods for inserting and deleting elements are defined. The main methods and their meanings are as follows:

2.2 Dual-end Queue: Deque interface

In the Queue interface definition above, the basic insert and delete methods are implemented, that is, insert elements from the end of the Queue and delete elements from the beginning of the Queue. Java also provides another powerful Deque interface, which implements the function of a double-endian queue.

What is a double-endian queue?

A double-ended queue is a queue that can insert and delete elements at either the beginning or the end of the queue, as shown in the following figure. In a two-ended queue, first and last represent the first and last ends of the queue, respectively, and you can specify which end of the queue to operate on when inserting or deleting an element.

For example, offerFirst(A) means that elements are inserted at the beginning of the queue, and pollLast() means that elements are deleted at the end of the queue.

The Deque interface is defined as follows:

As you can see, the Deque interface inherits from the Queue interface. In addition to the basic Queue interface methods, the Deque also provides the operation methods of a double-endian Queue. As shown in the code, each operation method is similar to the operation method of Queue, except that it specifies whether the element operation is performed at the beginning or the end of the Queue.

public interface Deque<E> extends Queue<E> {

    // Add an element to the queue head; Returns true if space is available, otherwise an 'IllegalStateException' exception is thrown
    void addFirst(E e);
    // Add an element to the end of the queue; Returns true if space is available, otherwise an 'IllegalStateException' exception is thrown
    void addLast(E e);
	
    // Add an element to the queue head; Return true if space was added successfully, false otherwise
    boolean offerFirst(E e);
    // Add an element to the end of the queue; Return true if space was added successfully, false otherwise
    boolean offerLast(E e);
  
    // Remove an element from the head of the queue; Return the first element if it exists, otherwise raise 'NoSuchElementException'
    E removeFirst(a);
    // Remove an element from the end of the queue; Return the last element if it exists, otherwise throw a 'NoSuchElementException' exception
    E removeLast(a);
		
    // Remove an element from the head of the queue; Returns the first element if it exists, null otherwise
    E pollFirst(a);
    // Remove an element from the end of the queue; Returns the first element if it exists, null otherwise
    E pollLast(a);
  
    // Get an element from the head of the queue, but do not delete it; Return the first element if it exists, otherwise raise 'NoSuchElementException'
    E getFirst(a);
    // Get an element from the end of the queue, but do not delete it; Return the last element if it exists, otherwise throw a 'NoSuchElementException' exception
    E getLast(a);

    // Get an element from the head of the queue, but do not delete it; Returns the first element if it exists, null otherwise
    E peekFirst(a);
    // Get an element from the end of the queue, but do not delete it; Returns the last element if it exists, null otherwise
    E peekLast(a);

    // If element o exists, the first occurrence of the element is removed from the queue
    boolean removeFirstOccurrence(Object o);
    // If element o exists, the last occurrence of that element is removed from the queue
    boolean removeLastOccurrence(Object o);
    // Other methods omit....
}
Copy the code

2.3 Implement class LinkedList

Earlier, we looked at the two Queue interfaces defined in Java, Queue and Deque, and the implementation classes for both interfaces are implemented through LinkedList. As can be seen from the class name definition, LinkedList is actually a data collection of List based on LinkedList implementation, and LinkedList also implements Queue interface and Deque interface. We can use LinkedList directly to implement queue operations. Here is the definition:

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable.java.io.Serializable
{... }Copy the code

Here is an example of a two-ended queue based on the LinkedList implementation:

public static void main(String[] args) {
  Deque<String> queue = new LinkedList<>();
  // The element joins the team
  queue.offer("1");
  queue.offer("2");
  queue.offer("3");
  queue.offerFirst("0");  // add element 0 to the head of the queue
  queue.offerLast("4");   // Add element 4 to the end of the queue

  System.out.println(queue);  [0, 1, 2, 3, 4]

  // Element out of the queue
  System.out.println(queue.poll());       // Delete the first element of the queue, print the value: 0
  System.out.println(queue.pollFirst());  // Delete the first element of the queue, print the value: 1
  System.out.println(queue.pollLast());   // Delete the last element of the queue, print the value: 4
}
Copy the code

OK, now that we have looked at the definition of the queue interface and the definition and usage of the implementation class LinkedList, let’s briefly look at how the queue function is implemented at the bottom of LinkedList.

3. How does LinkedList implement queuing

3.1 Definition of linked list

As we have seen above, LinkedList is actually a collection of data based on a LinkedList implementation and implements the interface functionality of queues. Let’s look again at the definition of LinkedList and its member variables.

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable.java.io.Serializable
{
    // Number of elements
    transient int size = 0;
    // first element node
    transient Node<E> first;
    // End of the queue element node
    transient Node<E> last;
    / /...
}
Copy the code

As can be seen, there are two member variables in the LinkedList, first and last, of type Node

, representing the first and last nodes in the queue respectively, which are actually the first and last nodes in the LinkedList. Node

is a Node in a linked list. Here is its definition:

private static class Node<E> {
  / / element value
  E item;
  // The last node
  Node<E> next;
  // The previous node
  Node<E> prev;

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

In Node

, the member variable item is used to store the specific element value, and two other Node

variables next and prev represent the next and previous nodes of the Node, respectively.

At this point, we can see that the LinkedList is actually composed of a two-way LinkedList, with first and last representing the first and last nodes of the list, respectively. Then we can draw a diagram of the list below.

3.2 Element insertion

From the previous introduction, we learned that we can insert elements using both add and offer, except that when the queue capacity is insufficient, add will throw the exception, while offer will return false. But LinkedList is implemented based on a two-way LinkedList, which is theoretically unbounded and can insert new elements as long as program memory allows.

Let’s take a look at the implementation logic of the offer method insert element as follows (comments have been added) :

public class LinkedList<E>...{
  /** * inserts the element */
  public boolean offer(E e) {
    // The add method is called directly here
    return add(e);
  }
  /** * inserts the element */
  public boolean add(E e) {
    // Call linkLast
    linkLast(e);
    return true;
  }
  /** * Add a new element to the end of the list as the new last node */
  void linkLast(E e) {
    // The current last node
    final Node<E> l = last;
    // Create a new node with the prev pointing to the current last node
    final Node<E> newNode = new Node<>(l, e, null);
    // The new node serves as the new last node
    last = newNode;
    if (l == null)
      // If last is null, the list is empty
      first = newNode;
    else
      // If the list is not empty, the new node will be the next node of the previous last node
      l.next = newNode;
    // Number of elements +1
    size++;
    // Set changes +1modCount++; }}Copy the code

As you can easily see from the code, the offer method calls the add method directly, and the add method calls the linkLast method, and returns true, indicating that the element must be inserted successfully. The logic of inserting elements is completed in linkLast method. It can be seen from the comments in the above code that the main function of linkLast method is to add a new node at the end of the linked list. The detailed operation diagram is as follows:

offerFirstandofferLastHow is it done?

Now that we know about the Offer method, let’s look at the implementations of offerFirst and offerLast. As you can see from the following code, the offerFirst and offerLast methods call addFirst and addLast, respectively, and within addFirst and addLast, they call linkFirst and linkLast, respectively.

The main function of linkLast is to add a new node to the end of the list. LinkFirst method, its main function is to add a new node at the beginning of the linked list. The specific logic is similar to linkLast method, which is not described here. You can refer to the notes in the code below.

public class LinkedList<E>...{
  // First insert element
  public boolean offerFirst(E e) {
    addFirst(e);
    return true;
  }
  // Insert elements at the end of the queue
  public boolean offerLast(E e) {
    addLast(e);
    return true;
  }
  // First insert element
  public void addFirst(E e) {
    linkFirst(e);
  }
  // Insert elements at the end of the queue
  public void addLast(E e) {
    linkLast(e);
  }
  /** * At the head of the list, add a new element as a new first node */
  private void linkFirst(E e) {
    // The current first node
    final Node<E> f = first;
    // Create a new node with the next node pointing to the current first node
    final Node<E> newNode = new Node<>(null, e, f);
    // The new node is the new first node
    first = newNode;
    if (f == null)
      // If the original first node is null, the list is empty
      last = newNode;
    else
      // If the list is not empty, the new node will be the prev node of the original first node
      f.prev = newNode;
    // Number of elements +1
    size++;
    // Set changes +1
    modCount++;
  }
  /** * Add a new element to the end of the list as the new last node */
  void linkLast(E e) {
    // this section is omitted, see the previous code block}}Copy the code

OK, now that we have seen how elements are inserted and the implementation logic for inserting elements at the head and tail of a two-ended queue, let’s take a quick look at how elements are deleted.

3.3 Deletion of elements

The main function of the delete process is to remove the node at the head or bottom of the queue. PollFirst, pollLast, delete, deleteFirst, and deleteLast can be used to delete a node. All of these methods call unlinkFirst and unlinkLast, which delete the nodes at the head and tail of the list.

Here is the code logic for the unlinkFirst and unlinkLast methods.

public class LinkedList<E>...{
    /** * delete list header f, f is not empty */
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f ! = null;
        // Get the element of the header
        final E element = f.item;
        // Get the next node of the header
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        // use next as the header
        first = next;
        if (next == null)
            // Next is null, indicating that the list is empty after deletion
            last = null;
        else
            // If the list is not empty after deletion, the prev of the current header is null
            next.prev = null;
        // Number of elements -1
        size--;
        // Set number of changes -1
        modCount++;
        // return the element of the deleted node
        return element;
    }

    /** * delete list end l, l is not empty */
    private E unlinkLast(Node<E> l) {
        // assert l == last && l ! = null;
        // Get the element of the end node
        final E element = l.item;
        // Get the prev of the end node
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        // use prev as a tail
        last = prev;
        if (prev == null)
            // if prev is null, the linked list will be empty after deletion
            first = null;
        else
            // If the list is not empty, the next node of the current tail is null
            prev.next = null;
        // Number of elements -1
        size--;
        // Set number of changes -1
        modCount++;
        // return the element of the deleted node
        returnelement; }}Copy the code

4. To summarize

This article mainly introduces the basic usage of Queue in Java and related underlying principles, using Queue we can achieve some tasks queuing processing functions.

However, in the above analysis, we can find that the implementation of Queue in Java is actually non-thread-safe. If the Queue is queued and queued in a multi-threaded environment, there will be inconsistent situation. So Java also provides a thread-safe queue class called BlockingQueue, which we’ll examine below.

I’m MAO Yifan. Thanks for your likes, comments and follows. see you next time