Algorithm for implementing a queue with java code samples.

Queue

A queue is a linear data structure where elements are stored in a FIRST-IN FIRST-OUT (FIFO) approach, where the first element inserted will be the first element to be accessed.

Similarity with Stack

A queue is an abstract data structure(ADT), similar to Stack, the only difference is that queue is open at both ends, i.e. while stack allows operation(insertion and deletion) on one end only, queue allows operations(insertion and deletion) on both ends.

Real Life Scenarios

In real life, a queue could be said to be similar to a checkout line in a supermarket or filling station, where a dispenser services the vehicles at the beginning of the line first. Other vehicles enter the line only at the end and wait for service.

Ways to implement a Queue

A queue can be implemented in various ways; using Arrays or Linked List, in this article, I delved into implementation with Linked List.

Basic Operations as used in this article

Below are some basic operations that can be carried out on a queue

enqueue - this operation mutates the queue, it inserts nodes at the end of the queue.
dequeue - this operation mutates the queue, it removes node from the front of the queue
peek - this operation does not mutate the queue, rather, it retrieves the node at the beginning of the queue.
isFull - verifies if the queue has all the slots filled(for fixed size queues)
isEmpty - verify whether the queue is empty

enqueue

Below is the algorithm for inserting into a queue

START
Check if the queue is full
If the queue is full, produce overflow error and exit
Check if the queue is empty
If the queue is empty, increment the front/rear pointer to point to the next empty slot
If the queue is not empty, increment the rear pointer to point to the next empty slot
Add element to the queue location, where the rear is pointing
Return success
END


package queue;

import java.util.EmptyStackException;

public class LinkedListQueueDSA<T> {
    private final int capacity;
    private int size = 0;
    private Node<T> front = null;
    private Node<T> rear = null;

    // Constructor to create a queue with default capacity
    public LinkedListQueueDSA() {
        this.capacity = 5;
    }

    // constructor to create a queue of defined capacity
    public LinkedListQueueDSA(int capacity) {
        this.capacity = capacity;
    }

    // Internal class to create Nodes
    private static class Node<T> {
        T data;
        Node<T> next;

        public Node(T value) {
            this.data = value;
            this.next = null;
        }
    }
}


    public int getSize() {
        return size;
    }

    // For fixed-size queue, check the slots remaining
    public int freeSlots() {
        return capacity - size;
    }

    public void enqueue(T value) {
        if (isFull()) throw new StackOverflowError("Can not enqueue. No free slot.");
        Node<T> newNode = new Node<>(value);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = rear.next;
        }
        size++;
    }

dequeue

START
Check if the queue is empty, if the queue is empty, produce underflow error and exit
If the queue is not empty, access the data where front is pointing
Increment front pointer to point to the next available data element
Return success
END

// Removes the first element from the queue
    public T dequeue() {
        if (isEmpty()) throw new EmptyStackException();
        // Grab data at the front
        T data = front.data;
        // move front pointer to the next
        front = front.next;
        // De-allocate memory
        if (front == null) rear = null;
        --size;
        return data;
    }

    // Remove n number of element from the front
    public void dequeue(int num) {
        if (isEmpty()) throw new EmptyStackException();
        if (num < 0 || num > size) {
            throw new IndexOutOfBoundsException("Index out of bound: " + num);
        }
        int i = 0;
        while (i < num) {
            dequeue();
            i++;
        }
    }

peek

START
Check if the queue is empty, if empty produce error and exit
If not empty, return the element at the front of the queue
END


// Retrieves the first element without deleting it
    public T peekFront() {
        if (isEmpty()) throw new EmptyStackException();
        return front.data;
    }

// Here, we decided to check the element at the end of the queue
    public T peekBack() {
        if (isEmpty()) throw new EmptyStackException();
        return rear.data;
    }

isFull

START
If the size of the queue elements is equal to the queue capacity, return true
Else, return false
END

    public boolean isFull() {
        return getSize() == capacity;
    }

isEmpty

START
If the count of the queue elements equals zero, return true
Else, return false
END

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

Iterate over the nodes in the queue

    public String getEnqueuedValues() {
        if (isEmpty()) return "[]";
        StringBuilder sb = new StringBuilder().append("[");
        Node<T> trav = front;
        while (trav != null) {
            sb.append(trav.data);
            if (trav.next != null) sb.append(", ");
            trav = trav.next;
        }
        return sb.append("]").toString();
    }

The codes put together

package queue;

import java.util.EmptyStackException;

public class LinkedListQueueDSA<T> {
    private final int capacity;
    private int size = 0;
    private Node<T> front = null;
    private Node<T> rear = null;

    // Constructor to create queue with default capacity
    public LinkedListQueueDSA() {
        this.capacity = 5;
    }

    // constructor to create a queue of defined capacity
    public LinkedListQueueDSA(int capacity) {
        this.capacity = capacity;
    }

    // Internal class to create Nodes
    private static class Node<T> {
        T data;
        Node<T> next;

        public Node(T value) {
            this.data = value;
            this.next = null;
        }
    }

    public int getSize() {
        return size;
    }

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

    public boolean isFull() {
        return getSize() == capacity;
    }

    // For fixed-size queue, check the slots remaining
    public int freeSlots() {
        return capacity - size;
    }

    // Retrieves the first element without deleting it
    public T peekFront() {
        if (isEmpty()) throw new EmptyStackException();
        return front.data;
    }

    public T peekBack() {
        if (isEmpty()) throw new EmptyStackException();
        return rear.data;
    }

    public void enqueue(T value) {
        if (isFull()) throw new StackOverflowError("Can not enqueue. No free slot.");
        Node<T> newNode = new Node<>(value);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = rear.next;
        }
        size++;
    }

    // Removes the first element from the queue
    public T dequeue() {
        if (isEmpty()) throw new EmptyStackException();
        // Grab data at the front
        T data = front.data;
        // move front pointer to the next
        front = front.next;
        // De-allocate memory
        if (front == null) rear = null;
        --size;
        return data;
    }

    // Remove n number of element from the front
    public void dequeue(int num) {
        if (isEmpty()) throw new EmptyStackException();
        if (num < 0 || num > size) {
            throw new IndexOutOfBoundsException("Index out of bound: " + num);
        }
        int i = 0;
        while (i < num) {
            dequeue();
            i++;
        }
    }

    public String getEnqueuedValues() {
        if (isEmpty()) return "[]";
        StringBuilder sb = new StringBuilder().append("[");
        Node<T> trav = front;
        while (trav != null) {
            sb.append(trav.data);
            if (trav.next != null) sb.append(", ");
            trav = trav.next;
        }
        return sb.append("]").toString();
    }
}

Here, we run the code in a different package

package queue;

public class LinkedListQueueDSAExercises {
    public static void main(String[] args) {
        LinkedListQueueDSA<Integer> q = new LinkedListQueueDSA<>(10);
        q.enqueue(10);
        q.enqueue(20);
        q.enqueue(30);
        q.enqueue(40);
        q.enqueue(50);

        Integer front = q.peekFront();
        Integer back = q.peekBack();

        System.out.println("Queue: " + q.getEnqueuedValues());
        System.out.println("Size: " + q.getSize());
        System.out.println("Peek Front: " + front);
        System.out.println("Peek Back: " + back);
        System.out.println("Free slots: " + q.freeSlots());

        System.out.println(("---------------"));

        Integer dq = q.dequeue();
        System.out.println("Dequeue " + dq);
        q.dequeue(2);

        front = q.peekFront();
        back = q.peekBack();

        System.out.println("Queue: " + q.getEnqueuedValues());
        System.out.println("Size: " + q.getSize());
        System.out.println("Peek Front: " + front);
        System.out.println("Peek Back: " + back);
        System.out.println("Free slots: " + q.freeSlots());
        System.out.println("Is empty queue: " + q.isEmpty());

        LinkedListQueueDSA<String> sq = new LinkedListQueueDSA<>();
        sq.enqueue("Hello world!");
        sq.enqueue("Nice to meet y'all");
        System.out.println(sq.getEnqueuedValues());
    }
}

Chigbogu Orji