06-Filas

Prévia do material em texto

1 
}  Tiago Maritan 
}  tiago@ci.ufpb.br 
Universidade Federal da Paraíba 
Centro de Informática 
Departamento de Informática 
Estrutura de Dados 
Filas 
2 
Conteúdos Abordados 
}  O Conceito de Fila 
}  Filas com Representação Sequencial 
}  Filas com Representação Dinâmica 
3 
Filas 
}  Listas que possuem a seguinte característica: 
}  Inserção é sempre feita no final da fila (lista) 
}  Remoção é feita no início da fila. 
}  Analogia: filas do nosso dia-a-dia 
}  Fila de banco, fila de carros num pedágio, etc. 
}  FIFO: First In First Out 
 
fim da fila início da fila 
4 
Aplicações de Filas 
}  Escalonamento de "Jobs": 
}  Fila de processos aguardando os recursos do SO; 
}  Fila de pacotes a serem transmitidos numa rede de 
comutação de pacotes. 
}  Fila de impressão 
 
Operações em uma fila 
}  insere(q, A); 
}  insere(q, B); 
}  insere(q, C); 
}  x = retira (q); 
}  insere(q, D); 
}  insere(q, E) 
6 
Operações com Filas 
}  Interface: 
}  Criar uma fila vazia; 
}  Testar se a fila está vazia; 
}  Verificar se a fila está cheia; 
}  Obter o tamanho da fila; 
}  Consultar o elemento da frente da fila; 
}  Inserir um novo elemento no fundo da fila; 
}  Remover o elemento da frente da fila. 
7 
 
 
 
Filas com Representação Sequencial 
8 
Implementação de Filas Sequenciais 
}  Fila sequencial é uma estrutura com: 
}  Um array (vetor) de elementos; 
}  Dois índices que representam o início e fim da fila; 
# define MAX 100 
 
typedef struct { 
 int item[MAX]; 
 int inicio; 
 int fim; 
 int tamanho; 
} tFila; /* tipo Fila */ 
 
 
Implementação de Filas Sequenciais 
9 
}  Problemas na implementação sequencial: 
}  Quando índice fim possui o valor MAX - 1 não implica, 
necessariamente, que haja MAX -1 elementos na fila. 
}  Isto só é verdade, se índice início possuir o valor zero; 
}  início da fila move-se para a direita a cada retirada de elemento. 
}  Solução: 
}  Implementar como uma fila circular 
¨  Reutilizando as posições já ocupadas pela fila; 
10 
Implementação de Filas Sequenciais 
/* Definição das Operações */ 
//Cria uma Fila 
void cria (tFila *F) { 
 F->inicio = 0; 
 F->fim = -1; 
 F->tam = 0; 
} 
 
//Verifica se a Fila está vazia 
int vazia (tFila F) { 
 if (F.tam == 0) 
 return 1; 
 else 
 return 0; 
} 
//continua... 
11 
Implementação de Filas Sequenciais 
//Verifica se a Fila está cheia 
int cheia (tFila F) { 
 if (F.tam == MAX) 
 return 1; 
 else 
 return 0; 
} 
 
//Obtém o tamanho da Fila 
int tamanho(tFila F) { 
 return (F.tam); 
} 
 
// continua... 
12 
Implementação de Filas Sequenciais 
// Consulta o elemento do início da fila. 
// Retorna 0 se a fila estiver vazia, 1 caso contrário. 
// O parâmetro dado irá receber o elemento do inicio 
int primeiro (tFila F, int dado) { 
 if (vazia(F)) 
 return 0; //Erro: Fila vazia 
 else{ 
 *dado = F.item[F.inicio]; 
 return 1; 
 } 
} 
 
// continua... 
13 
Implementação de Filas Sequenciais 
//Insere um elemento no fim de uma fila 
//Retorna 0 se a fila estiver cheia, 1 caso contrário. 
int insereCirc (tFila *F, int dado) { 
 if (F->tam == MAX) 
 return 0; // Erro: fila cheia 
 
 F->fim = (F->fim + 1) % MAX; //circularidade 
 F->item[F->fim] = dado; 
 F->tam++; 
 return 1; 
} 
 
// continua... 
14 
Implementação de Filas Sequenciais 
//Retira o elemento do início da fila 
//Retorna 0 se a fila estiver vazia, 1 caso contrário 
//O parâmetro dado irá receber o elemento retirado 
int retiraCirc (tFila *F, int *dado) { 
 int res = 0; 
 if (vazia(*F)) 
 return 0; // Erro: Fila vazia 
 
 res = primeiro(*F, dado); 
 F->inicio = (F->inicio + 1) % MAX ; //circularidade 
 F->tam--; 
 return 1; 
} 
15 
 
 
 
Filas com Representação Dinâmica 
Implementação de Filas com Representação 
Dinâmica 
16 
}  Implementa como uma lista com duas cabeças 
}  Uma cabeça aponta para o início da fila 
}  Outra aponta para o fim; 
início fim 
17 
Implementação de Filas Encadeadas 
// Definição da ED Fila Encadeada com Duas Cabeças 
 
typedef struct no { 
 int dado; 
 struct no *prox; 
} tNo; 
 
typedef struct fila { 
 tNo *inicio; /* aponta para o inicio da fila */ 
 tNo *fim; /* aponta para o fim da fila */ 
 int tam; 
} tFila; /* tipo fila */ 
 
 
18 
Implementação de Filas Encadeadas 
/* Definição das Operações */ 
//Cria uma Fila 
void cria (tFila *F) { 
 F->inicio = NULL; 
 F->fim = NULL; 
 tam = 0; 
} 
 
//Verifica se a Fila está vazia 
int vazia (tFila F) { 
 if (F.tam == 0) 
 return 1; 
 else 
 return 0; 
} // continua... 
19 
Implementação de Filas Encadeadas 
//Obtém o tamanho da Fila 
int tamanho (tFila F) { 
 return F.tam; 
} 
 
// Consulta o elemento do início da fila 
// Retorna 0 se a fila estiver vazia, 1 caso contrário 
// O parâmetro elem recebe o elemento início 
int primeiro (tFila F, int *elem) { 
 if (vazia(F)) 
 return 0; //Erro: Fila vazia 
 
 *elem = (F.inicio)->dado; 
 return 1; 
} 
// continua... 
20 
Implementação de Filas Encadeadas //Insere um elemento no fim de uma fila //Retorna 0 se a mem. for insuficiente, 1 caso contrário 
int insere (tFila *F, int valor ) { 
 tNo *novoNo; 
 novoNo = malloc(sizeof(tNo)); 
 if (novoNo == NULL) 
 return 0; // erro: mem. insuficiente 
 
 novoNo->dado = valor; 
 novoNo->prox = NULL; 
 if (vazia(*F)){ //Inserção em fila vazia 
 F->inicio = novoNo; 
 F->fim = novoNo; 
 } else { 
 (F->fim)->prox = novoNo; // liga com a fila 
 F->fim = novoNo; // atualiza o novo fim. 
 } 
 F->tam++; 
 return 1; 
} 
21 
Implementação de Filas Encadeadas 
//Retira o elemento do início da fila 
//Retorna 0 se a fila estiver vazia, 1 caso contrário 
//O parâmetro valor irá receber o elemento retirado 
int retira (tfila *F, int *valor ) { 
 tNo *aux ; 
 int res; 
 if (vazia(*F)) {return 0;} //Erro: Fila vazia 
 
 res = primeiro(*F, valor); 
 if (F->inicio == F->fim) // Fila com 1 elemento 
 F->fim = NULL; 
 
 aux = F->inicio; 
 F->inicio = aux->prox; 
 F->tam--; 
 free(aux); 
 return (1); 
} 
22 
}  Tiago Maritan 
}  tiago@ci.ufpb.br 
Universidade Federal da Paraíba 
Centro de Informática 
Departamento de Informática 
Estrutura de Dados 
Filas