Juliana Jenny Kolb
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