Day 9: Queues

Queues are another fundamental data structure that follow the First In, First Out (FIFO) principle. In a queue, the first element added is the first one to be removed, much like a line of people waiting for service. In this post, we’ll define queues, explore their types, implement them in Java, and solve example problems, including queue reversal.

Definition of Queues

A queue is a collection of elements that supports two primary operations:

• Enqueue: Add an element to the end of the queue.
• Dequeue: Remove and return the element from the front of the queue.

Queues are essential for scenarios where order matters, such as scheduling tasks or handling requests.

Types of Queues

1. Circular Queue: A circular queue connects the last position back to the first position, making it efficient in terms of space utilization. When the queue is full, the next enqueue operation will overwrite the oldest elements if allowed.
2. Priority Queue: In a priority queue, each element has a priority level. Elements with higher priority are dequeued before those with lower priority, regardless of their order in the queue. This is often implemented using a heap data structure.

Implementation in Java

Here’s a simple implementation of a queue using an array:

javaCopy codeclass Queue {
    private int maxSize;
    private int[] queueArray;
    private int front;
    private int rear;
    private int currentSize;

    public Queue(int size) {
        maxSize = size;
        queueArray = new int[maxSize];
        front = 0;
        rear = -1;
        currentSize = 0;
    }

    public void enqueue(int value) {
        if (currentSize >= maxSize) {
            System.out.println("Queue is full. Cannot enqueue " + value);
            return;
        }
        rear = (rear + 1) % maxSize; // Circular increment
        queueArray[rear] = value;
        currentSize++;
    }

    public int dequeue() {
        if (currentSize == 0) {
            System.out.println("Queue is empty. Cannot dequeue.");
            return -1; // Indicate empty queue
        }
        int value = queueArray[front];
        front = (front + 1) % maxSize; // Circular increment
        currentSize--;
        return value;
    }

    public int peek() {
        if (currentSize == 0) {
            System.out.println("Queue is empty.");
            return -1;
        }
        return queueArray[front];
    }

    public boolean isEmpty() {
        return (currentSize == 0);
    }
}

Example Problem: Queue Reversal

One interesting problem is to reverse a queue. This can be achieved by using a stack to temporarily hold the elements as you dequeue them.

Implementation in Java

javaCopy codeimport java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class QueueReversal {
    public static Queue<Integer> reverseQueue(Queue<Integer> queue) {
        Stack<Integer> stack = new Stack<>();

        // Dequeue all elements from the queue and push them onto the stack
        while (!queue.isEmpty()) {
            stack.push(queue.poll());
        }

        // Pop elements from the stack and enqueue them back to the queue
        while (!stack.isEmpty()) {
            queue.offer(stack.pop());
        }
        
        return queue;
    }

    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        
        System.out.println("Original Queue: " + queue);
        Queue<Integer> reversedQueue = reverseQueue(queue);
        System.out.println("Reversed Queue: " + reversedQueue); // Output: [3, 2, 1]
    }
}

Conclusion

Queues are an essential data structure that supports various applications, from task scheduling to resource management. Understanding how to implement and manipulate queues effectively will enhance your programming skills.

In our next post, we will explore Hash Tables, another crucial data structure, and discuss their operations and applications. Stay tuned!

Also see: The Z Blogs

my other Blog: The Z Blog ZB