Queue - Clean Design

Definition

A queue is an ordered collection of items from which items may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (called the rear of the queue). The first element inserted into a queue is the first element to be removed. For this reason a queue is sometimes called a FIFO (first-in, first-out).

Clean Design of Queue

The basic set of operations for a queue are insert, remove & isEmpty. Hence, per clean design principles (Single Responsibility Principle & Interface Segregation Principle) that is our basic interface for queues

package clean.project.ds.queue.contract;

public interface PrimitiveQueue<T> {
    public void insert(T item) throws Exception;
    public T remove() throws Exception;
    public boolean isEmpty();
}

Additionally, for practical purposes we may need additional operations to be defined, hence the following interfaces extending the primitive queue interface

package clean.project.ds.queue.contract;

public interface LimitedQueue<T> extends PrimitiveQueue<T> {
    public boolean isFull();
}

package clean.project.ds.queue.contract;

public interface MonitoredLimitedQueue<T> extends LimitedQueue<T> {
    public T peek();
}

The queue can be in two flavours, straight or circular, hence the two types of implementation

All such implementations of queue interfaces will be plugins for the queues, hence can be easily replaceable without breaking the high level logic based on the queues.

For the object management, we will create the abstract factory for queues.

package clean.project.ds.queue.factory;

public interface QueueFactory<QT, T> {
    public QT getQueue(final int size);
}

package clean.project.ds.queue.factory;

import clean.project.ds.queue.contract.MonitoredLimitedQueue;
import clean.project.ds.queue.impl.StraightMonitoredLimitedQueueImpl;

public class StraightMonitoredLimitedQueueFactory<T> implements QueueFactory<MonitoredLimitedQueue<T>, T> {
    public MonitoredLimitedQueue<T> getQueue(int size) {
        return new StraightMonitoredLimitedQueueImpl<T>(size);
    }
}

package clean.project.ds.queue.factory;

import clean.project.ds.queue.contract.MonitoredLimitedQueue;
import clean.project.ds.queue.impl.CircularMonitoredLimitedQueueImpl;

public class CircularMonitoredLimitedQueueFactory<T> implements QueueFactory<MonitoredLimitedQueue<T>, T>{
    public MonitoredLimitedQueue<T> getQueue(int size) {
        return new CircularMonitoredLimitedQueueImpl<T>(size);
    }
}

package clean.project.ds.queue.factory;

public class QueueFactoryBuilder<T> {
    public StraightMonitoredLimitedQueueFactory<T> getStraightMonitoredLimitedQueueFactory() {
        return new StraightMonitoredLimitedQueueFactory<T>();
    }

    public CircularMonitoredLimitedQueueFactory<T> getCircularMonitoredLimitedQueueFactory() {
        return new CircularMonitoredLimitedQueueFactory<T>();
    }

}

UML diagram for the queue factory

Application of Queues

Find Largest Multiple of 3 from a set of digits

package clean.project.ds.queue.application;

import clean.project.ds.queue.contract.MonitoredLimitedQueue;
import clean.project.ds.queue.factory.QueueFactoryBuilder;

import java.util.Arrays;

/**
 * Mathematical background of the algorithm.
 * Following are true for all multiples of 3
 * 1. A number is multiple of 3 if and only if the sum of digits of number is multiple of 3.
 * 2. If a number is multiple of 3, then all permutations of it are also multiple of 3.
 * 3. We get the same remainder when we divide the number and sum of digits of the number by 3.
 */
public class FindLargestMultipleOfThree {

    private static final QueueFactoryBuilder<Integer> intQueueFactoryBuilder = new QueueFactoryBuilder<Integer>();

    public boolean findLargestMultipleOfThreeFromDigits(int [] digits) throws Exception {
        Arrays.sort(digits);
        final MonitoredLimitedQueue<Integer> remainderZeroQueue = intQueueFactoryBuilder.getStraightMonitoredLimitedQueueFactory().getQueue(100);
        final MonitoredLimitedQueue<Integer> remainderOneQueue = intQueueFactoryBuilder.getStraightMonitoredLimitedQueueFactory().getQueue(100);
        final MonitoredLimitedQueue<Integer> remainderTwoQueue = intQueueFactoryBuilder.getStraightMonitoredLimitedQueueFactory().getQueue(100);
        int sumOfDigits = sumDigitsAndDistributeIntoRemainderQueues(digits, remainderZeroQueue, remainderOneQueue, remainderTwoQueue);
        if ((sumOfDigits % 3) == 1) {
            if (!remainderOneQueue.isEmpty()) {
                remainderOneQueue.remove();
            } else {
                for (int numOfTimes = 0; numOfTimes < 2; numOfTimes++) {
                    if (!remainderTwoQueue.isEmpty()) {
                        remainderTwoQueue.remove();
                    } else {
                        return false;
                    }
                }
            }
        } else if ((sumOfDigits % 3) == 2) {
            if (!remainderTwoQueue.isEmpty()) {
                remainderTwoQueue.remove();
            } else {
                for (int numOfTimes = 0; numOfTimes < 2; numOfTimes++) {
                    if (!remainderOneQueue.isEmpty()) {
                        remainderOneQueue.remove();
                    } else {
                        return false;
                    }
                }
            }
        }
        int [] aux = new int[digits.length];
        int lastIndex = sumAllQueuesInArrayAndGetLastIndex(aux, remainderZeroQueue, remainderOneQueue, remainderTwoQueue);
        Arrays.sort(aux, 0, lastIndex);
        System.out.println("Largest Multiple of 3 from the given digits: ");
        for (int index = lastIndex -1; index >= 0; index--) {
            System.out.print(aux[index] + " ");
        }
        return true;
    }

    private int sumDigitsAndDistributeIntoRemainderQueues(int [] sortedDigitsArray,
                                                           MonitoredLimitedQueue<Integer> remainderZeroQueue,
                                                           MonitoredLimitedQueue<Integer> remainderOneQueue,
                                                           MonitoredLimitedQueue<Integer> remainderTwoQueue) throws Exception {
        int sumOfDigits=0;
        for (int i = 0; i < sortedDigitsArray.length; ++i) {
            sumOfDigits += sortedDigitsArray[i];
            if ((sortedDigitsArray[i] % 3) == 0) {
                remainderZeroQueue.insert(sortedDigitsArray[i]);
            } else if ((sortedDigitsArray[i] % 3) == 1) {
                remainderOneQueue.insert(sortedDigitsArray[i]);
            } else {
                remainderTwoQueue.insert(sortedDigitsArray[i]);
            }
        }
        return sumOfDigits;
    }

    private int sumAllQueuesInArrayAndGetLastIndex(int [] aux,
                                                  MonitoredLimitedQueue<Integer> remainderZeroQueue,
                                                  MonitoredLimitedQueue<Integer> remainderOneQueue,
                                                  MonitoredLimitedQueue<Integer> remainderTwoQueue) throws Exception {
        int lastIndex = 0;
        while (!remainderZeroQueue.isEmpty()) {
            aux[lastIndex++] = remainderZeroQueue.remove();
        }
        while (!remainderOneQueue.isEmpty()) {
            aux[lastIndex++] = remainderOneQueue.remove();
        }
        while (!remainderTwoQueue.isEmpty()) {
            aux[lastIndex++] = remainderTwoQueue.remove();
        }
        return lastIndex;
    }

    public static void main(String[] args) {
        int [] digits = {8, 1, 7, 6, 0};
        final FindLargestMultipleOfThree findLargestMultipleOfThree = new FindLargestMultipleOfThree();
        try {
            if (!findLargestMultipleOfThree.findLargestMultipleOfThreeFromDigits(digits)) {
                System.out.println("Multiple of 3 not possible");
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

You can find the full code at https://github.com/priyeshkpandey/clean-data-structures