Vector-based flood-fill algorithm queue class

Question

I want to implement the flood-fill algorithm for https://stackoverflow.com/questions/12995378/is-there-a-proper-algorithm-for-detecting-the-background-color-of-a-figure. I did it recursively, but I had a stack-overflow error. No matter - Wikipedia has a spot for a non-recursive, iterative solution.

It requires a queue. For school, we're not supposed to use Lists nor the Java Queue class (I don't even know if it does what I think it does, but it doesn't matter - I can't use it).

public class QueueOfPixeles
{
    public Pixel[] elements;
    public int numberOfElements;

    public QueueOfPixeles()
    {
        numberOfElements = 0;
        elements = new Pixel[1];
    }

    // Next pixel is supposed to return the last pixel element in the queue.
    // When a pixel element is returned, it will become null in the system.
    public Pixel nextPixel() {
        Pixel result = null;
        for (int i = elements.length - 1; i >= 0 && result == null; --i) {
            result = elements[i];
            if (result != null) {
                elements[i] = null;
            }
        }
        return result;
    }

    // Adds a new pixel to the queue.
    // Then, it checks if the capacity of the vector has been reached.
    public void add(Pixel pixel) {
        elements[numberOfElements] = pixel;
        ++numberOfElements;
        fixVector();
    }

    // If the vector capacity has been reached, create a new vector with all old elements
    // but with more capacity.
    private void fixVector() {
        if (numberOfElements >= elements.length) {
            Pixel[] newVector = new Pixel[(elements.length * 2) + 1];
            for (int i = 0; i < numberOfElements; ++i) {
                newVector[i] = elements[i];
            }
            elements = newVector;
        }
    }
}

WHAT IS IT SUPPOSED TO DO?

You should be able to add pixels to the end of the queue, and get the next pixel by using nextPixel(). When you retrieve the next pixel, it should be removed from the queue automatically.

DOES IT WORK?

Yes, it seems to be working. I've done a few tests and it has indeed returned all I expected.

WHAT'S THE PROBLEM?

I'd like to get some feedback about this. I can only use vectors for this project, and I feel there is something rather not-efficient with the way I manage the pixels in the queue (converting the elements to null and just that etc, or asking for more capacity size instead of using the null-spaces I made).

What do you think?

Answer 1

A note on terminology: What you have implemented is usually called a stack rather than a queue, but it can also be called a LIFO (last in, first out) queue, so it's not wrong to call it a queue, only uncommon.

The nextPixel() method is rather inefficient. You keep track of the number of elements in the queue, and you never do anything that allows any array element with an index >= numberOfElements to be anything but null. So instead of starting the search at elements.length - 1, you should start at numberOfElements - 1.

But that still leaves an inconsistency/inefficiency. The add() method doesn't guard against adding nulls to the queue, but you never return a null until the queue is empty.

You should either return nulls if you accept them to be added to the queue, or, better, I think, guard against nulls in add(). So I'd recommend

public void add(Pixel pixel) {
    if (pixel == null) return; // nothing to do
    // pixel isn't null, add it
    elements[numberOfElements] = pixel;
    ++numberOfElements;
    fixVector();
}

and then - also if you decide to return nulls if they're added - nextPixel() can simply be

public Pixel nextPixel() {
    // queue empty
    if (numberOfElements == 0) return null;
    // decrement numberOfElements and
    // return the last added Pixel
    return elements[--numberOfElements];
}

In fixVector(), you can probably be a bit more efficient if you use the generic Arrays.copyOf method, but maybe you are not allowed to use that either.

Answer 2

As Daniel Fisher already mentioned, you're using a Stack. The most basic implementation of this is a single linked list. The down side is that it consumes more memory than an array based implementation. The up side is that it is much easier to implement: You don't have to juggle with indexes, you don't have to copy the array content etc.