Implementation of priority queue using vector

1

I'm implementing a priority queue using a vector, so my insert method 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 retrieve the first element of the queue, I get a free position in the vector, but when trying to insert an expection ArrayIndexOutOfBounds appears, 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 can be inserted into it after removing the first element from the row?

    
asked by anonymous 21.12.2015 / 00:36

1 answer

2

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

You'll 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 next value.

An extra suggestion: Change your return from type boolean to void . If your structure is full, throw an exception.

    
21.12.2015 / 00:53