Listas Lineares – Filas

Juliana Jenny Kolb

teste seu conhecimento

Home > Simulados on-line  > Questões de Concursos > Tecnologia da Informação (TI) Algoritmos e Estruturas de Dados Estruturas de Dados

Listas Lineares – Filas

Filas são listas lineares com disciplina de acesso FIFO (first-in, first-out, ou, primeiro a entrar é o primeiro a sair). Sua principal aplicação é o armazenamento de dados em que é importante preservar a ordem FIFO de entradas e saídas.

O comportamento de fila é obtido armazenando-se a posição das extremidades da estrutura (chamadas aqui de fim e início), e permitindo entradas apenas na extremidade “fim” e retiradas apenas na extremidade “início”.

A implementação pode ser estática (usando um vetor circular) ou dinâmica (com ponteiros) sem diferenças significativas em termos de eficiência, uma vez que estas operações só podem ocorrer nas extremidades da estrutura.

*Ver: Implementação do conceito de FIFO (+)

Implementação dinâmica

typedef struct estrutura
{

TIPOCHAVE chave;
estrutura *prox;

} NO;

typedef struct {

NO* inicio;
NO* fim;

} Fdinam;

// Inicialização da fila dinamica
void inicializarFdinam(Fdinam *f)
{

f->inicio = NULL;
f->fim = NULL;

}

// quantos elementos existem
int tamanhoFdinam(Fdinam f)
{

NO* p;
int tam = 0;
p = f.inicio;
while (p)

{

tam++;
p = p->prox;

}

return(tam);

}

// inserir item ao final da fila dinamica

void entrarFdinam(TIPOCHAVE ch, Fdinam *f)
{

NO* novo;
novo = (NO*) malloc(sizeof(NO));
novo->chave = ch;
novo->prox = NULL;
if(f->fim) f->fim->prox = novo; // fila não é vazia
else f->inicio = novo; // 1a. inserção em fila vazia
f->fim = novo;

}

// retirar a chave da frente ou -1
TIPOCHAVE sairFdinam(Fdinam *f)
{

NO* aux;
TIPOCHAVE ch;
if(!f->inicio) return(-1);
ch = f->inicio->chave;
aux = f->inicio;
f->inicio = f->inicio->prox;
free(aux);
if(!f->inicio) f->fim = NULL; // fila ficou vazia
return(ch);

}

Implementação Estática

typedef struct

{

TIPOCHAVE chave;

} RegistroEstat;

typedef struct

{

int inicio;

int fim;

RegistroEstat A[MAX];

} Festat;

// Inicializacao da fila estática

void inicializarFestat(Festat *f)

{

f->inicio = -1; f->fim = -1;

}

// Inserir novo item ao final

bool entrarFestat(TIPOCHAVE ch, Festat *f)

{

if(tamanhoFestat(*f) >= MAX) return(false);

f->fim = (f->fim + 1) % MAX;

f->A[f->fim].chave = ch;

if(f->inicio < 0 ) f->inicio = 0;

return(true);

}

// Retirar um item da frente ou retornar -1 se vazia

TIPOCHAVE sairFestat(Festat *f)

{

if(f->inicio < 0) return(-1);

int ch = f->A[f->inicio].chave;

if(f->inicio != f->fim) f->inicio = (f->inicio + 1) % MAX; else

{

f->inicio = -1;

f->fim = -1;

}

return(ch);

}

Referência Bibliográfica

Honda, Willian Yukio; Paraboni, Ivandré. ACH2023 – ALGORITMOS E
ESTRUTURAS DE DADOS I. Trabalho Acadêmico, 2011.

Sites Pequisados

www.devmedia.com.br

Deixe uma resposta