Filas: mudanças entre as edições
(→Filas) |
|||
| Linha 32: | Linha 32: | ||
:A fila estará contida no vetor, entre o índice '''0''' e '''TAM -1'''. | :A fila estará contida no vetor, entre o índice '''0''' e '''TAM -1'''. | ||
:A parte do vetor ocupada por elementos na fila, ocupam os índices entre '''Início''' e '''Final'''. | :A parte do vetor ocupada por elementos na fila, ocupam os índices entre '''Início''' e '''Final - 1'''. | ||
====Declaração da fila==== | ====Declaração da fila==== | ||
| Linha 49: | Linha 49: | ||
void insere(struct fila *q, int x) | void insere(struct fila *q, int x) | ||
{ | { | ||
q->itens[q->final] = x; | |||
q->final = p->final +1; | q->final = p->final +1; | ||
} | } | ||
</source> | </source> | ||
| Linha 68: | Linha 68: | ||
Inicialmente é definido: | Inicialmente é definido: | ||
q.final = | q.final = 0 | ||
q.inicio = 0 | q.inicio = 0 | ||
A fila está vazia sempre que: | A fila está vazia sempre que: | ||
q.final | q.final = q.inicio | ||
<source lang="c"> | <source lang="c"> | ||
int vazia(struct fila *q) | int vazia(struct fila *q) | ||
{ | { | ||
if (q.final | if (q.final = q.inicio) | ||
return -1; | return -1; | ||
else | else | ||
| Linha 84: | Linha 84: | ||
A qualquer momento, o número de elementos na fila é dado por: | A qualquer momento, o número de elementos na fila é dado por: | ||
q.final - q.inicio | q.final - q.inicio | ||
==Referências== | ==Referências== | ||
Edição das 21h36min 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.
- 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.
Uma pilha é uma lista LIFO (Last In First Out), ou último que entra é o primeiro que sai.
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].
- A fila estará contida no vetor, entre o índice 0 e TAM -1.
- A parte do vetor ocupada por elementos na fila, ocupam os índices entre Início e Final - 1.
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->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;
}
Operação vazia
Verifica se a fila está vazia.
Inicialmente é definido:
q.final = 0 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
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)
