Estruturas de Dados com
Jogos
Capítulo 3
Filas - Alocação Sequencial e Estática
Seus Objetivos
neste Capítulo
iStochPhoto
• Entender o que é e para que serve uma estrutura do tipo
Fila;
• Desenvolver habilidade para implementar uma estrutura
do tipo Fila, como um Tipo Abstrato de Dados - TAD,
com Alocação Sequencial e Alocação Estática de
Memória;
• Desenvolver habilidade para manipular Filas através dos
Operadores definidos para o TAD Fila;
• Iniciar o desenvolvimento do seu segundo jogo,
referente ao Desafio 2.
O Que É uma Fila?
iStochPhoto
Definição de Fila
iStochPhoto
Definição: Fila
Fila é uma estrutura para armazenar um conjunto de
elementos, que funciona da seguinte forma:
• Novos elementos entram no conjunto sempre no Final da
Fila;
• O único elemento que pode ser retirado da Fila em um
determinado momento, é o Primeiro elemento da Fila.
Do Inglês: Stack, F.I.F.O.
Uma Fila (em Inglês: Queue) é uma estrutura que
obedece o critério First In, First Out - F.I.F.O. Ou seja, o
primeiro elemento que entrou no conjunto será o primeiro
elemento a sair do conjunto.
Retirando e Inserindo Elementos
em uma Fila
A Cobra como uma Fila
iStochPhoto
Inserindo e Retirando
Pedacinhos
Operações de uma Fila
• Insere (F, X, DeuCerto)
• Retira (F, X, DeuCerto)
• Vazia (F)
• Cheia(F)
• Cria (F)
Exercício 3.1
Junção dos
Elementos de Duas
Filas
iStochPhoto
JunçãoDosElementos (parâmetro por
referência F1, F2, F3 do tipo Fila);
/* recebe F1 e F2, e cria F3, com os elementos
de F1 seguidos dos elementos de F2. Ao final da
Operação, F1 e F2 mantém seus elementos
originais, na mesma ordem */
JunçãoDosElementos (parâmetro por referência F1, F2, F3 do tipo Fila) {
Variável ElementoDaFila do tipo Char;
Variável FilaAuxiliar do tipo Fila;
Cria (FilaAuxiliar);
Cria (F3);
/* Passando os elementos de F1 para F3 e também para FilaAuxiliar */
Enquanto (Vazia(F1) == Falso) Faça { // enquanto F1 não for vazia...
Retira(F1, X, DeuCerto); // retira elemento de F1 - retorna valor em X
Insere(F3, X, DeuCerto);
// insere X em F3
Insere(FilaAuxiliar, X, DeuCerto); }; // insere X na FilaAuxiliar
/* Retornando os elementos da FilaAuxiliar para F1 */
Enquanto (Vazia(FilaAuxiliar) == Falso) Faça { // enquanto tiver elemento
Retira(FilaAuxiliar, X, DeuCerto);
// retira X da FilaAuxiliar
Insere(F1, X, DeuCerto) };
// insere X em F1
}
/* idem para F2 */
Exercícios
iStochPhoto
Exercício 3.2
Troca dos Elementos entre Duas Filas
• TrocaDosElementos (parâmetros por referência F1, F2 do tipo Fila);
/* recebe F1 e F2, e troca os elementos: ao final da operação, F1
deverá ter os elementos que estavam em F2 antes do início da
operação, na mesma ordem; e F2 deverá ter os elementos que
estavam em F1 antes do início da operação, também na mesma
ordem */
Fila com Alocação Sequencial e
Estática de Memória
Solução Com Realocação de Elementos
Fila com Alocação Sequencial e
Estática de Memória
Solução Sem Realocação de Elementos
Fila com Alocação Sequencial e
Estática de Memória
Solução Com Vetor Circular
Fila com Alocação Sequencial e
Estática de Memória
Solução Com Vetor Circular
Insere
Exercício 3.5
Operação Insere
Insere (parâmetro por referência F do tipo Fila, parâmetro
X do tipo Char, parâmetro por referência DeuCerto do tipo
Boolean);
/* Insere o elemento X na Fila F. O parâmetro DeuCerto
deve indicar se a operação foi bem sucedida ou não. A
operação só não será bem sucedida se tentarmos inserir
um elemento em uma Fila cheia */
Exercício 3.5
Operação Insere
Insere (parâmetro por referência F do tipo Fila, parâmetro X do
tipo Char, parâmetro por referência DeuCerto do tipo Boolean);
Se (Cheia(F)== Verdadeiro)
Então DeuCerto = Falso;
// se a Fila F estiver cheia...
// ... não podemos inserir
Senão { DeuCerto = Verdadeiro;// inserindo X na Fila F... deu certo..
F.NroElementos = F. NroElementos + 1; // aumenta NroElementos
F.Elementos[ F.Final ] = X;
// insere X no final da Fila F
// avançando o apontador Final... Atenção: o vetor é circular
Se (F.Final == Tamanho)// se Final estiver na última posição..
Então F.Final = 1;
// ..avança para a primeira (1 ou 0???)
Senão F.Final = F.Final + 1; // senão avança para a próxima
}; // fim do senão
} // fim da operação Insere
Exercícios
iStochPhoto
Exercício 3.6, 3.7, 3.8 e 3.9 Operações Retira,
Cria, Vazia e Cheia – Fila com Vetor Circular
Exercício 3.4 TAD Fila com Realocação de
Elementos
Exercício 3.10 Fila em Vetor Circular Sem o
Total de Elementos
Exercício 3.14 Implementar e Testar uma Fila
Abrir a TV
ou Não Abrir a TV?
Exercício 3.11 Número de Elementos de uma
Fila
Exercício 3.12 Mesmo Número de Elementos?
(F1 e F2)
Exercício 3.13 As Filas São Iguais? (F1 e F2)
Projeto
Snake:
Cobra como
uma Fila de
Cores
Diretrizes de Projeto
• Armazene as cores que compõem a Cobra em um TAD
Fila;
• A aplicação e o TAD Fila devem estar em arquivos
separados;
• A aplicação (e outros módulos) deve(m) manipular o
TAD Fila exclusivamente através dos Operadores
Primitivos - Empilha, Desempilha, Vazia, etc. Aumente o
volume da TV apenas pelo botão de volume;
• Inclua no código do TAD Fila somente ações pertinentes
ao armazenamento e recuperação das informações
sobre a Cobra; faça o possível para deixar o TAD Fila o
mais independente possível dos demais módulos;
• Procure fazer a interface do modo mais independente
possível dos demais componentes de software.
Exercícios
Exercício 3.15 Genius (Hasbro / Estrela). Como
resolver com filas?
Exercício 3.16 Outras Aplicações de Filas
Exercício 3.20 Regras e Nome do Seu Jogo
Avanço de
Projeto
Exercício 3.17 Arquitetura
de Software
Exercício 3.21 Iniciar o
Projeto da Interface
Exercício 3.18 Elemento
da Cobra e Comida da
Cobra – Definir os Tipos
Exercício 3.19 Fila de
Elementos Coloridos
Comece a
Desenvolver
Seu Jogo
Agora!
Faça um jogo com a sua cara! Distribua para os
seus amigos!
Estruturas de Dados com Jogos
Aprender a programar pode ser divertido!