Implement a queue using an array - Java

Question

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!!!

A common method for getting you to appreciate the easy way to do something is to have you do it the hard way first. =) — Alan Krueger
– Alan Krueger, Commented Nov 4, 2012 at 23:26
What is your specific problem -- we have better things to do than to study your code for defects. And keep in mind that for an array queue you need the array itself and the head (dequeue location) and tail (enqueue location) index values. When you get to the end of the array you "wrap" back, so the tail value can be larger than the head. — Hot Licks
– Hot Licks, Commented Nov 4, 2012 at 23:28
You know, I try to be very polite on this site especially when asking for help, and I am sorry if I wasn't specific enough (still trying to get the hang of this I guess). But speaking frankly, if you have better things to do than go do them. I have no problem with you asking for more detail but you can at least be courteous about it. Thanks for you response anyway I suppose — salxander
– salxander, Commented Nov 4, 2012 at 23:42
Did you read the rest of my comment? You're missing a piece of data you need to make it work. — Hot Licks
– Hot Licks, Commented Nov 5, 2012 at 0:36
@Jake1164: please read the homework tag wiki. Do not add it to questions. — Mat
– Mat, Commented Mar 5, 2013 at 5:47

Community · Accepted Answer · 2017-05-23 12:21:29Z

3

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.)

edited May 23, 2017 at 12:21

CommunityBot

11 silver badge

answered Nov 4, 2012 at 23:45

SajithA

4461 gold badge9 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Hot Licks Over a year ago

@Xander -- There is wisdom here. Pay attention.

thedayofcondor · Accepted Answer · 2012-11-04 23:39:12Z

1

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)

answered Nov 4, 2012 at 23:39

thedayofcondor

3,8761 gold badge24 silver badges28 bronze badges

Comments

Alan Krueger · Accepted Answer · 2012-11-04 23:29:23Z

0

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.

answered Nov 4, 2012 at 23:29

Alan Krueger

4,8064 gold badges38 silver badges50 bronze badges

Comments

Don Roby · Accepted Answer · 2012-11-04 23:30:22Z

0

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.

answered Nov 4, 2012 at 23:30

Don Roby

41.2k6 gold badges96 silver badges114 bronze badges

Comments

Paulo Viana · Accepted Answer · 2012-11-04 23:33:15Z

0

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.

answered Nov 4, 2012 at 23:33

Paulo Viana

1365 bronze badges

Collectives™ on Stack Overflow

Implement a queue using an array - Java

5 Answers 5

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related