Desempenho da fila que é melhor implementação - matriz ou lista vinculada
Qual o caminho para enfileirar e desenfileirar mais rapidamente quando preciso inserir muito poucos elementos? O array é melhor que uma lista vinculada?
Preciso inserir alguns elementos e tenho que remover e ler esse elemento removido da fila. Se for um array, talvez seja necessário modificar os índices toda vez que removo um elemento. A inserção e exclusão também podem ocorrer simultaneamente.
Qual é o melhor do caso abaixo?
typedef struct{
mylist list;
struct mylistQ *next;
}mylistQ;
Código da matriz
static mylist myListQ[QUEUESIZE+1];
int qLast = 0;
void enqueue_element(mylist qItem)
{
myListQ[qLast] = qItem;
qLast++;
}
mylist dequeue_element()
{
retryq:
if(qLast >0) {
mylist qReturn = myListQ[0];
int i;
for (i = 0; i < qLast - 1; i++){
myListQ[i] = myListQ[i + 1];
}
qLast--;
return qReturn;
}
else {
goto retryq;
}
}
Lista vinculada
int qLast = 0;
mylistQ *headElement = NULL;
mylistQ *tailElement = NULL;
void enqueue_element(mylist *List)
{
mylistQ *newnode;
newnode=(mylistQ*)av_malloc(sizeof(mylistQ));
newnode->next=NULL;
newnode->list=*List;
qLast++;
if(headElement==NULL && tailElement==NULL)
{
headElement=newnode;
tailElement=newnode;
}
else
{
tailElement->next=newnode;
tailElement=newnode;
}
}
mylist dequeue_element()
{
mylistQ *delnode; /* Node to be deleted */
mylist Dellist;
if(headElement==NULL && tailElement==NULL){
LOg( "Queue is empty to delete any element");
}
else
{
Log("In dequeue_picture queue is not empty");
delnode=headElement;
headElement=headElement->next;
if (!headElement){
tailElement=NULL;
}
Dellist = delnode->list;
av_free(delnode);
qLast--;
}
return Dellist;
}