Pilhas LIFO em Estruturas de Dados - Conceitos e Implementações

Aula 5 Listas Restritas Pilhas Prof Maurício Duarte UNIVEM Centro Universitário Eurípedes de Marília maurduarteunivemedubr Pilha Conceito Uma Pilha armazena qualquer tipo de dado Inserções e remoções seguem a política lastin firstout LIFO Pilha Conceito Empilhar 10 Topo 0 Empilhar 5 Topo 1 Empilhar 15 Topo 2 Desempilhar Topo 1 4 3 2 1 0 4 3 2 1 0 4 3 2 1 0 4 3 2 1 0 10 5 15 5 10 15 5 10 topo topo topo topo Operações fundamentais numa pilha push insere um elemento na pilha pop retorna e remove o último elemento inserido na pilha Operações auxiliares topo retorna o último elemento inserido na pilha sem removêlo size retorna o número de elementos armazenados pilhavazia retorna a indicação se existe ou não elementos na pilha Pilha Operações Aplicações diretas Histórico de páginas visitadas em um navegador de internet Comando desfazer em editores de texto Chaveamento de processos em um computador Aplicações indiretas Estrutura de dados auxiliar para algoritmos Componente de outras estruturas de dados Pilha Aplicações As pilhas podem ser implementadas alocação estática vetores Alocação dinâmica listas encadeadas Para pilhas implementadas na forma de listas encadeadas basta considerar as operações refletidas em seu conceito insere no fim da pilha topo e remove elementos do fim da pilha topo Em síntese operações na mesma extremidade Pilha Implementações define tam 10 typedef struct int topo int infotam lugar onde serão armaz os dados PILHA Pilha Declaração em Vetor a Criando uma pilha vazia inicialização void Inicializa PILHA p ptopo1 Pilha Operações b Verificando se a pilha está cheia int Cheia PILHA p return ptopotam1 c Verificando se a pilha está vazia int VaziaPILHA p return ptopo1 Pilha Operações d Inserindo elementos em uma pilha int Push PILHA p int v if Cheiap return 0 pilha cheia pinfoptopov return 1 Pilha Operações e Removendo elementos em uma pilha int Pop PILHA p int v if Vaziap return 0 pilha vazia v pinfoptopo return 1 Pilha Operações 1 Implemente as funções referentes a pilhas discutidas nesta aula e elabore uma função main para gerenciálas 2 Considerando as funções push e pop implementadas elabore uma função que receba um número decimal como parâmetro e retorne com o correspondente em binário Veja o esquema Pilha Exercícios Para o número 37 decimal o seu correspondente em binário é 100101 37 2 1 18 2 0 9 2 1 4 2 0 2 2 0 1 2 1 0 Basta inserir os restos das divisões em uma pilha até que o número seja reduzido a 0 em seguida retire os elementos da pilha e concateneos matematicamente para constituírem o número em binário Pilha Exercícios 3 Redeclare uma pilha para que nela armazenemos caracteres letras Em seguida faça as alterações necessárias nas funções push e pop Elabore uma função pode ser a main que receba uma palavra string como parâmetro e retorne se ela é ou não um palíndromo Ex palavra arara palíndromo palavra ovo palíndromo palavra casa não é palíndromo Pilha Exercícios