Lista 06 - Filas

Essa lista tem como objetivo fixar os conceitos de fila, bem como a implementação de suas operações básicas.

Exercício 01

Implementar em linguagem Python o pseudocódigo do algoritmo Fila visto em sala de aula, com capacidade igual à quantidade de caracteres que compõem o seu primeiro nome. Faça também:

1. Teste o método esta_vazia() através do método desenfileirar();
2. Demonstre o enfileiramento de cada um dos caracteres que compõem o seu primeiro nome;
3. Teste o método esta_cheia() através do método enfileirar(valor);
4. Após executar as operações anteriores, demonstre qual elemento está na frente da fila;
5. Execute o método desenfileirar() por três vezes e verifique qual elemento está na frente da fila.

Exercício 02

Considere uma fila circular com capacidade igual a 5 elementos contendo em seu interior a sequência S, A. Responda:

1. Insira a sequência T, C na fila e demonstre esse procedimento através do preenchimento da tabela abaixo:

   fim	elementos
   -	-
   -	-

2. Qual o valor do atributo fim após a inserção da sequência descrita no item 1?

3. Se você fosse desenfileirar() um elemento da fila, qual seria esse elemento?

4. Desenfileirar dois elementos da fila e demonstrar esse procedimento através do preenchimento da tabela abaixo:

   inicio	elementos
   -	-
   -	-

5. Considerando a fila resultante do item 4, insira um novo elemento e demonstre o comportamento circular da fila (quando o atributo fim retorna à posição 0).

Exercício 03

1. O problema de inserir (enfileirar) elementos em uma fila envolve?
2. O problema de retirar (desenfileirar) elementos em uma fila envolve?
3. Qual critério é utilizado para saber se uma fila está vazia?
4. Qual critério é utilizado para saber se uma fila está cheia?
5. Qual é o valor dos atributos inicio, fim e quantidade quando a fila está vazia?
6. Qual é o valor dos atributos inicio, fim e quantidade quando a fila contém apenas um elemento?
7. Qual é o valor dos atributos inicio, fim e quantidade quando a fila está cheia?

Exercício 04

Durante as aulas, usamos as nomenclaturas em português para nos referirmos aos métodos da Fila. No entanto, na literatura, é comum encontrar os nomes em inglês. Preencha a tabela abaixo com os nomes em inglês correspondentes aos nomes em português:

Nome em Português	Nome comum usado em Inglês
Fila
enfileirar
desenfileirar
esta_vazia
esta_cheia
frente
capacidade

Exercício 05

Utilizando a classe Fila implementada no Exercício 01, resolva os desafios abaixo:

1. Ordem de Atendimento: receba uma sequência de clientes e utilize a Fila para atendê-los na ordem de chegada;

   • Entrada: Ana, Bruno, Carla, Diego → Saída: Atendendo: Ana, Atendendo: Bruno, Atendendo: Carla, Atendendo: Diego

2. Inversão de Fila: receba uma sequência de elementos e utilize uma Pilha auxiliar para exibir a fila invertida;

   • Entrada: 1, 2, 3, 4, 5 → Saída: 5, 4, 3, 2, 1

3. Intercalação de Filas: receba duas filas e utilize uma terceira Fila para intercalar seus elementos alternadamente (se uma fila terminar antes, os elementos restantes da outra vão ao final);

   • Entrada: Fila 1: 1, 3, 5 e Fila 2: 2, 4, 6 → Saída: 1, 2, 3, 4, 5, 6
   • Entrada: Fila 1: 1, 3 e Fila 2: 2, 4, 6 → Saída: 1, 2, 3, 4, 6