data-driven-docs

Selft training repo

Project maintained by ggranados Hosted on GitHub Pages — Theme by mattgraham

Queue and Deque Interface

Queue and Deque Interface

Queue Interface Characteristics

In Java, the Queue interface is a part of the Java Collections Framework and represents a collection that holds elements in a specific order. Elements in a Queue are typically processed in a first-in-first-out (FIFO) manner, meaning that the element that was added first will be the first one to be removed. Queues are commonly used in scenarios like task scheduling, event handling, and breadth-first search algorithms.

Key of the Queue interface:

Ordering: Elements in a Queue are ordered based on their insertion time. The first element inserted will be the first to be removed.
FIFO: The Queue follows the “First-In-First-Out” principle, where elements are processed in the order they were added.
Basic Operations: Common methods include add(), offer(), remove(), poll(), and peek(), among others.

_{Back to top}

Deque Interface Characteristics

The Deque (Double-Ended Queue) interface extends the Queue interface and represents a queue where you can add or remove elements from both ends. You can treat a Deque as both a queue and a stack. Deques are useful in scenarios where you need to efficiently add or remove elements from the beginning or end of the queue.

Key characteristics of the Deque interface:

Double-Ended: The Deque allows adding and removing elements from both the front (head) and the rear (tail).
Stack and Queue Operations: As a Deque extends the Queue interface, you can perform queue operations like FIFO as well as stack operations like LIFO (Last-In-First-Out).
Additional Methods: In addition to the methods from the Queue interface, the Deque provides methods such as addFirst(), addLast(), removeFirst(), removeLast(), getFirst(), and getLast().

_{Back to top}

Most Used Queue and Deque Implementations

Java provides several implementations of the Queue and Deque interfaces. Let’s go through the most commonly used ones:

_{Back to top}

Queue Implementations

LinkedList

Implements both the Queue and Deque interfaces.
Provides efficient add and remove operations for both ends.
Not thread-safe, so if you require thread-safety, consider using java.util.concurrent.ConcurrentLinkedDeque.

Preferred when you need a versatile and efficient Queue implementation with both FIFO capabilities. Deque Implementations

Example:

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

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        // Adding elements to the queue
        queue.add("Apple");
        queue.offer("Banana");
        queue.add("Orange");

        // Removing and processing elements (FIFO)
        while (!queue.isEmpty()) {
            String element = queue.poll();
            System.out.println("Processing: " + element);
        }
    }
}

_{Back to top}

PriorityQueue

Implements the Queue interface and provides elements based on their natural order or a custom comparator.
Elements are ordered based on their priority.
Offers quick access to the element with the highest priority.

Most preferred when you need to process elements based on their priority, such as in a task scheduler or Dijkstra’s algorithm.

Example:

import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();

        // Adding elements to the priority queue
        priorityQueue.add(5);
        priorityQueue.add(10);
        priorityQueue.add(2);
        priorityQueue.add(8);

        // Removing and processing elements (based on priority)
        while (!priorityQueue.isEmpty()) {
            Integer element = priorityQueue.poll();
            System.out.println("Processing: " + element);
        }
    }
}

_{Back to top}

ArrayBlockingQueue

ArrayBlockingQueue is a specific implementation of the BlockingQueue interface in Java. It is a bounded, blocking queue backed by an array, which means it has a fixed capacity specified during its creation.

Fixed capacity, meaning it can hold only a limited number of elements. Once the queue reaches its capacity, attempts to add more elements will block until space becomes available.
Blocking operations, which means if the queue is empty, attempts to retrieve elements (take(), poll(), etc.) will block until an element becomes available. Similarly, if the queue is full, attempts to add elements (put(), offer(), etc.) will block until space becomes available.
Follows the First-In-First-Out (FIFO) order, meaning elements are processed in the order they were added.
Thread-Safe, is designed to be used in concurrent environments, and all of its methods are thread-safe. This makes it suitable for scenarios where multiple threads need to interact with the queue simultaneously.
Is not reentrant. If a thread holds a lock on the queue and attempts to perform another blocking operation on the same queue, it will result in a deadlock.
Does not allow null elements. Attempts to add null elements will result in a NullPointerException.

Is particularly useful in scenarios where you have multiple producers and consumers sharing a bounded buffer. Since it is a blocking queue, it allows producers to block when the buffer is full and consumers to block when the buffer is empty, effectively coordinating the communication between threads.

Example:

import java.util.concurrent.ArrayBlockingQueue;

public class Main {
public static void main(String[] args) {
int capacity = 10;
ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<>(capacity);

        // Producer adding elements to the queue
        try {
            queue.put(1);
            queue.put(2);
            // ...
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        // Consumer retrieving elements from the queue
        try {
            Integer element = queue.take();
            // Process the element
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

_{Back to top}

Deque Implementations

LinkedList

Implements both the Queue and Deque interfaces.
Provides efficient add and remove operations for both ends.
Not thread-safe, so if you require thread-safety, consider using java.util.concurrent.ConcurrentLinkedDeque.

Preferred when you need a versatile and efficient Queue implementation with both FIFO and LIFO capabilities. Deque Implementations

Example:

import java.util.LinkedList;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();

        // Adding elements to the deque from the rear
        deque.addLast("Element 1");
        deque.addLast("Element 2");
        deque.addLast("Element 3");

        // Adding elements to the deque from the front
        deque.addFirst("Element 0");

        // Removing and processing elements from both ends (FIFO and LIFO)
        while (!deque.isEmpty()) {
            String frontElement = deque.pollFirst(); // Removes from the front (FIFO)
            String rearElement = deque.pollLast();   // Removes from the rear (LIFO)

            System.out.println("Processing from front: " + frontElement);
            System.out.println("Processing from rear: " + rearElement);
        }
    }
}

ArrayDeque

Implements both the Deque and Queue interfaces.
Resizable-array implementation with better performance compared to LinkedList.
Not thread-safe, so if you require thread-safety, consider using java.util.concurrent.ConcurrentLinkedDeque.

Preferred when you need a fast and efficient double-ended queue implementation.

Example:

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

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

        // Adding elements to the deque
        deque.addFirst("Front");
        deque.offerLast("Back");
        deque.add("Middle");

        // Removing and processing elements from both ends (FIFO and LIFO)
        while (!deque.isEmpty()) {
            String firstElement = deque.pollFirst();
            String lastElement = deque.pollLast();

            System.out.println("Processing from front: " + firstElement);
            System.out.println("Processing from back: " + lastElement);
        }
    }
}

_{Back to top}

LinkedBlockingDeque

Implements the BlockingDeque interface, extending BlockingQueue and Deque.
Provides blocking operations for concurrent scenarios.
Suitable for use in concurrent producer-consumer patterns.

Preferred when you need a thread-safe Deque implementation to handle concurrent operations efficiently.

Example:

import java.util.concurrent.BlockingDeque;
import java.util.concurrent.LinkedBlockingDeque;

public class Main {
    public static void main(String[] args) {
        BlockingDeque<String> blockingDeque = new LinkedBlockingDeque<>();

        // Adding elements to the blocking deque
        blockingDeque.add("One");
        blockingDeque.offer("Two");
        blockingDeque.addLast("Three");

        // Removing and processing elements from both ends (FIFO and LIFO)
        while (!blockingDeque.isEmpty()) {
            String firstElement = blockingDeque.pollFirst();
            String lastElement = blockingDeque.pollLast();

            System.out.println("Processing from front: " + firstElement);
            System.out.println("Processing from back: " + lastElement);
        }
    }
}

_{Back to top}

Choose the appropriate implementation

Always consider the characteristics and performance implications of each implementation for your application’s needs.

For Queue:

Use LinkedList (as Queue) when you need a basic, versatile, and memory-efficient queue implementation with both FIFO capabilities.

Use PriorityQueue when you need to process elements based on their priority, where elements with higher priority are processed before those with lower priority.

If you need a fixed-size, thread-safe queue with blocking behavior, ArrayBlockingQueue would be more appropriate

For Deque:

Use LinkedList (as Deque) when you need a basic, versatile, and memory-efficient queue implementation with both FIFO and LIFO capabilities.

Use ArrayDeque (as Deque) when you require a fast and efficient double-ended queue for adding or removing elements from both the front and the back.

When you need a thread-safe double-ended queue for concurrent producer-consumer scenarios, such as in a multi-threaded environment, use LinkedBlockingDeque.

_{Back to top}

Queue Comparison Table

Characteristic	LinkedList	PriorityQueue	ArrayBlockingQueue
Ordering	Insertion Order	Priority Order	No specific order
Element Ordering	FIFO (First-In-First-Out)	Depends on priority	FIFO (First-In-First-Out)
Null Elements Allowed	Yes	No	No
Blocking Behavior	Not Blocking	Not Blocking	Blocking on insertion/removal
Iteration Performance	`O(n)`	`O(n)`	`O(n)`
Use Cases	Basic Queue Operations	Priority-based Queue	Bounded Queue with blocking behavior

_{Back to top}

Deque Comparison Table

Characteristic	LinkedList	ArrayDeque	LinkedBlockingDeque
Ordering	Insertion Order	Insertion Order	Insertion Order
Element Ordering	FIFO/LIFO	FIFO/LIFO	FIFO/LIFO
Null Elements Allowed	Yes	No	No
Blocking Behavior	Not Blocking	Not Blocking	Blocking on insertion/removal
Iteration Performance	`O(n)`	`O(n)`	`O(n)`
Use Cases	Basic Deque Operations	General-purpose Deque	Bounded Deque with blocking behavior

_{Back to top}

Ref.

https://www.geeksforgeeks.org/queue-interface-java/?ref=lbp https://www.geeksforgeeks.org/deque-interface-java-example/?ref=lbp https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html

Get Started | Languages | Java Development | Original Collections API | Updated Collections

data-driven-docs

Queue and Deque Interface

Table of Contents

Queue Interface Characteristics

Deque Interface Characteristics

Most Used Queue and Deque Implementations

Queue Implementations

LinkedList

PriorityQueue

ArrayBlockingQueue

Deque Implementations

LinkedList

ArrayDeque

LinkedBlockingDeque

Choose the appropriate implementation

Queue Comparison Table

Deque Comparison Table

Ref.