Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

Link para esta página de comparações

Ambos lados da revisão anterior Revisão anterior
Próxima revisão		 Revisão anterior
so:biblioteca_de_filas [2021/04/19 08:19] – [Interface] mazieroso:biblioteca_de_filas [2023/03/21 08:37] (atual) – [A entregar] maziero
Linha 1: Linha 1:
 +====== Biblioteca de Filas ======
 +
 +{{:so:ppos_00_queue.mkv |Video deste projeto}}
 +
 +O sistema operacional gerencia muitas filas: de processos prontos, suspensos, dormindo, esperando em semáforos, etc. A estrutura de dados mais adequada para implementar essas filas é uma **lista circular duplamente encadeada**, como indicada na figura abaixo:
 +
 +{{ so:fila-circular.png |}}
 +
 +Este projeto consiste em construir uma pequena biblioteca que ofereça operações básicas de inserção e remoção em uma lista circular duplamente encadeada totalmente escrita em C (padrão C99), usando estruturas e ponteiros. A fila é genérica e pode ser usada para organizar vários tipos de dados.
 +
 +<note important>
 +Esta biblioteca será utilizada em vários outros projetos, portanto capriche na implementação!
 +</note>
 +
 +===== Interface =====
 +
 +A biblioteca a ser construída deverá respeitar rigorosamente a interface definida no arquivo {{so:queue.h|queue.h}} (que não deve ser modificado). Ela deverá ser totalmente escrita em C (C99 ou similar), em um arquivo único chamado ''queue.c'', e deverá funcionar corretamente com o programa de teste {{so:testafila.c|testafila.c}}.
 +
 +Eventuais mensagens de erro devem ser escritas na saída de erro (''stderr'').
 +
 +===== A entregar =====
 +
 +Somente o arquivo ''queue.c'' deverá ser enviado ao professor.
 +
 +===== Exemplos =====
 +
 +Os exemplos abaixo permitem compreender o significado preciso das estruturas e operações a implementar.
 +
 +=== Exemplo 1 ===
 +
 +Uma fila com um único elemento, uma fila vazia e um elemento isolado (elemento fora de uma fila):
 +
 +{{ so:fila-circ-casos.png |}}
 +
 +=== Exemplo 2 ===
 +
 +Inserção de um elemento em uma fila vazia:
 +
 +{{ so:fila-circ-insere-vazia.png |}}
 +
 +Observe que:
 +
 +  * o elemento a inserir deve estar isolado, ou seja, não deve pertencer a nenhuma outra fila;
 +  * o elemento a inserir já existe, ou seja, não há necessidade de alocar memória para ele (''malloc'').
 +
 +=== Exemplo 3 ===
 +
 +Inserção de um elemento no fim de uma fila não-vazia:
 +
 +{{ so:fila-circ-insere-cheia.png |}}
 +
 +=== Exemplo 4 ===
 +
 +Remoção de um elemento da fila, indicado pelo ponteiro aux. Observe que a remoção apenas retira o elemento da fila, sem o destruir, alterar seu conteúdo ou liberar sua memória.
 +
 +{{ so:fila-circ-remove.png |}}
 +
 +<note warning>
 +É importante observar que as operações feitas por esta biblioteca consistem somente de manipulações de ponteiros; portanto, não devem ser feitas alocações/liberações de memória em ''queue.c''. Se seu código estiver usando ''malloc'' ele está **errado**!
 +</note>
 +
 +===== Outras informações =====
 +
 +  * Duração estimada: 6 horas.
 +  * Dependências:
 +    * Conhecimento de linguagem C.