Queue data structure

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, meaning the element added first to the queue is the first one to be removed. This property makes queues ideal for managing tasks in the order they arrive, such as scheduling tasks, handling requests, and more.

Key Characteristics of Queue

• FIFO Principle: Elements are dequeued in the order they were enqueued.
• Head and Tail: The queue maintains a head pointer for the front and a tail pointer for the back.
• Dynamic Size: The size of the queue changes as elements are enqueued and dequeued.

Applications of Queue

• Task Scheduling: Operating systems use queues to manage processes and threads.
• Breadth-First Search: Graph traversal algorithms use queues to visit nodes layer by layer.
• Order Processing: Queues are used to manage orders in systems where the order of processing matters.

Queue Implementation in Java

In Java, queues can be implemented using various data structures like arrays, linked lists, and the Java Collections Framework.

Array-Based Queue

An array-based queue uses a fixed-size array. This is a straightforward implementation but is not suitable for dynamic resizing.

class ArrayQueue {
    private int front, rear, size;
    private int capacity;
    private int[] queue;

    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        front = size = 0;
        rear = capacity - 1;
        queue = new int[this.capacity];
    }

    boolean isFull() {
        return (size == capacity);
    }

    boolean isEmpty() {
        return (size == 0);
    }

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

    int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return Integer.MIN_VALUE;
        }
        int item = queue[front];
        front = (front + 1) % capacity;
        size--;
        return item;
    }

    int front() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return Integer.MIN_VALUE;
        }
        return queue[front];
    }

    int rear() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return Integer.MIN_VALUE;
        }
        return queue[rear];
    }
}

Linked List-Based Queue

A linked list-based queue provides dynamic sizing and is often the preferred implementation for queues that need to grow and shrink dynamically.

class LinkedListQueue {
    class Node {
        int data;
        Node next;

        Node(int item) {
            data = item;
            next = null;
        }
    }

    private Node front, rear;

    public LinkedListQueue() {
        front = rear = null;
    }

    boolean isEmpty() {
        return front == null;
    }

    void enqueue(int item) {
        Node newNode = new Node(item);
        if (rear == null) {
            front = rear = newNode;
            return;
        }
        rear.next = newNode;
        rear = newNode;
    }

    int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return Integer.MIN_VALUE;
        }
        int item = front.data;
        front = front.next;
        if (front == null) rear = null;
        return item;
    }

    int front() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return Integer.MIN_VALUE;
        }
        return front.data;
    }

    int rear() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return Integer.MIN_VALUE;
        }
        return rear.data;
    }
}

Queue Using Java Collections Framework

Java provides a built-in Queue interface, which is implemented by classes like LinkedList and PriorityQueue. The LinkedList class provides an easy-to-use implementation for FIFO queues.

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

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();

        q.add(10);
        q.add(20);
        q.add(30);

        System.out.println("Front element: " + q.peek());
        q.remove();
        System.out.println("After dequeue, front element: " + q.peek());

        System.out.println("Queue size: " + q.size());
    }
}

Advanced Queue Implementations

A priority queue is a type of queue where each element is assigned a priority, and elements with higher priorities are dequeued before elements with lower priorities.

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.add(30);
        pq.add(10);
        pq.add(20);

        System.out.println("Priority Queue: " + pq);

        while (!pq.isEmpty()) {
            System.out.println("Dequeued: " + pq.poll());
        }
    }
}

A deque (double-ended queue) allows insertion and deletion at both ends, providing flexibility to operate as both a stack and a queue.

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

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

        dq.addFirst(10);
        dq.addLast(20);
        dq.addFirst(5);

        System.out.println("Deque: " + dq);

        System.out.println("Removed from front: " + dq.removeFirst());
        System.out.println("Removed from back: " + dq.removeLast());
    }
}

Applications of Queues in Real-World Scenarios

1. Operating System Scheduling The operating system uses queues to manage processes and threads, scheduling them based on different criteria like first-come-first-served (FCFS) and round-robin scheduling.
2. Network Packet Management Routers use queues to manage network packets, prioritizing them based on the type of service to ensure efficient network traffic.
3. Printer Management Printing jobs are managed using queues to ensure that documents are printed in the order they are received.

Performance Analysis

The performance of a queue implementation depends on the data structure used:

• Array-Based Queue: Access and enqueue operations are O(1), but dequeue operations are also O(1) with circular buffering.
• Linked List-Based Queue: Both enqueue and dequeue operations are O(1).
• Priority Queue: Both enqueue and dequeue operations are O(log n).