Filas: mudanças entre as edições
(→Filas) |
|||
| Linha 44: | Linha 44: | ||
void insere(struct fila *q, int x) | void insere(struct fila *q, int x) | ||
{ | { | ||
q->final = p->final +1; | |||
q->itens[q->final] = x; | q->itens[q->final] = x; | ||
} | } | ||
</source> | </source> | ||
====Operação remove==== | ====Operação remove==== | ||
| Linha 63: | Linha 62: | ||
Verifica se a fila está vazia. | Verifica se a fila está vazia. | ||
Inicialmente | Inicialmente é definido <tt>q.final = -1</tt> e <tt>q.inicio = 0</tt>. A fila está vazia sempre que <tt>q.final < q.inicio</tt>. | ||
<source lang="c"> | <source lang="c"> | ||
| Linha 74: | Linha 73: | ||
} | } | ||
</source> | </source> | ||
A qualquer momento, o número de elementos na fila é dado por: | |||
q.final - q.inicio + 1 | |||
==Referências== | ==Referências== | ||
Edição das 19h22min 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 e 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,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.
- ↑ 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)
