Estrutura de dados Filas

Fala, meus consagrados! Tudo beleza com vocês?

Já estudamos listas e pilhas, neste artigo, iremos revisar os principais pontos sobre a estrutura de dados filas e responder algumas questões.

Teoria

As filas, ou queues em inglês, são tipos abstrados de dados (TAD). São listas especiais que seguem o princípio FIFO (First-in first-out), onde o primeiro elemento a ser inserido será o primeiro a ser retirado.

Os elementos são adicionados no fim da estrutura e são removidos do início dela. Nas filas, utilizamos uma das extremidades para inserção e a outra para remoção.

Figura 1: estrutura de uma fila.

O príncipio que as filas seguem é FIFO (First In First Out), ou seja, o primeiro elemento a entrar é o primeiro a sair. Como princípio análogo, temos o LILO (Last In Last Out): o último elemento a entrar é o último a sair.

Exemplos de uso:

Controle de documentos para impressão;
Troca de mensagens entre computadores numa rede.

As filas, assim como as pilhas, podem ser implementadas de duas formas:

Forma estática, usando array (vetor); ou
Forma dinâmica, usando lista encadeada.

Podemos ter as seguintes operações para manipulação de pilhas:

Criar fila: informa a capacidade no caso de implementação sequencial (vetor)
Enqueue (enfileirar):
- Adiciona um elemento após o último elemento da fila;
- O elemento a ser adicionado é o parâmetro desta operação;
Dequeue (desenfileirar):
- Remove o elemento que está na primeira posição da fila;
- Retorna esse elemento;
isEmpty: verifica se a fila está vazia;
isFull: verifica se a fila está cheia.

Temos especializações de filas como:

Filas circulares; e
Deques.

As filas circulares ajudam a eliminar o relativo desperdício de tempo da fila sequencial, ocasionado pelos deslocamentos dos elementos das filas às primeiras posições. Podem ser bastante vantajosas ao viabilizar a reutilização das posições desocupadas, sem a necessidade de movimentação de dados.

Figura 2: fila circular.

Os deques (double-ended queues) são filas com dupla terminação, ou seja, é possível operações de inserção e remoção tanto no início da fila quanto no final da fila.

Exemplos de uso:

Canal marítimo ou fluvial;
Servidão com circulação em dois sentidos.

Questões de concursos

[UFSM 2017 UFSM – Técnico de Tecnologia da Informação] Assinale a alternativa que representa uma estrutura de dados em que cada novo elemento é inserido no final da estrutura e retirado no início.

[A] Vetor.
[B] Matriz.
[C] Fila.
[D] Pilha.
[E] Árvore

Comentários:

A questão trouxe a conceituação correta das filas.

Gabarito: letra C.

[SUGEP/UFRPE 2016 UFRPE – Técnico em Tecnologia da Informação] Sobre as estruturas de dados lineares, analise as proposições abaixo.

[4] Uma fila é mais eficientemente implementada, em uma lista simplesmente encadeada, se as remoções são realizadas na cabeça da lista, e as inserções na cauda da lista.

Comentários:

O texto ficou confuso, pois, nas filas, as remoções apenas acontecem na cabeça da lista e as inserções, na cauda da lista. Isso não torna uma fila mais eficientemente implementada. Isso é regra que uma fila deve seguir.

Mas, tirando o rigor dessa explicação, o examinador deu com certo o texto.

Gabarito: CERTO.

[NUCEPE 2018 PC/PI – Perito Criminal – Informática] Acerca da estrutura de dados do tipo filas, considere as operações de inserção e remoção de uma fila F abaixo:

1. enfileira (‘amarelo’, F) 2. enfileira (‘branco’, F) 3. enfileira (‘verde’, F) 4. enfileira (‘vermelho’, F) 5. desenfileira (F) 6. desenfileira (F) 7. enfileira (‘azul’, F) 8. enfileira (desenfileira (F), F)

O resultado final das operações resulta em:

[A] [verde, azul, vermelho].
[B] [branco, azul, amarelo].
[C] [verde, azul].
[D] [amarelo, branco].
[E] [vermelho, azul, verde].

Comentários:

Essa questão requer o uso das operações de enfileirar (enqueue) e desenfileirar (dequeue):

1. enfileira (‘amarelo’, F):
- Cria uma fila com o elemento amarelo;
- Fila: amarelo (elemento mais antigo);
2. enfileira (‘branco’, F):
- Insere o elemento branco no final da lista;
- Fila: amarelo (elemento mais antigo), branco;
3. enfileira (‘verde’, F):
- Insere o elemento verde no final da lista;
- Fila: amarelo (elemento mais antigo), branco, verde;
4. enfileira (‘vermelho’, F):
- Insere o elemento vermelho no final da lista;
- Fila: amarelo (elemento mais antigo), branco, verde, vermelho;
5. desenfileira (F):
- Retira o elemento mais antigo: amarelo;
- Fila: branco (elemento mais antigo atual), verde, vermelho;
6. desenfileira (F):
- Retira o elemento mais antigo: branco;
- Fila: verde (elemento mais antigo atual), vermelho;
7. enfileira (‘azul’, F):
- Insere o elemento azul no final da lista;
- Fila: verde (elemento mais antigo atual), vermelho, azul;
8. enfileira (desenfileira (F), F):
- Temos uma operação de desenfileirar dentro de uma operação de enfileirar;
- Retira primeiro o elemento mais antigo: verde;
- Depois insere o elemento retirado verde no final da lista;
- Fila: vermelho (elemento mais antigo atual), azul, verde.

No final, a fila tem os seguintes elementos: vermelho, azul, verde.

Gabarito: letra E.

[Instituto AOCP 2018 – PRODEB – Analista de TIC II – Construção de Software] Durante a programação de um sistema, é possível usar uma estrutura que utiliza a metodologia denominada de FIFO (First In First Out), sendo que o primeiro que entra é o primeiro que sai, em que os elementos são atendidos sequenciados ou utilizados conforme armazenados.

Essa estrutura denomina-se

[A] Lista.
[B] Lista Encadeada.
[C] Árvore Binária.
[D] Pilha.
[E] Fila.

Comentários:

Se segue o princípio de FIFO, então é fila.

Gabarito: letra E.

[Instituto AOCP 2016 EBSERH – Analista de Tecnologia da Informação – Sistemas Operacionais (Nacional)] Em um sistema de memória virtual que utiliza paginação, todas as molduras de páginas podem estar ocupadas quando requeridas por um processo. Na estratégia de substituição de páginas que substitui a página que está há mais tempo no sistema, utiliza-se a estrutura

[A] FIFO.
[B] Pilha.
[C] LIFO.
[D] Árvore.
[E] Escalonamento.

Comentários:

Quando um elemento está a mais tempo em uma fila, este é o elemento que será retirado primeiro, ou seja, FIFO (o primeiro elemento inserido, o mais antigo, é o primeiro elemento a ser retirado.

Dessa forma, o princípio da estrutura para o caso da questão é o FIFO.

Gabarito: letra A.

[CESGRANRIO 2014 Banco da Amazônia – Técnico Científico – Analise de Sistemas] Considere uma estrutura de fila (disciplina FIFO) de números inteiros com duas operações: INSERE (n) e RETIRA ( ). Considere, também, que a representação do estado da fila em um instante qualquer é realizada listando os elementos, de forma que o primeiro elemento, da esquerda para a direita, é o mais antigo presente na fila.
Se a fila começa vazia, a sequência

INSERE (2)
INSERE (3)
RETIRA ( )
INSERE (1)
RETIRA ( )
INSERE (4)
INSERE (5)
RETIRA ( )
RETIRA ( )

levará a uma fila no estado

[A] 1 2 3 4 5
[B] 2 3 1 4 5
[C] 3 1 4
[D] 4 5
[E] 5

Comentários:

Mais uma questão com operações de enfileirar (enqueue) e desenfileirar (dequeue):

INSERE(2):
- Cria uma fila com o elemento 2;
- Fila: 2 (elemento mais antigo);
INSERE(3):
- Insere o elemento 3 no final da lista;
- Fila: 2 (elemento mais antigo), 3;
RETIRA( ):
- Retira o elemento mais antigo: 2;
- Fila: 3 (elemento mais antigo atual);
INSERE(1):
- Insere o elemento 1 no final da lista;
- Fila: 3 (elemento mais antigo), 1;
RETIRA( ):
- Retira o elemento mais antigo: 3;
- Fila: 1 (elemento mais antigo atual);
INSERE(4):
- Insere o elemento 4 no final da lista;
- Fila: 1 (elemento mais antigo), 4;
INSERE(5):
- Insere o elemento 5 no final da lista;
- Fila: 1 (elemento mais antigo), 4, 5;
RETIRA( ):
- Retira o elemento mais antigo: 1;
- Fila: 4 (elemento mais antigo), 5;
RETIRA( ):
- Retira o elemento mais antigo: 4;
- Fila: 5 (elemento mais antigo).