Filas

Nesse post você encontra alguns exercícios sobre filas (estrutura de dados) extraídos dos livros de Tannenbaum e Zaviani. Se você quer acessar mais exercícios sobre esse assunto acesse nosso índice aqui. O IME-USP possui um conteúdo incrível sobre filas que recomendo você dar uma olhada antes de resolver esses exercícios.

1- Exercícios básicos

Os exercícios abaixo são essenciais para sua formação, portanto, antes de realizar qualquer outro exercício é necessário que no mínimo você tenha implementado uma fila estática e uma fila dinâmica.

---

1.1 – Filas estáticas

Crie um programa para simular uma fila usando um vetor estático. Para isso, resolva os seguintes problemas:

a) Declare um vetor de 10 posições (inteiros)

b) Crie uma função “push” que recebe um inteiro e “empurra” um número para o final da nossa fila. Quando a fila estiver cheia envie um aviso ao usuário.

c) Crie uma função “pop” que remove o primeiro elemento da fila e reposiciona todos os elementos de modo que sempre as ultimas posições estejam vazias. Nessa função, quando a fila estiver vazia, envie uma mensagem ao usuário “A fila está vazia”.

d) Crie uma função que imprime sua fila na tela

e) Crie uma função de busca em que o usuário insere um valor e mostra na tela a posição em que esse elemento se encontra.

---

1.2- Filas dinâmicas

Implemente uma fila dinâmica contendo todas as funcionalidades de uma fila padrão. Para isso, resolvar:

a) Crie um nó padrão da fila.

b) Crie uma função de inicialização da fila vazia

c) Crie uma função push que cria e insere um novo nó para o final da fila.

d) Crie uma função pop que remove o primeiro elemento da fila.

e) Crie uma função de busca em que o usuário insere um valor (inteiro) e o programa retorna a sua posição na fila.

f) Crie uma função que percorre e imprime todos os elementos da fila.

---

2- Problemas

1) Considere a fila estática e a fila dinâmica que foram implementadas nos exercícios anteriores e escreva uma função que inverta a ordem dos elementos da fila.  Por exemplo:

[1] [4] [5] [2] → [2] [5] [4] [1]  

2) Considerando a estrutura de fila dinâmica implementada anteriormente uma função para FurarFila. Essa função deverá inserir um item na primeira posição da fila. Lembre-se que nesse caso estamos desrespeitando o conceito de fila – primeiro a entrar é o primeiro a sair). 

3) No seu sistema operacional ao abrir o “gerenciador de tarefas” você pode exibir os processos que estão em execução, veja como isso é apresentado no windows:

Você já parou pra pensar como é possível executar todos esses aplicativos em apenas um processador? Isso existe graças a uma funcionalidade chamada de tempo compartilhado (“time-shared”). Essa funcionalidade mantém uma sequência de processos em uma fila, esperando para serem executados. Modifique a fila dinâmica que você implementou anteriormente para armazenar as informações desses processos.

{
    id = 104,
    name = "Window manager",
    priority = 4,
    wait = 20
}

Seu programa deverá permitir:

• Incluir novos processos na fila de processo;         
• Matar o processo com o maior tempo de espera;
• Executar um processo (remover da fila)         
• Imprimir o conteúdo da lista de processos.    

4) Uma pode ser representada por vetores (assim como foi implementada anteriormente) e também podemos assumir que ela é “circular”. Isso significa que o primeiro e o ultimo elemento são tratados como pivôs e eles indicam o começo e o fim da fila. Veja um exemplo de representação gráfica:

Esse tipo de representação previne que você deixe espaços vazios no vetor depois de uma operação de desenfileirar. Quando uma fila não é circular (que é o caso do nosso exemplo anterior), entende-se que cada operação Desenfileira deve deslocar para “frente” todo elemento restante de uma fila. Um método alternativo é adiar o deslocamente até que “tras” seja igual ao último índice do vetor. Nesse caso, ocorre e faz-se uma tentativa de inserir um elemento na fila, a fila inteira é deslocada para “frente”, de modo que o primeiro elemento da fila fique na primeira posição do vetor, ou posição 0, caso a implementação seja em C/C++/Java.

Responda as questões:

a) Quais são as vantagens desse método sobre um deslocamente em cada operação Desenfileira?

b) Quais as desvantagens?

5) Implemente uma fila de números inteiros usando apenas arrays (vetores) de 100 posições. Nessa fila a posição zero [0] e posição um [1] são usadas para representar a posição inicial e final da fila respectivamente. O restante das posições [2] até [99] devem conter os elementos do vetor.

Para esse exercício você precisa:

• Demonstre como inicializar esse vetor de modo a representar a fila vazia
• Escreva a função desenfileira → remove elementos da fila;
• Escreva a função enfileira → adiciona elementos a fila.

Respostas

ATENÇÃO: esses exercícios ainda estão em fase de reestruturação e teste. Se você gostou do desafio e gostaria de contribuir entre em nosso github, solucione e envie para nós. Ficaríamos muito felizes em compartilhar seu empenho com nossa comunidade. Em um futuro próximo esses exercícios serão resolvidos e disponibilizados à todos.