Priority queue implementation using vector

Question

I am implementing a priority queue through an array, 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 recover the first element of the queue, I get a free position in the vector, but when I try to insert an Arrayindexoutofbounds expection, I believe it is because the free space in the vector is the first. What should I do to rearrange the array so that it is possible to insert it after removing the first element from the row?

Answer 1

As you are queuing on a vector-based basis, you need to rearrange the vector after a removal. This is the price to pay for using 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 suggestion: change your return of the type boolean by a void. If your structure is full, make an exception.