pilha estrutura de dados

Prévia do material em texto

Estrutura de dadosEstrutura de dados
Pilha Pilha 
20132013
Prof Melo
Apresentação
• Técnico em Desenvolvimento de Sistemas - Ibratec, Recife-PE
• Bacharel em Sistemas de Informação – FIR, Recife-PE
• Especialista em Docência no Ensino Superior – Faculdade 
Maurício de Nassau, Recife-PE
• Mestre em Ciência da Computação – UFPE/CIN, Recife-PE
• Currículo Lattes http://lattes.cnpq.br/0759508594425296)
• Homepage https://sites.google.com/site/hildebertomelo/
Disciplinas Lecionadas
• Desenvolvimento de Aplicações Desktop
• Programação Orientada a Objetos
• Estrutura de Dados
• Tecnologia da Informação & Sociedade
• Sistemas Operacionais
• Sistemas Distribuídos
• Introdução a Informática
• Lógica de Programação
• Informática Aplicada a Saúde
• Banco de Dados
• Projeto de Banco de Dados
• Análise de Projetos Orientado a Objetos
• Programação Cliente Servidor
• Linguagens de Programação: C, C#, Pascal, PHP, ASP, Delphi, Java, JavaScript
• Programação WEB
PILHA
• Uma pilha é um tipo especial de lista linear em que todas as 
operações de inserção, remoção ou consulta são realizadas em 
uma só extremidade, denominada TOPO.
• Cada vez que um novo elemento deve ser inserido na pilha, ele é
colocado no seu topo; e em qualquer momento, apenas aquele 
posicionado no topo da pilha pode ser removido. Percebemos 
claramente um padrão de comportamento que indica que o 
último elemento a ser inserido (empilhado), é o primeiro 
elemento a ser removido. Esse é o motivo das pilhas serem 
também referenciadas como uma estrutura LIFO (‘Last In, First 
Out’).
PILHA
• Por definição, uma lista LIFO é uma estrutura dinâmica, ou seja, é uma 
coleção que pode aumentar e diminuir durante a sua existência. Aliás, o 
nome pilha, usado como sinônimo para lista LIFO, advém justamente da 
semelhança entre o modo como as listas LIFO crescem/diminuem e o 
modo como as pilhas no mundo real, funcionam, O exemplo mais 
comum do quotidiano e uma pilha de pratos, porque ela aumenta e 
diminui somente por um único lado: o seu topo. Nessa analogia, 
percebemos que o topo é o que se movimenta, e não a base.
• Por definição, uma lista LIFO é uma estrutura dinâmica, ou seja, é uma 
coleção que pode aumentar e diminuir durante a sua existência. Aliás, o 
nome pilha, usado como sinônimo para lista LIFO, Advém justamente da 
semelhança entre o modo como as listas LIFO crescem/diminuem e o 
modo como as pilhas, no mundo real, funcionam.
PILHA
• Uma pilha suporta três operações básicas, 
tradicionalmente denominadas como: 
• - Top: acessa o elemento posicionado no topo 
da pilha;
• - Push: insere um novo elemento no topo da 
pilha;
• - Pop: remove um elemento do topo da pilha.
PILHA
• Exemplos de declaração de uma PILHA em 
C
Typedef struct registro{ 
char nome[60];
int idade;
float salario; 
}tregistro;
Typedef struct pilha{
struct registro dado;
struct pilha *abaixo;
}tpilha;
Tpilha *topo;
Inserir – PILHA - Passos
• Alocar memória para um elemento auxiliar 
do tipo pilha
• Verificar se a PILHA está vazia
–Não – vazia
• Este elemento recém criado deverá apontar o topo da 
pilha
• O topo da pilha deverá apontar para o 
mesmo endereço de memória do elemento 
auxiliar recém criado
Inserir PILHA - PUSH
• void Inserir () {
– Tpilha * aux = (Tpilha *)malloc (sizeof(Tpilha));
– if (*topo != NULL) {
• (*aux).abaixo = *topo;
– } 
– *topo = *aux;
– Scanf(“%s”,(*topo).dado.nome);
– Scanf(“%i”,(*topo).dado.idade);
– Scanf(“%f”,(*topo).dado.salario);
• }
Ler – PILHA - Passos
• Verificar se a PILHA está vazia
–Sim – vazia
• Exibir mensagem de pilha vazia
–Não – vazia
• Exibir as informações do topo da pilha
Ler PILHA - TOP
• void ler () {
– if (*topo != NULL) {
• printf(“%s”,(*topo).dado.nome);
• printf(“%i”,(*topo).dado.idade);
• printf(“%f”,(*topo).dado.salario);
– } else{
• Printf(“Pilha vazia”);
– }
• }
Remover – PILHA - Passos
• declarar um elemento auxiliar do tipo pilha, para 
marcar o topo que deverá ser removido
• Verificar se a PILHA está vazia
– Não – vazia
• Marcar o topo da pilha com a variável auxiliar
• Atualizar o topo da pilha, o topo deverá ser o elemento logo 
abaixo do topo
• Devolver a memória do antigo topo (aux)
– Sim
• Exibir a mensagem pilha vazia
Remover PILHA - POP
• void remover () {
– Tpilha * aux; 
– if (*topo != NULL) {
• (*aux) = *topo;
• (*topo) = (*topo).abaixo;
• Free(*aux);
– } else{
• Printf(“pilha vazia”);
– }
• }
Destruir - PILHA
• Ao terminar o programa deveremos 
devolver todos os espaços de memória 
requisitados, para isso criaremos um 
procedimento para destruir a PILHA
Destruir - PILHA
• void Destruir () {
• TPilha *aux = (*topo);
• while (*topo != NULL) {
• (*topo) = *topo.abaixo;
• free (*aux);
• *aux = (*topo);
• }
• (*topo) = NULL;
• }
Perguntas...
Bibliografia
• Livro(s) Texto(s):
• PREISS, Bruno R. Estrutura de Dados e 
Algoritmos. Rio de Janeiro: Campus, 2001.
• PEREIRA, Silvio L. Estruturas de dados 
fundamentais. São Paulo: Érica, 2000.
• AZEREDO, Paulo A. Métodos de 
Classificação de Dados e Análise de suas 
Complexidades. Rio de Janeiro: Campus, 
1995.
Bibliografia
• Livros de referencia:
• WEISS, M. A. Data structures and algorithm 
analysis in C++. California: Benjamin/Cummings, 
1999.
• SEDGEWICK, R. Algorithms in C++: Fundamentals, 
data structures, sorting, searching. New York: 
Addison-Wesley, 2001.
• TANENBAUM, Aaron; LANGSAM, Y. & 
AUGENSTEIN, M. Estruturas de Dados usando C. 
São Paulo: Makron Books, 1995.
• LAFORE, R. Aprenda em 24 horas estrutura de 
dados e algoritmo. Rio de Janeiro: Campus, 1999.
• MORAES, Celso R. Estruturas de Dados e 
Algoritmos. São Paulo: Berkeley Brasil, 2001.