Priority queue implementation using vector

Question

Priority queue implementation using vector

I am implementing a priority queue through a vector, my method for insertion works normally:

public boolean inserir(int n){


if(estaCheia()) {
    return false;
}

if(estaVazia()) {
    fila[nItens++] = n;
    return true;
} else {

    int i; 
    for(i = nItens-1; i>=0; i--) {
        if(n > fila[i]){
            fila[i+1] = fila[i];
        } else{
            break;
        }
    }

    fila[i+1] = n;
    nItens++;
    return true;
}

}

The only problem is when I will retrieve the first element of the queue, I get a free position in the vector, but when trying to insert an ArrayIndexOutOfBounds expection arises, I believe it is because the free space in the vector is the first. What should I do to rearrange the vector so that it is possible to insert it after having removed the first element of the queue?

1

java array fila

Author: Vinicius, 2015-12-20

Source

1 answers

score 2 · Accepted Answer

Since you are doing a vector-based queue, you need to rearrange the vector after a removal. This is the price to pay for the use of a static structure, but it can be a great price if the application works with few removals.

You will need something like this in your removal algorithm:

for (int i = posicaoDoElementoRemovido; i < tamanhoDaFila-1; i++) {
    fila[i] = fila[i+1];
}

That is, each position receives the value of the next.

An extra hint: exchange this your return of type boolean for a void. If your structure is full, throw an exception.