Queue Data Structure in java

A queue is a fundamental data structure in computer science that follows the First-In-First-Out (FIFO) principle. It is an abstract data type that represents a collection of elements with two primary operations: enqueue and dequeue.

A queue can be visualized as a line of people waiting in a queue, where new elements are added at the rear (enqueue) and elements are removed from the front (dequeue). The element at the front is the one that has been in the queue for the longest time.

Here are the key operations associated with a queue:

1. Enqueue: This operation adds an element to the rear of the queue. The newly added element becomes the last element in the queue.

2. Dequeue: This operation removes the element at the front of the queue. After the removal, the element that was previously behind it becomes the new front element.

3. Peek (or Front): This operation returns the element at the front of the queue without removing it.

4. isEmpty: This operation checks if the queue is empty or not. It returns true if the queue contains no elements, and false otherwise.

Queues are widely used in various computer science applications, such as job scheduling, event handling, breadth-first search algorithms, and more. They provide an efficient way to manage and retrieve elements based on the FIFO principle.

Queues can be implemented using various data structures, such as arrays or linked lists. The choice of implementation affects the efficiency of queue operations.

Here's a brief explanation of queue implementation using arrays:

In an array-based queue, we use a fixed-size array to store the elements of the queue. We maintain two indices, front and rear, to keep track of the front and rear elements, respectively. Additionally, we keep a variable size to store the current number of elements in the queue.

• Enqueue: When an element is enqueued, we increment the rear index and add the new element to the corresponding position in the array. If the rear index exceeds the size of the array, we wrap it around to the beginning using the modulo operator. We also increment the size variable.

• Dequeue: When an element is dequeued, we retrieve the element at the front index and increment the front index. If the front index exceeds the size of the array, we wrap it around using the modulo operator. We also decrement the size variable.

• Peek: The peek operation returns the element at the front index without removing it from the queue.

• isEmpty: The isEmpty operation checks if the size variable is equal to 0, indicating an empty queue.

• isFull: The isFull operation checks if the size variable is equal to the capacity of the array, indicating a full queue.

Here's a brief explanation of queue implementation using a linked list:

A linked list-based queue maintains a linked list to store the elements, along with references (or pointers) to the front and rear nodes.

• When an element is enqueued, a new node is created, and the rear node's next reference is updated to the new node. The rear reference is then updated to the new node.

• When an element is dequeued, the front node is removed by updating the front reference to point to the next node. You can retrieve the data from the removed node before discarding it.

• The peek operation simply returns the element at the front node without modifying the queue.

• The isEmpty operation checks if both the front and rear references are null, indicating an empty queue.

Code:

public class Node<T> {
    private T data;
    private Node<T> next;    
    public Node() {
    }    
    public Node(T data) {
        this.data = data;
        this.next=null;
    }    
    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public Node<T> getNext() {
        return next;
    }
    public void setNext(Node<T> next) {
        this.next = next;
    }    
}

public class Queue<T> {
    Node<T> head;
    Node<T> tail;

    public void enqueue(T data) {
        Node<T> node = new Node<T>(data);
        if (head == null) {
            head = node;
            tail = node;
        } else {
            tail.setNext(node);
            tail = node;
        }
    }

    public boolean dequeue() {
        if (head == null) {
            tail = null;
            return false;
        } else {
            head = head.getNext();
            return true;
        }
    }

    public boolean isEmpty() {
        if (head == null) {
            return true;
        } else {
            return false;
        }
    }

    public T peek() {
        if (head == null) {
            return null;
        }
        return head.getData();
    }

    @Override
    public String toString() {
        StringBuilder output = new StringBuilder();
        Node n = head;
        output.append('[');
        while (n != null && n.getNext() != null) {
            output.append(n.getData()).append(',');
            n = n.getNext();
        }
        if (n != null)
            output.append(n.getData()).append(']');
        else
            output.append(']');

        return output.toString();
    }
}

public class QueueDemo {

    public static void main(String[] args) {

        Queue<Integer> queue = new Queue<Integer>();
        int i = 1;        
        //insert data
        queue.enqueue(i++);
        queue.enqueue(i++);
        queue.enqueue(i++);
        queue.enqueue(i++);
        queue.enqueue(i++);
        queue.enqueue(i++);
        queue.enqueue(i++);
        queue.enqueue(i++);

        System.out.println(queue.toString());
        System.out.println(queue.peek());

        queue.dequeue();
        queue.dequeue();        
        System.out.println(queue.toString());
        System.out.println(queue.peek());        
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        System.out.println(queue.toString());
        System.out.println(queue.peek());    
        System.out.println(queue.isEmpty());
        queue.dequeue();
        System.out.println(queue.toString());
        System.out.println(queue.peek());    
        System.out.println(queue.isEmpty());    
    }
}

Output: