Is it not possible to have an array based Queue with generics ?

Question

This is an array based Queue , for int :

/**
 * Array based
 * @author X220
 *
 */

public class MyQueue {

    private int[] _data;
    private int MAX_SIZE;
    private int front = -1;
    private int back = 0;
    private int elementsCount = 0;

    public void printQueue()
    {
        int j = this.front + 1;
        int i = 0;
        while (i < this._data.length && i < elementsCount)
        {
            System.out.println("At location " + j % MAX_SIZE + " element :" + this._data[j % MAX_SIZE]);
            j++;
            i++;
        }
    }

    public MyQueue(int _size)
    {
        MAX_SIZE = _size > 0 ? _size : 10;
        this._data = new int[MAX_SIZE];
    }

    public boolean IsEmpty()
    {
        return this.elementsCount == 0;     
    }

    public boolean IsFull()
    {
        return this.elementsCount == MAX_SIZE;
    }

    public void Push(int pushMe) throws QueueIsFullException
    {
        if (IsFull())
        {
            throw new QueueIsFullException("Queue is full");
        }
        this.elementsCount++;
        _data[back++ % MAX_SIZE] = pushMe;
    }

    public int Pop() throws QueueIsEmptyException 
    {
        if (IsEmpty())
        {
            throw new QueueIsEmptyException("Queue is full");
        }
        elementsCount--;
        return _data[++front % MAX_SIZE];
    }

    public static void main(String args[])
    {
        try
        {
            MyQueue q1 = new MyQueue(15);
            q1.Push(1);
            q1.Push(2);
            q1.Push(3);
            q1.Push(4);
            q1.Push(5);
            q1.Pop();
            q1.Pop();
            q1.Pop();
            q1.Pop();
            q1.Pop();
            q1.Push(6);
            q1.Pop();
            q1.Push(7);
            q1.Push(8);
            q1.Push(9);
            q1.Push(10);
            q1.Push(11);
            q1.Push(12);


//          q1.Push(1);
//          q1.Push(2);
//          q1.Push(3);
//          q1.Push(4);
//          q1.Push(5);
//          q1.Push(7);
//          q1.Push(8);
//          q1.Push(9);
//          q1.Push(10);
//          q1.Push(11);
//          q1.Push(12);
//          q1.Push(40);
//          q1.Push(50);
            q1.printQueue();

        }
        catch (Exception e)
        {
            System.out.println(e);
        }
    }


    @SuppressWarnings("serial")
    class QueueIsFullException extends Exception 
    {
          public QueueIsFullException(String message){
             super(message);
          }
    }

    @SuppressWarnings("serial")
    class QueueIsEmptyException extends Exception 
    {
          public QueueIsEmptyException(String message){
             super(message);
          }

    }

}

I wanted to use generics so I changed the int to T but then I got for this :

public class MyQueue <T>{

    private T[] _data;
    private int MAX_SIZE;
    private int front = -1;
    private int back = 0;
    private int elementsCount = 0;

    public void printQueue()
    {
        int j = this.front + 1;
        int i = 0;
        while (i < this._data.length && i < elementsCount)
        {
            System.out.println("At location " + j % MAX_SIZE + " element :" + this._data[j % MAX_SIZE]);
            j++;
            i++;
        }
    }

    public MyQueue(int _size)
    {
        MAX_SIZE = _size > 0 ? _size : 10;
        this._data = new T[MAX_SIZE];
    }

....


}

That :

• Cannot create a generic array of T

And from the answers to this post I see that I can't use generics with arrays .

Does this mean that there is no work around for a generics Queue based on array ? Must I switch to some other data structure ?

Answer 1

The root cause of your problem is not with your MyQueue class, I think you misunderstand the way Java handles generics. Generic types exist only at compile time, after that they are simply erased from the byte code and at runtime only real Java types exist behind the scenes.

This is why you cannot instantiate a generic type, because at runtime this parameterized type simply doesn't exist.

What you can do is to provide a real class (extending T) as a parameter in your MyQueue class an instantiate this class type, since this is a first-class Java type.

Here is a very similar StackOverflow question and a solution: Instantiating a generic class in Java

It is also recommended to read the Java reference about generics, like the answer for you original question is here: https://docs.oracle.com/javase/tutorial/java/generics/restrictions.html#createObjects

Answer 2

No there is a work around for this the ugly cast, change your array generic creation to:

        this._data = (T[])new Object[MAX_SIZE];

Due to the implementation of Java generics, you can't have code like this:

        this._data = new T[MAX_SIZE];

Have a look at this How to create a generic array in Java?

Answer 3

The method I prefer is using

@SuppressWarnings("unchecked")
T[] arr = (T[]) Array.newInstance(clazz,length);

where clazz is the Class<T> object corresponding to the generic type. Note that the cast is unchecked, but Array.newInstance ensures you that you won't be able to insert invalid types into your array.

To me this is the best solution because :

• you handle the type consistency to the Array class by passing a Class<T> instance which will be used to cast all the objects inserted in the array. This is thus type-safe without needing you to do anything.
• this is relatively small and self-contained, it won't force you to manually cast objects over and over everytime you use the array. This would be the case if you were using an Object[] under the hood.