Ferramentas do usuário

Ferramentas do site


so:biblioteca_de_filas

Biblioteca de Filas

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:

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.

Esta biblioteca será utilizada em vários outros projetos, portanto capriche na implementação!

Interface

A biblioteca a ser construída deverá respeitar rigorosamente a interface definida no arquivo queue.h (que não deve ser modificado). Ela deverá ser totalmente escrita em C (padrão C99), em um arquivo único chamado queue.c, e deverá funcionar corretamente com o programa de teste testafila.c.

Eventuais mensagens de erro devem ser escritas na saída de erro (stderr).

A entregar

Somente o arquivo queue.c deverá ser entregue 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):

Exemplo 2

Inserção de um elemento em uma fila vazia:

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:

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.

É importante observar que as operações feitas pela biblioteca consistem somente de manipulações de ponteiros; portanto, não devem ser feitas alocações/liberações de memória dentro da biblioteca. Se seu código precisar usar malloc é porque ele está errado!

Outras informações

  • Duração estimada: 6 horas.
  • Dependências:
    • Conhecimento de linguagem C.
so/biblioteca_de_filas.txt · Última modificação: 2019/03/15 17:35 por maziero