ED Fila Pilha Lista Estaticas

Prévia do material em texto

*
*
Estruturas de Dados Elementares
Prof. Bruno Teixeira
*
*
Roteiro
Estruturas de Dados Elementares
Estruturas de Dados Estáticas
Fila Estática
Pilha Estática
Lista Estática
*
*
Estruturas de Dados Elementares
“Uma das formas mais simples de interligar os elementos de um conjunto é através de uma lista. Lista é uma estrutura onde as operações inserir, retirar e localizar são definidas. Listas são estruturas muito flexíveis porque podem crescer ou diminuir de tamanho durante a execução de um programa, de acordo com a demanda. Itens podem ser acessados, inseridos ou retirados de uma lista.” (ZIVIANI, 1992)
*
*
Estruturas de Dados Elementares
Fila (FIFO – First In First Out)
Estrutura de dados onde o primeiro elemento que entra é sempre o primeiro a sair
Pilha (LIFO – Last In First Out)
Estrutura de dados onde o último elemento a entrar é sempre o primeiro a sair
 
Lista 
Estrutura de dados onde os elementos podem entrar e sair em qualquer lugar da lista.
*
*
Estruturas de Dados Estáticas
Listas, filas e pilhas são conhecidas como estáticas quando usamos arranjos (vetores), de maneira que podemos acrescentar ou retirar elementos, mas, sempre com um tamanho máximo pré definido.. 
Por exemplo, um vetor com 100 posições, sempre terá 100 posições, mesmo se você não as utilizar. 
*
*
Estruturas de Dados Dinâmicas
Listas, filas e pilhas são conhecidas como dinâmicas quando usamos ponteiros (ligações), de maneira que podemos acrescentar ou retirar elementos sem ter um tamanho máximo pré definido. 
Por exemplo, uma lista dinâmica, pode, em algum momento da execução do programa, ter 100 elementos, em outro momento ter 550 elementos e em outro momento ter somente um elemento. 
Com estruturas dinâmicas esquecemos a idéia de posição, pois não caracteriza vetor. 
*
*
Filas Estáticas
Façamos um paralelo com um fila bancária. Neste tipo de fila, temos diversas pessoas dispostas uma a uma em fila, esperando o momento do atendimento, salve raras exceções (idosos, gravidez, etc.), todo próximo elemento a ser atendido entrou na fila antes dos elementos que estão atrás dele. 
*
*
Filas Estáticas
Isto significa dizer que, em uma fila, o primeiro elemento a entrar é sempre o primeiro a sair, da mesma maneira, o último elemento a entrar é sempre o último a sair. 
Toda fila possui um início, um fundo e uma quantidade de elementos inseridos nela.
*
*
Filas Estáticas
Entenda a figura abaixo como uma fila, onde o Início e o Fundo estão juntos, isto significa que não temos nenhum cadastro feito até o momento. 
Dentro de cada posição do vetor podemos enxergar o valor “L” (Lixo de memória), quantos também possui valor 0 e o meu vetor(vetor de inteiros) suporta 20 registros.
*
*
Filas Estáticas
Com a chamada a um método inserir desta fila, cadastramos o elemento (38) na posição fundo da estrutura, ou seja, no primeiro lugar (pois fundo possui valor 0), logo após, devemos andar com a variável (entenda como se fosse um ponteiro) fundo para a próxima posição do vetor. Quantos então, deverá ser também incrementado de 1.
*
*
Filas Estáticas
Em uma nova chamada de um método inserir desta fila, cadastramos o elemento (45) na posição fundo da estrutura, ou seja, no segundo lugar (pois fundo possui valor 1), logo após, devemos andar novamente com a variável fundo para a próxima posição do vetor. Quantos então, será também incrementado de 1.
*
*
Filas Estáticas
Imagine que este processo poderá ocorrer diversas vezes, desta maneira, chegará um momento, que a fila esteja disposta da seguinte maneira:
*
*
Filas Estáticas
De acordo com a figura abaixo, temos quantos = 12 valores cadastrados, Fundo também possui valor 12 e início possui valor 0.
*
*
Filas Estáticas
Veja o que acontece se resolvermos retirar algum elemento:
*
*
Filas Estáticas
De acordo com a figura abaixo, após chamada do método retira elemento, a variável início deve ser incrementada de 1 (retirando o primeiro elemento), o topo continua na mesma posição e o quantos deve ser decrementado de 1. 
*
*
Filas Estáticas
Perceba que, quando você inserir o último registro (valor), o fundo será o tamanho da sua fila (vetor). 
Imagine agora que você retire todos os elementos. O que acontecerá com sua fila? Resposta: Início conterá o mesmo valor do fundo, portanto ela estará vazia e cheia ao mesmo tempo, sendo assim, você não conseguirá inserir nenhum elemento, apesar de ter espaço para isso.
*
*
Filas Estáticas
Como resolver este problema? Toda vez que desejar inserir algum elemento pergunte se o Início é igual ao tamanho de sua fila, se for (automaticamente o fundo também o será), substitua fundo e início pelo valor 0. Assim você estará recomeçando sua fila. Outra maneira de resolver este problema é a implementação de fila usando alocação dinâmica de memória.
*
*
Exercício
Você foi contratado para implementar uma solução para gerenciar uma fila de espera de um CALL CENTER. 
Ao ligar para o CALL CENTER o cliente informa NOME, CPF, DATA DE NASCIMENTO e NATUREZA DA SOLICITAÇÃO (suporte, reclamação, solicitação, etc.). 
A partir disso, o cliente aguarda na fila para ser atendido.
O atendente irá resolver os chamados de acordo com a ordem de chegada.
Neste sentido, seu sistema deve contar com as seguintes funcionalidades (menu):
Inserir cliente na fila
Pesquisar cliente
Imprimir lista de espera
Atender próximo da fila
Imprimir tamanho da fila
*
*
Pilhas Estáticas
Fazendo um paralelo com uma pilha de pratos ou um carregamento de veículos automotivos em um caminhão cegonha, notamos que o primeiro elemento que entra é sempre o último que sai, ou até mesmo, o último elemento que entra é sempre o primeiro que sai. 
Isto acontece, porque não há como retirar o primeiro veículo do caminhão, pois todos os demais veículos impedem seu caminho.
*
*
Pilhas Estáticas
A figura abaixo demonstra o início e o topo de uma pilha. 
*
*
Pilhas Estáticas
Uma pilha desenhada de forma linear, é vista da seguinte maneira:
*
*
Pilhas Estáticas
A figura acima está idêntica a uma fila antes de inserir e retirar qualquer elemento, apenas a variável Topo substitui a variável Fundo.
*
*
Pilhas Estáticas
Apesar da semelhança, quando retirarmos algum elemento, não alteramos o valor do início, e sim do Topo, portanto, o valor do quantos sempre corresponderá ao valor do topo. 
Procure desenhar algumas inserções e retiradas em uma pilha, lembrando que, só inserimos e retiramos no Topo.
*
*
Pilhas Estáticas
Pilha com 12 elementos:
*
*
Pilhas Estáticas
Veja o que acontece se resolvermos retirar algum elemento da pilha:
*
*
Exercício
Você foi contratado para implementar uma solução para gerenciar/controlar a carga/descarga de caminhões cegonha. 
Ao carregar o caminhão, cada veículo deve ser cadastrado na ordem de inserção. Os dados a serem armazenados são: MODELO, COR, CHASSI, ANO DE FABRICAÇÃO.
A fim de otimizar o trabalho, ao carregar o caminhão, as montadoras observam a ordem de descarga, uma vez que o primeiro veiculo a ser carregado será sempre o último a ser descarregado. 
Isso facilita o trabalho de entrega, pois um mesmo frete, pode efetuar entregas em várias concessionárias
Neste sentido, seu sistema deve contar com as seguintes funcionalidades (menu):
Inserir carro na cegonha
Pesquisar por carro na cegonha
Listar carros ainda carregados
Descarregar próximo carro
Imprimir quantidade de carros na cegonha
*
*
Listas Estáticas
Imagine uma estrutura de dados onde você possa inserir e retirar elementos em qualquer posição do vetor. 
Imagine que, ao retirar algum elemento especificado pelo usuário (não possuindo posição pré definida), teremos que removimentar os elementos posteriores uma posição à esquerda para mantermos nossa lista organizada. 
*
*
Listas Estáticas
Imagine tambémque, ao inserir algum elemento desejamos que nossa lista permaneça em ordem
Desta maneira teremos que removimentar todos os elementos maiores que o elemento que está sendo inserido uma posição à direita na lista. 
*
*
Listas Estáticas
No exemplo abaixo, temos uma lista com 12 elementos inseridos, como ficaria após retirada do elemento 77 ?
*
*
Listas Estáticas
De acordo com a figura abaixo, removimentamos todos os elementos à direita do elemento retirado para a primeira posição mais à esquerda. Decrementamos o fim e a variável quantos.
*
*
Listas Estáticas
Veja o resultado final abaixo:
*
*
Listas Estáticas
Perceba que, na figura acima, o valor 38 se repete, entretanto, esta posição não será utilizada.
*
*
Exercício
Você foi contratado para implementar uma solução para gerenciar/controlar listas de convidados . 
Uma lista sofre alterações constantemente, devido a vários fatores. Entretanto, esta deve estar sempre organizada.
Os dados dos convidados a serem armazenados são: nome, telefone, empresa e cargo.
Neste sentido, seu sistema deve contar com as seguintes funcionalidades (menu):
Inserir convidado na lista por posição
Pesquisar por convidado (nome)
Pesquisar por posição na lista
Listar convidados
Remover convidado da lista por nome
Remover convidado da lista por posição na lista
Imprimir número de convidados
*
*
Referências
Faria, Esutáqui o São José. “Notas de Aula”. 2002.
 Ziviani, Nívio. “Projetos de Algoritmos com Implementações em pascal e C”. 5ª Edição. São Paulo. Pioneira Informática, 1999.
Bibliografia
- Knuth, D.. “The Art of Computer Programming”. London. Addison-Wesley Publishing Company, 1973.
- Sedgewick, R.. “Algorithms”. London. Addison-Wesley Publishing Company, 1988.
- Von Staa, A.. “Programação Modular”. Rio de Janeiro. Campus, 2000.
- Tanembaum, A. M. & Augenstein, M.J.. “Estruturas de Dados Usando C”. São Paulo. Makron Books, 1995.
- Terada, R.. “Desenvolvimento de Algoritmos e Estruturas de Dados”. São Paulo. Makron Books, 1991.
- Wirth, Niklaus. “Algoritmos e Estruturas de Dados”. Rio de Janeiro. LTC, 1989.
- Cormen, T. H. & Leiserson, C. E. & Rivest, R. L. & Stein, C.. “Algoritmos – Teoria e Prática”. Tradução da 2ª edição americana. São Paulo. Campus, 2002.
- Salvetti, Dirceu Douglas & Barbosa, Lisbete Madsen. “Algoritmos”. São Paulo. Makron Books, 1998.
- Deitel, H.M. & Deitel, P.J.. “C++: Como Programar”. 3ª Edição. Editora Bookman, 2001. - Mizrahi, Victorine Viviane. “Treinamento em Linguagem C++ Módulo 1”. São Paulo. Makron Books, 1995.
- Mizrahi, Victorine Viviane. “Treinamento em Linguagem C++ Módulo 2”. São Paulo. Makron Books, 1995.
- Pappas, Chris H. & Murray, William H. “Borland C++ 4.0”. São Paulo. Makron Books, 1994.
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*