Filas: mudanças entre as edições

De Wiki Cursos IFPR Foz
Ir para navegaçãoIr para pesquisar
Linha 28: Linha 28:


Na '''linguagem C''', uma das maneiras de implememtar uma '''fila''' é utilizando um '''vetor''' para armazenar a fila e mais '''duas variáveis''' para armazenar o '''início''' e o '''final''' da fila <ref name="TENENBAUM"/> <ref name="FEOFILOFF">FEOFILOFF, p. '''Projeto de algoritmos em C''': Filas. http://www.ime.usp.br/~pf/algoritmos/aulas/fila.html</ref>.
Na '''linguagem C''', uma das maneiras de implememtar uma '''fila''' é utilizando um '''vetor''' para armazenar a fila e mais '''duas variáveis''' para armazenar o '''início''' e o '''final''' da fila <ref name="TENENBAUM"/> <ref name="FEOFILOFF">FEOFILOFF, p. '''Projeto de algoritmos em C''': Filas. http://www.ime.usp.br/~pf/algoritmos/aulas/fila.html</ref>.
[[Arquivo:FilaVetor.png]]


====Declaração da fila====
====Declaração da fila====

Edição das 19h28min de 30 de setembro de 2014

Filas

Uma fila é um conjunto ordenado de itens, na qual itens podem ser extraídos de uma extremidade (início da fila) e novos itens podem ser inseridos na outra extremidade (final da fila) [1].

Como os elementos são inseridos por uma extremidade e extraídos pela outra, este tipo de fila é chamado de lista FIFO (First In First Out), ou primeiro que entra é o primeiro que sai.

Uma pilha é uma lista LIFO (Last In First Out), ou último que entra é o primeiro que sai.


Na figura, A foi o primeiro elemento inserido na fila, será portanto o primeiro a sair. Novos elementos são inseridos no final da fila, ou seja, depois do elemento C. Se A for removido da fila, B passará a ser o primeiro da fila, ou o próximo a sair.

Operações primitivas com filas

As operações primitivas para lidar com filas são para inserir itens, remover itens e verificar se a fila está vazia[1].

Considere uma fila q e um item x, a função

insere(q, x)

insere o item x na fila q;

x = remove(q)

remove o item do início da fila;

vazia(q)

verifica se a fila está vazia.

A operação para remover itens da fila somente pode ser executada se a fila não estiver vazia, por isto a utilizada da função para verificar se a fila está vazia.

Imlementação de filas em linguagem C

Na linguagem C, uma das maneiras de implememtar uma fila é utilizando um vetor para armazenar a fila e mais duas variáveis para armazenar o início e o final da fila [1] [2].

Declaração da fila

Poderíamos declarar uma fila q de inteiros como uma estrutura, com três campos:

#define TAM 100
struct fila {
  int inicio, final;
  int itens[TAM];
} q;

Operação insere

Insere item recebido como argumento no final da fila.

void insere(struct fila *q, int x)
{
   q->final = p->final +1;
   q->itens[q->final] = x;
}

Operação remove

Extrai e retorna item do início da fila.

int remove(struct fila *q)
{
   return q->itens[q->inicio];
   q->inicio = p->inicio +1;
}

Operação vazia

Verifica se a fila está vazia.

Inicialmente é definido:

q.final = -1
q.inicio = 0

A fila está vazia sempre que:

q.final < q.inicio 
int vazia(struct fila *q)
{
    if (q.final < q.inicio) 
        return -1;
    else
        return 0;
}

A qualquer momento, o número de elementos na fila é dado por:

q.final - q.inicio + 1

Referências

  1. 1,0 1,1 1,2 TENENBAUM, A. A.; LANGSAM, Y.; AUGENSTEIN, M.J. Estruturas de dados usando C, capítulo 2: A Pilha, São Paulo: Makron Books, 1995.
  2. FEOFILOFF, p. Projeto de algoritmos em C: Filas. http://www.ime.usp.br/~pf/algoritmos/aulas/fila.html

--Evandro.cantu (discussão) 12h16min de 30 de setembro de 2014 (BRT)