Queue ​

A Queue is a frequently used collection. A Queue is essentially an ordered list that implements a First In First Out (FIFO) structure. The difference between a Queue and a List is that a List allows adding and removing elements at any position, while a Queue only supports two operations:

• Adding elements to the end of the queue.
• Removing elements from the front of the queue.

The checkout counter in a supermarket is an example of a queue:

In Java's standard library, the Queue interface defines the following methods:

• int size(): Get the length of the queue.
• boolean add(E)/boolean offer(E): Add an element to the end of the queue.
• E remove()/E poll(): Retrieve and remove the head element of the queue.
• E element()/E peek(): Retrieve the head element of the queue without removing it.

For specific implementations, some Queues have a maximum length limit while others do not. Note that adding, removing, and retrieving elements from the queue always have two methods, as the behavior of these two methods differs when adding or retrieving elements fails. We summarize this in the following table:

For example, suppose we have a queue and we perform an add operation. If we call the add() method and it fails (perhaps due to exceeding the queue's capacity), it will throw an exception:

Queue<String> q = ...
try {
    q.add("Apple");
    System.out.println("Addition successful");
} catch (IllegalStateException e) {
    System.out.println("Addition failed");
}

If we call the offer() method to add an element and it fails, it will not throw an exception but will return false:

Queue<String> q = ...
if (q.offer("Apple")) {
    System.out.println("Addition successful");
} else {
    System.out.println("Addition failed");
}

When we need to remove the head element from the Queue, if the current Queue is empty, calling the remove() method will throw an exception:

Queue<String> q = ...
try {
    String s = q.remove();
    System.out.println("Retrieval successful");
} catch (IllegalStateException e) {
    System.out.println("Retrieval failed");
}

If we call the poll() method to retrieve the head element and it fails, it will not throw an exception but will return null:

Queue<String> q = ...
String s = q.poll();
if (s != null) {
    System.out.println("Retrieval successful");
} else {
    System.out.println("Retrieval failed");
}

Therefore, you can choose which set of methods to use based on your needs.

Note: Do not add null to the queue, as it becomes difficult to determine whether poll() returns null because it retrieved a null element or because the queue is empty.

Next, let's use poll() and peek() as examples to discuss the difference between “retrieve and remove” and “retrieve but do not remove.” For a Queue, each time poll() is called, it retrieves the head element, and the retrieved element has been removed from the queue:

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> q = new LinkedList<>();
        // Add 3 elements to the queue:
        q.offer("apple");
        q.offer("pear");
        q.offer("banana");
        // Retrieve elements from the queue:
        System.out.println(q.poll()); // apple
        System.out.println(q.poll()); // pear
        System.out.println(q.poll()); // banana
        System.out.println(q.poll()); // null, because the queue is empty
    }
}

If we use peek(), because retrieving the head element does not remove it from the queue, we can retrieve it repeatedly:

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> q = new LinkedList<>();
        // Add 3 elements to the queue:
        q.offer("apple");
        q.offer("pear");
        q.offer("banana");
        // The head is always apple, because peek() does not remove it:
        System.out.println(q.peek()); // apple
        System.out.println(q.peek()); // apple
        System.out.println(q.peek()); // apple
    }
}

From the above code, we can also see that LinkedList implements both the List and Queue interfaces. However, when using it, if we treat it as a List, we obtain a reference to the List. If we treat it as a Queue, we obtain a reference to the Queue:

// This is a List:
List<String> list = new LinkedList<>();
// This is a Queue:
Queue<String> queue = new LinkedList<>();

Always adhere to the principle of programming to an abstraction, which can significantly improve the quality of your code.

Summary ​

• The Queue implements a First In First Out (FIFO) data structure:
  • Use add()/offer() methods to add elements to the tail.
  • Use remove()/poll() to retrieve and remove elements from the head.
  • Use element()/peek() to retrieve elements from the head without removing them.
• Avoid adding null to the queue.