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.
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.
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).
No final, a fila tem o seguinte elemento: 5.
Gabarito: letra E.
Então é isso!
[]s e até a próxima!
_________________________
Professor Rogerão Araújo
Participe da conversa