Queue

A Queue is a First-In, First-Out (FIFO) data structure that models a real-world queue.

The basic operations include:

• enqueue: Adding an element at the end
• dequeue: Removing the element from the front
• peek: Viewing the front element without removing it

How to implement Queue in Java?

Here is a implementation of a Circular Queue data structure using array in Java:

public class Queue {
    private int front;
    private int rear;
    private int capacity;
    private int[] array;

    public Queue(int capacity) {
        this.capacity = capacity;
        this.front = this.rear = -1;
        this.array = new int[capacity];
    }

    public boolean isEmpty() {
        return front == -1;
    }

    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }

    public void enqueue(int item) {
        if (isFull()) {
            System.out.println("Queue is full.");
            return;
        }
        rear = (rear + 1) % capacity;
        array[rear] = item;
        if (front == -1) {
            front = rear;
        }
    }

    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty.");
            return -1;
        }
        int item = array[front];
        if (front == rear) {
            front = rear = -1;
        } else {
            front = (front + 1) % capacity;
        }
        return item;
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty.");
            return -1;
        }
        return array[front];
    }

    public static void main(String[] args) {
        Queue queue = new Queue(5);
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);

        System.out.println("Front element is: " + queue.peek());  // Output: Front element is: 1
        System.out.println("Dequeued element is: " + queue.dequeue());  // Output: Dequeued element is: 1
    }
}

Usage of Queue

1. Order Preservation: Useful in scenarios where the order of elements matters, such as task scheduling.
2. Data Buffering: Used in asynchronous data transfer mechanisms like printers, message queues.
3. Breadth-First Search: Used in algorithms that explore nodes and edges of graphs.
4. Rate Limiting: Helpful in controlling the rate of task execution in multitasking environments.
5. Operational Resiliency: Used in call centers, web service backends for task distribution.
6. Undo Mechanism: Stores operations in a software application to allow undo features.

Java and Queues: Using Built-in Constructs

Java provides a rich set of in-built classes to deal with the Queue data structure. Let’s explore in details.

1. Queue Interface

Located in the java.util package, the Queue interface provides several methods to manipulate data in a First-In-First-Out (FIFO) manner.

Basic methods

• add(E e): Inserts the specified element into the queue.
• offer(E e): Inserts the specified element into the queue, returns false if the element cannot be inserted.
• remove(): Retrieves and removes the head of the queue.
• poll(): Retrieves and removes the head of the queue, returns null if the queue is empty.
• element(): Retrieves, but does not remove, the head of the queue.
• peek(): Retrieves, but does not remove, the head of the queue, returns null if the queue is empty.

2. Implementations

Java provides several implementations of the Queue interface:

a. LinkedList

Though LinkedList is primarily known as a doubly-linked list, it also implements the Queue interface, making it usable as a queue.

Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
int head = queue.poll();  // retrieves and removes the head: 1

b. PriorityQueue

It’s not a standard FIFO queue but a priority queue where elements are ordered according to their natural ordering or a comparator provided during construction.

Queue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.add(3);
priorityQueue.add(1);
priorityQueue.add(2);
int head = priorityQueue.poll();  // retrieves and removes the smallest element: 1

c. ArrayDeque

A resizable-array implementation of a double-ended queue (Deque). It’s more memory efficient than LinkedList when used as a queue.

Queue<Integer> arrayDeque = new ArrayDeque<>();
arrayDeque.add(1);
arrayDeque.add(2);
int head = arrayDeque.poll();  // retrieves and removes the head: 1

d. ConcurrentLinkedQueue

A thread-safe queue based on linked nodes. Suitable for highly concurrent applications.

Queue<Integer> concurrentQueue = new ConcurrentLinkedQueue<>();
concurrentQueue.add(1);
concurrentQueue.add(2);
int head = concurrentQueue.poll();  // retrieves and removes the head: 1

e. ArrayBlockingQueue:

A bounded blocking queue backed by an array. It’s thread-safe and blocks when trying to add to a full queue, or remove from an empty one.

Queue<Integer> blockingQueue = new ArrayBlockingQueue<>(10);
blockingQueue.add(1);
blockingQueue.add(2);
int head = blockingQueue.poll();  // retrieves and removes the head: 1

3. Takeaways

• The Queue interface provides a standard way to interact with various queue implementations in Java.
• Depending on the use-case (ordering, concurrency needs, or memory considerations), Java offers a diverse set of classes to work with queues.
• Always choose the right implementation based on your specific requirements.