CODEWITHSUNDEEP
javaarraysqueue
salxander
salxander

Reputation: 1091

Implement a queue using an array - Java

I'm trying to implement a queue ADT using an array for a homework assignment (were it up to me I would be using a linked list, but I guess the professor wants us to learn new things or something XD). Anyway, I'm working on a method to add an element to the end of the queue, this same method should create a new re-sized array if it gets out of bounds, and this is the method I'm struggling with (the enqueue() method). Here is my code: 

import java.util.Arrays;


public class Queue<T> implements QueueInterface<T> {

    private T[] a;
    private int sz;

    public Queue(int capacity) {
        sz = 0;
        @SuppressWarnings("unchecked")
        T[] tempQueue = (T[])new Object[capacity];
        a= tempQueue;
    }

    public void enqueue(T newEntry) {
        try {
        for (int i=0; i<a.length; i++) {
                if (a[i] == null) {
                    a[i] = newEntry;
                    break;
                }
            }
        sz++;
        }
        catch (ArrayIndexOutOfBoundsException e) {
            @SuppressWarnings("unchecked")
            T[] tempQueue = (T[])new Object[a.length*+5];
            a= tempQueue;
            for (int i=0; i<a.length; i++) {
                if (a[i] == null) {
                    a[i] = newEntry;
                    break;
                }

            }
        }
    }

    public T dequeue() {
        T result = a[0];
        a[0] = null;
        for (int i=1; i<a.length;i++) {
            a[i-1] = a[i];
        }
        sz--;
        return result;
    }

    public T getFront() {
        return a[0];
    }

    public boolean isEmpty() {
        for (int i=0; i<a.length; i++) {
            if (a[i] != null) {
                return false;
            }
        }
        return true;
    }

    public void clear() {
        for (int i=0; i<a.length; i++) {
            a[i] = null;
            sz--;
        }
    }

    @Override
    public String toString() {
        return "Queue [a=" + Arrays.toString(a) + ", sz=" + sz + "]";
    }

}

Thanks so much for your time everyone!!!

Upvotes: 1

Views: 10835

Answers (5)

SajithA
SajithA

Reputation: 436

If you are going to implement a queue using an array, I think the best way to do it is using a circular array. In that way you don't have to move all elements by one step forward when you dequeue. But since you want to implement a re-sizable (on-bounded) queue, circular array implementation become little bit difficult. Here are some useful links,

If you want an implementation, just Google for it.

(This may not be an answer for your question, but I cannot comment in your question.)

Upvotes: 2

thedayofcondor
thedayofcondor

Reputation: 3876

Check the array length to detect the outoubounds - exceptions are expensive.

To copy the array, create a new array of the proper size and then use System.arrayCopy

A rule of thumb is not to increase the size by a fixed amount, but to increase by a percentage of the original size (eg 30% larger)

Upvotes: 1

Paulo Viana
Paulo Viana

Reputation: 136

Complementing Alan Krueger's answer: you do not have to iterate through the whole array again when resizing it. Create a temporary variable that stores the old array's length and begin iterating from it.

Upvotes: 0

Don Roby
Don Roby

Reputation: 41127

Your implementation may not be the most efficient way of using an array to implement a queue, but given that you've decided to implement it this way, your enqueue method is a bit more complex than it need be.

You have a field sz that can be used to determine where the new entry has to be put rather than checking through to find the first non-null. And the search for a non-null won't work properly anyway as the dequeue isn't clearing the last element moved forward.

The sz field will also tell you when you need to resize, rather than detecting that need by an exception.

Upvotes: 0

Alan Krueger
Alan Krueger

Reputation: 4786

Try putting the resizing logic into a private method called ensureSize or something. Check the desired size there; if it's too small, resize the array and copy the contents over. Call this method from any methods that might need the array size increased.

Upvotes: 0

Related Questions