Filas: mudanças entre as edições
(→Filas) |
|||
| Linha 15: | Linha 15: | ||
Considere uma fila '''q''' e um item '''x''', a função | Considere uma fila '''q''' e um item '''x''', a função | ||
insere(q, x) | |||
insere o item x na fila q; | insere o item x na fila q; | ||
x = remove(q) | x = remove(q) | ||
remove o item do início da fila; | remove o item do início da fila; | ||
vazia(q) | |||
verifica se a fila está vazia. | verifica se a fila está vazia. | ||
| Linha 26: | Linha 26: | ||
==Imlementação de filas em linguagem C== | ==Imlementação de filas em linguagem C== | ||
Na '''linguagem C''', uma das maneiras de implememtar uma '''fila''' é utilizando ''' | 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>. | ||
====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; | |||
</source> | |||
====Operação insere==== | |||
'''Insere item''' recebido como argumento no '''final da fila'''. | |||
<source lang="c"> | |||
void insere(struct fila *q, int x) | |||
{ | |||
q->itens[q->final] = x; | |||
q->final = p->final +1; | |||
} | |||
</source> | |||
====Operação remove==== | |||
'''Extrai e retorna item''' do '''início da fila'''. | |||
<source lang="c"> | <source lang="c"> | ||
int remove(struct fila *q) | |||
{ | |||
return q->itens[q->inicio]; | |||
q->inicio = p->inicio +1; | |||
} | } | ||
</source> | </source> | ||
==Referências== | ==Referências== | ||
| Linha 44: | Linha 62: | ||
---- | ---- | ||
--[[Usuário:Evandro.cantu|Evandro.cantu]] ([[Usuário Discussão:Evandro.cantu|discussão]]) | --[[Usuário:Evandro.cantu|Evandro.cantu]] ([[Usuário Discussão:Evandro.cantu|discussão]]) 12h16min de 30 de setembro de 2014 (BRT) | ||
---- | ---- | ||
[[Categoria:Estruturas de Dados]] | [[Categoria:Estruturas de Dados]] | ||
Edição das 15h16min 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; </source>
Operação insere
Insere item recebido como argumento no final da fila.
void insere(struct fila *q, int x)
{
q->itens[q->final] = x;
q->final = p->final +1;
}
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;
}
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)
