7
\$\begingroup\$

I've implemented the queue data structures using array in java. Anything I need to change in my code?

Queue.java

import java.util.Arrays;

public class Queue<T> {

    private int front;
    private int rear;
    int size;
    T[] queue;

    public Queue(int inSize) {
        size = inSize;
        queue = (T[]) new Object[size];
        front = -1;
        rear = -1;
    }

    public boolean isempty() {
        return (front == -1 && rear == -1);
    }

    public void enQueue(T value) {
        if ((rear+1)%size==front) {
            throw new IllegalStateException("Queue is full");

        } else if (isempty()) {
            front++;
            rear++;
            queue[rear] = value;

        } else {
            rear=(rear+1)%size;
            queue[rear] = value;

        }
    }

    public T deQueue() {
        T value = null;
        if (isempty()) {
            throw new IllegalStateException("Queue is empty, cant dequeue");
        } else if (front == rear) {
            value = queue[front];
            front = -1;
            rear = -1;

        } else {
            value = queue[front];
            front=(front+1)%size;

        }
        return value;

    }

    @Override
    public String toString() {
        return "Queue [front=" + front + ", rear=" + rear + ", size=" + size
                + ", queue=" + Arrays.toString(queue) + "]";
    }

}

QueueImpl.java

public class QueueImpl {

    public static <T> void main(String[] args) {
        Queue newQueue = new Queue(5);
        newQueue.enQueue(10);
        newQueue.enQueue(20);
        newQueue.enQueue(30);
        newQueue.enQueue(40);
        newQueue.enQueue(50);
        System.out.println((T) newQueue.toString());
        System.out.println((T) newQueue.deQueue().toString());
        System.out.println((T) newQueue.deQueue().toString());
        System.out.println((T) newQueue.toString());
        newQueue.enQueue(60);
        newQueue.enQueue(70);
        System.out.println((T) newQueue.toString());
        System.out.println((T) newQueue.deQueue().toString());
        System.out.println((T) newQueue.deQueue().toString());
        System.out.println((T) newQueue.deQueue().toString());
        System.out.println((T) newQueue.deQueue().toString());
        System.out.println((T) newQueue.deQueue().toString());
        System.out.println((T) newQueue.toString());


    }

}
\$\endgroup\$
7
\$\begingroup\$

Your fields size and queue have package access, they need to be private so only your class can control them.

private final int size;
private final T[] queue;

And because their values are known at initialization, its good practice to declare them final.

your isempty method is not Camelcase, use isEmpty instead. Some validation on the size parameter is needed as well.

 if(size<=0){
  throw new IllegalArgumentException("Size cannot be less than or equal to zero");
 }

Something I love about the this keyword is that it helps you finding a name for your variables

 public Queue(int size) { // size is more relevant than inSize 
   if(size<=0){
       throw new IllegalArgumentException("Size cannot be less than or equal to zero");
    }
    this.size = size;
    queue = (T[]) new Object[size];
    front = -1;
    rear = -1;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks. Actually I thought of doing size check, but i forgot while implementing my code :( \$\endgroup\$ – Arun Prakash Sep 30 '14 at 13:04
  • \$\begingroup\$ thats very common :( \$\endgroup\$ – Sleiman Jneidi Sep 30 '14 at 13:05
5
\$\begingroup\$

Disclaimer: I'm not a Java guy.

But....

  • This If needs some breathing space.

    public void enQueue(T value) {
        if ((rear+1)%size==front) {
    

    It would be much more readable like this:

    if ((rear + 1) % size == front) {
    
  • Same goes for this statement later in the same enQueue method.

    rear=(rear+1)%size;
    
  • Actually, it looks like you could extract a function there.

  • deQueue also suffers from inconsistent (and poor) whitespace.

  • I know it's just an example implementation to show us that it works, but QueueImpl is a poor name. There's no reason to abbrv names. It's not the 1960's. We're not counting bytes in our names anymore. Prefer clear, concise, and meaningful names over shortened ones.

  • Speaking of the example implementation, it would be better to write an actual Unit Test than to print to the console.

\$\endgroup\$
  • \$\begingroup\$ Thanks. I will try to write unit test cases from my next programs. \$\endgroup\$ – Arun Prakash Sep 30 '14 at 13:08
4
\$\begingroup\$

You have a memory hog when using a large queue.

Because you store the object references and don't null them on retrieval, one could store a object reference to an object that references a great deal of other objects. Once I dequeue this object, it remains in your array and is not garbage collected.

\$\endgroup\$
  • \$\begingroup\$ how to avoid this? \$\endgroup\$ – Arun Prakash Sep 30 '14 at 13:03
  • 5
    \$\begingroup\$ "Because you store the object references and don't null them on retrieval, (...)": null the object references on retrieval. \$\endgroup\$ – Pimgd Sep 30 '14 at 13:05
3
\$\begingroup\$

The size field is not required (just use queue.length)

In fact, the size field is a misnomer, because it is the capacity, not the size. The size is the number of elements that the queue actually contains, while the capacity is the maximum number of elements that it can hold.

In enQueue, you have a special case for the empty queue, and in deQueue you have a special case for the singleton queue. These special cases are avoidable. Instead of representing the empty queue with head == rear == -1 you could keep a separate size field (to remember how many elements are in the queue). Or you could use a different invariant:

queue empty iff head == rear
queue full  iff rear == (head+1) % queue.length
\$\endgroup\$

protected by Jamal Dec 5 '16 at 19:01

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.