Queue

Photo by Meizhi Lang on Unsplash

What is a Queue in Java?

A Queue is an interface in the Java Collections Framework, found in the java.util package. It’s designed to hold a collection of elements before they are processed. The primary characteristic of a queue is that it typically, but not always, orders elements in a First-In, First-Out (FIFO) manner. This means that the first element added to the queue will be the first one to be removed.

Think of it like a line of people waiting for a service; the first person to get in line is the first person to be served.

Queue Interface Methods

The Queue interface provides methods for three main operations: inserting an element, removing an element, and examining an element. For each operation, there are two methods available: one that throws an exception if the operation fails, and another that returns a special value (like null or false).

Here’s a summary of its core methods:

• offer() vs. add(): offer() is generally preferred, especially for bounded (fixed-capacity) queues, as it returns false if the element can’t be added, whereas add() will throw an IllegalStateException.
• poll() vs. remove(): poll() returns null if the queue is empty, while remove() throws a NoSuchElementException.
• peek() vs. element(): peek() returns null if the queue is empty, whereas element() throws a NoSuchElementException.

How to Create a Queue

Since Queue is an interface, you cannot create an instance of it directly. You need to use one of the classes that implement it. The most common implementations are:

• LinkedList: A versatile class that implements both the List and Deque (and therefore Queue) interfaces. It’s a common choice for a standard FIFO queue.
• ArrayDeque: A resizable-array implementation of the Deque interface. It is often more efficient than LinkedList for add and remove operations at both ends.
• PriorityQueue: This is a special kind of queue that doesn’t order elements in FIFO order. Instead, it orders them based on their natural order or a custom Comparator provided at creation. The element with the highest priority (often the smallest value) is at the head.

Here’s how you would create a queue using LinkedList:

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

public class QueueExample {
    public static void main(String[] args) {
        // Create a Queue using a LinkedList
        Queue<String> fruitQueue = new LinkedList<>();

        // Add elements to the queue (enqueue)
        fruitQueue.offer("Apple");
        fruitQueue.offer("Banana");
        fruitQueue.offer("Cherry");

        System.out.println("Queue: " + fruitQueue);

        // Examine the head of the queue
        String head = fruitQueue.peek();
        System.out.println("Head of the queue: " + head); // Outputs: Apple

        // Remove an element from the queue (dequeue)
        String removedElement = fruitQueue.poll();
        System.out.println("Removed: " + removedElement); // Outputs: Apple

        System.out.println("Queue after removal: " + fruitQueue); // Outputs: [Banana, Cherry]
    }
}

Visualizing a Queue

Here is a diagram illustrating the First-In, First-Out (FIFO) principle of a queue.

Choosing the Right Queue Implementation

The implementation you choose has a significant impact on your application’s performance and behavior.

• LinkedList: A general-purpose implementation. It’s a good default choice if you’re not sure, but it can be less performant than ArrayDeque because it creates a new node object for every element added, which can lead to more frequent garbage collection.
• ArrayDeque: Generally the most efficient choice for a FIFO queue. It’s implemented as a resizable circular array, which is faster than LinkedList for adding and removing elements from both ends. If you need a simple queue, ArrayDeque is often the best choice.
• PriorityQueue: Use this only when you need elements to be processed based on priority rather than insertion order. For example, scheduling tasks where more urgent tasks must be handled first.

The Deque Interface (Double-Ended Queue)

Both LinkedList and ArrayDeque actually implement the Deque interface, which extends Queue. A Deque (pronounced “deck”) is a double-ended queue. This means you can add and remove elements from both the front and the back.

Get Saumya14’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

This makes Deque incredibly versatile. You can use it as:

• A Queue (FIFO): Using addLast() (or offerLast()) and removeFirst() (or pollFirst()).
• A Stack (LIFO): Using addFirst() (or push()) and removeFirst() (or pop()).

Because of its efficiency and flexibility, it’s now recommended to use an ArrayDeque as a Deque when you need a Stack, rather than the older Stack class.

import java.util.Deque;
import java.util.ArrayDeque;

public class DequeExample {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();

        // Push elements onto the stack
        stack.push("A"); // same as addFirst()
        stack.push("B");
        stack.push("C");

        // Pop elements off the stack (LIFO)
        System.out.println(stack.pop()); // C
        System.out.println(stack.pop()); // B
        System.out.println(stack.pop()); // A
    }
}

Common Use Cases

Queues are fundamental in computer science and have many real-world applications:

• Task Scheduling: Managing a queue of tasks to be executed by a pool of threads.
• Breadth-First Search (BFS): An algorithm for traversing tree or graph data structures uses a queue to keep track of nodes to visit.
• Buffering: Handling data streams, like network packets or user input, where data might arrive faster than it can be processed.
• Message Queues: In distributed systems, services often communicate by sending messages to each other through a queue (e.g., RabbitMQ, Kafka).

Collection Hierarchy Diagram

To help you visualize where these interfaces fit, here is a simplified diagram of the Java Collections Framework hierarchy.

Summary

Here’s the shortest summary:

• What it is: A First-In, First-Out (FIFO) collection.
• Key Methods: Use offer() (add), poll() (remove), and peek() (look).
• Best Implementation: Use ArrayDeque for a standard queue or stack.
• Special Cases:
  - PriorityQueue for priority-based order.
  - BlockingQueue for multi-threading.