Estruturas de Dados - Pilha (Lista Encadeada)

Olá meus caros alunos na aula de hoje nós vamos retomar os nossos estudos sobre a estrutura de dados pilha só que agora utilizando uma implementação como desista encadeada que aquela implementação que vai nos dar a liberdade de Não precisar dizer Quantos elementos nós temos a nossa pilha a priori nós tentaremos implementar essa pilha tendo reversões em seções em tempo constante do mesmo modo como nós fizemos com a implementação em vetor o roteiro da aula de hoje vai ser o seguinte primeiramente nós vamos ir estudar a estrutura de um nó depois nos falaremos sobre as mudanças

no tipo abstrato de dados depois nós seguiremos para os detalhes de implementação e depois nós falaremos um pouco sobre aplicações dessa nossa estrutura de dados e vamos começar com a estrutura do nó nós sabemos que vamos implementar uma distro emcada da seguinte forma nós teremos um ponteiro para o primeiro elemento da lista que vai ser o nosso a nossa pilha e cada ó ele vai ter que ter uma informação e vai ter que ter uma pontador um ponteiro para o próximo elemento na nossa filha é isso daqui vai caracterizar uma distro encadeada o que nós

vamos estudar primeiramente é como vai ser a implementação desse novo aqui e na parte de informação vamos supor que a parte que está aqui nós utilizaremos aquele nosso ethertype que temos utilizado até agora então nós iremos itemtype vai ser a parte de informação nessa nossa estrutura em cadeado e o que que é o nosso itemtype Nós faremos nosso tentar e pensei aquilo que a gente já utilizava anteriormente Nós faremos com que itemtype sejam apelido para fechar ou seja nessa nossa filha Não achou a crermos caracteres eu só não quero colocar caracteres aqui por quê Porque

eu não quero uma pilha específica para caractere eu quero dar a chance de um desenvolvedor depois mudarem atentai para alguma outra coisa que ele achava necessário sem ter que fazer grandes modificações na estrutura então nós sabemos aqui na nossa parte de informações teremos um atentai só que nós precisamos também ter um ponteiro para next Isso vai ser feito nessa Street aqui e a gente não utilizou Street até agora quê que é na verdade uma estante estou aqui tem uma palavra reservada comum você ser mais mais ele vem você e para nós aqui vamos tentar interpretar

as trouxe como sendo uma estrutura que vai nos ajudar a unir variáveis diferentes num só bloco então em uma mesma região de memória eu vou poder colocar uma itemtype junto com um ponteiro para nos detalhe que é justamente a estrutura que a gente tá precisando criar aqui a gente quer colocar o entende que a nossa informação junto com um ponteiro para o próximo elemento eu poderia ter utilizado uma classe aqui sim eu poderia ter utilizado uma classe não mudaria em nada entretanto se utilizasse uma classe aqui fica aparecendo que ficar um pouco maior do que

o do que o que eu preciso porque normalmente uma classe A gente cria funções antes que a metros desculpa nós temos uma interface público mas é fácil privada aqui eu só preciso das variáveis e todas elas serão públicas facilmente acessíveis por todo mundo que quiser utilizar e deu preferir utilizar uma striptease vem aqui entretanto que a gente vai ver posteriormente você pode imaginar que aqui era uma classe A E aí e com aquela estrutura é possível iniciar o encadeamento a gente só precisa de um ponteiro para o primeiro novo detalhe e o nó de tac

vai apontar para o segundo node Type o segundo não destaque vai apontar para o terceiro node Type e assim por diante como todas as operações vão ocorrer na cabeça da pilha ou seja para o ponteiro que a gente tem que aguardar a gente vai apontar para a cabeça da filha então a gente sabe que vai conseguir implementar tudo isso em tempo constante se quiser inserir já tem um ponteiro apontando para o lugar onde eu quero que esteja inserido se você quer remover também já tem um ponteiro apontando para o elemento que você tem que remover

em outras palavras você não vai precisar Olhar todos os elementos da pilha para poder remover o e sobre o tipo abstrato de dados bem sobre o tipo abstrato de dados a gente não vai mudar nada da classe pública Observe que a gente nem mudou o nome da classe vai ser classe step nada foi mudada na parte pública aqui todos os métodos são exatamente iguais todos eles têm o mesmo nome todos eles têm o mesmo tipo de retorno e todos eles têm um mesmo tipo de parâmetro aqui o que vai mudar na parte privada ao invés

da gente ter um item Type* structure Aqui nós temos um detalhe* Street Aqui ou seja nós temos uma ponteiro para não detalhe anteriormente nós tínhamos um ponteiro para itemtype porque porque Nós criamos uma estrutura de dados de Vetor de e tentar foi isso que a gente fez anteriormente E nós agora que a gente não tem aquela variável inteira chamada lenha é E estávamos anteriormente àquela variável para saber quem é que estava na cabeça da filha aqui tem que já tem um ponteiro para a cabeça da filha então não precisa de uma outra variável só para

dizer quem é que está na cabeça da Bíblia bom então o que é que nós estaremos nós implementamos uma pilha com uma desencadeada o ponteiro esse três sempre apontará para o elemento no topo e assim Sensações e remoções ocorreram em tempo constante é isso que nós temos que ter em mente Vamos falar agora dos detalhes de implementação primeira coisa temos esse step 2 pontos: steck aqui dizendo que nós vamos implementar o Construtor da classe Tech que é o que a gente viu anteriormente o que que nós precisamos fazer nesse Construtor nós temos um ponteiro para

o topo da pilha que por enquanto como ele não foi inicializado Ele está como antes eu vou preferir que ele esteja micelizado com o número para as principalmente dizer ele não tá apontando para lugar nenhum nesse momento porque eu vou fazer isso porque em algum momento eu vou utilizar isso como critério de parado na verdade nos outros algoritmos eu vou utilizar o ponteiro e pula essa ideia de se estiver apontando para nulo é sinal de que eu vou ter que parar algumas coisas alguns laços então eu fiz apenas isso daqui Não precisei por exemplo alocar

nada porque porque eu só vou alocar regiões de memória quando eu precisar inserir um elemento Então como eu não preciso inserir um elemento no Construtor então ele vai ficar apontando para mim e aqui no de instrutor você vai dizer well deixa eu tô ele tem um pouquinho maior do que o que eu estava acostumado anteriormente de instrutor ele apenas deslocava aquilo que o Construtor alocou por quê Porque ela acabamos a priori entretanto agora nós vamos alocar a cada nova inserção Então tem que o destrutor vai fazer o de instrutor vai deslocar tudo aquilo que assim

se ações alocaram e que não foram Claro desalocadas pelas remoções então o que que ele vai fazer ele vai assumir que nós temos uma estrutura encadeada a idade essa estrutura encadeada ele vai varrer do início aqui é o instrutor que uma gente já sabe então nossa variável structure está apontando para cá e ele vai deslocar todos os elementos que foram alocados como eu vou fazer isso eu sei que eu vou ter que varrer a gente tem CAD ata só que ao varrer a desencadeada eu não posso deletar um nó sem ter salvo o nosso e

games Então o que é que eu fiz eu criei uma nova variável que eu chamei aqui de tempo PTR então esse tempo e PTR significa ponteiro temporário vai apontar para o Nokia vai ser removido naquela iteração do laço entretanto antes de deletar eu faço com que os trouxe a ponte para o nosso seguintes Então dentro desse urso enquanto structure for diferente de nulo e o salvo aquele que eu vou deletar então digo tempo e PTR é igual instante esse tempo e PTR vai apontar o preço da pilha depois eu faço a structure apontar para o

próximo elemento E aí sim ou seja não posso deletar antes de fazer isso E aí sim Eu deleto o tempo e PTR por quê Porque eu já estou apontando para o próximo é mesmo e eu faço isso até acabar o número de elementos e vamos falar agora um pouco sobre sintáxi aqui tá e você deve estar botando essa seta aqui a ser menos maior que é uma certa pensa nele com uma seta ao invés de utilizar assim táxi de ponto que nós estamos utilizando anteriormente o que que ocorre aqui ocorre que a gente tem um

node type é só que nós estamos acessando esse nodetype' mediante um ponteiro se eu tivesse pois eu tenho por exemplo novo detalhe um ponteiro para nodetype' é diferente de ter por exemplo uma variável do tipo node Type a diferença e ter por exemplo node Type B se eu quero acessar os campos esse nodetype' quando eu tenho realmente uma variável desse tipo eu posso fazer bebê. Nome do campo por exemplo poderia fazer b.net por quê Porque eu tenho uma variável desse tipo quando eu tenho um ponteiro que no caso do ar eu não posso colocar a.net

eu devo colocar a colocar essa setinha next então Imagine o que Imagine que assim a ideia é semelhante só que anteriormente eu tinha uma variável cujo valor cujo se fala à noite tá que eu poderia usar. Só que agora eu tenho uma variável ponteiro para o nó de thai a história esse campo um atalho é usar essa setinha bem aqui existem mais detalhes que eu poderia falar justamente sobre esse assunto mas eles não interessam agora o que eu preciso que vocês entendam é apenas isso daqui que eu acabei de mencionar bom então vamos seguir para

os próximos metros Lembrando que esses métodos não material de apoio eles já estão dentro dos arquivos dos códigos para você olhar e executar não a de hoje vou preferir ficar olhando para esses slides apenas Mas saiba que você pode acessar os arquivos em si para verificar se a nossa pilha está vazia o que que eu faço eu simplesmente verifico se o meu ponteiro Inicial está apontando para matar nulo se o meu ponteiro Inicial está apontando para nulo Ou seja no está contando para lugar nenhum eu sei que a pilha está vazia Então essa ideia que

eu coloco aqui para verificar se uma pilha está cheia aí você deve imaginar o é mas eu posso ficar colocando todos os elementos que eu quiser na pilha não definir a priori quando a pilha vai estar cheia você pode pensar isso eu vou dizer isso é verdade sempre que você quiser um colocar um novo elemento você pode em uma nova região de memória mas pode haver o caso de que a memória dos vários esteja tão lotada que o sistema operacional vai dizer olha não vou deixar você alocar mais nada aqui na memória tá cheia ou

vai dar um erro qualquer bom então o que que eu vou fazer aqui eu vou no meu esforço o que que eu vou fazer aqui para verificar se eu posso colocar novos elementos eu vou usar um tricats aqui e vou verificar se um erro vai ser dado na hora que eu tentar adicionar uma nova região de memória então o que que eu faço aqui dentro do tracto Troy vai dizer Tente fazer isso aqui em casa o Diego Não faça isso aqui essa ideia do traquete Então vou tentar alocar nós verifique aquilo OK são igual a

new novo detalhe eu vou tentar alocar um novo nodetype' depois eu vou deletar esse nodetype' aí você vai dizer mas porque eu fiz isso porque se eu consegui deletar o esse esse node Type sem ter sido encaminhado para o cat ou seja sem ter dado nenhum erro então eu sei que eu consigo ao local onde estais Então vou dizer um retorno e Pop sendo área da para local ainda mais um na memória você consegue se eu conseguir dentro desse Troy você consegue fora dele essa mais ou menos a ideia dessa dessa linha de código caso

contrário por exemplo caso de algum erro você tentou a local novo nó não tem mais memória sistema operacional deu erro algo aconteceu então você dá obter Nitro disem adora já tá cheio tá cheio aqui por quê Porque eu não consegui alocar um novo nosso sistema operacional avisou se você a creche e o programa Vai abordar Então nem tente já está cheio essa ideia que eu vou utilizar aqui na step essa ideia vou utilizar na fila também na próxima ao você vai se acostumar com ela porque ela vai estar presente em todos os códigos agora em

diante aqui agora vamos falar do post O que é que eu posto tem que fazer eu tenho um ponteiro para a cabeça da pilha e o puxe vai inserir um novo elemento Então tem que eu tenho que fazer eu vou alocar um novo node type em qualquer lugar da memória vou fazer esse nó detalhe apontar para a cabeça da pilha e depois eu vou fazer esse ponteiro está apontando para o elemento que anteriormente ela cabeça apontar para esse elemento que eu acabei de seria em qualquer lugar da memória então como eu vou fazer a infecção

em qualquer lugar da memória com essas linhas e código bem aqui veja o que eu recebi um itemtype que apenas a informação que vai estar um nó não são os ponteiros mas eu vou alocar um node Type aqui node Type location tá E daí eu vou inicializar o o queixo igual a new node time esse mil nome de time vai dizer vou colocar um nodetype' em qualquer lugar da memória não precisa estar contigo esse nó de Itaipu tem um campo chamado info e nesse Campo chamado Limpo é que eu vou colocar um itemtype que aquela

informação que o usuário quer oi e daí eu falo olha o Next desse novo elemento aqui ele tem que apontar para a cabeça da pilha tem a cabeça da pilha é o ponteiro que tá Street então ele tende apontar para onde os brothers está contando mostrou que ser apontava para cá então node Type que foi esse aqui que eu acabei de gerar ele também tem que apontar para cá Só que feito isso eu tenho que atualizar os trouxa ele não tem mais que apontar para cá porque porque esse deixou de ser a cabeça da filha

tem a cabeça da pilha é assim ó então eu faço Extra ter Igual a location porque é porque eu tenho que apontar para esse nome isso claro se não estiver cheio se estiver cheio ou simplesmente o lance uma mensagem de erro dizendo Olha já está cheio bom Então essa é a ideia do poço basicamente que eu fiz aqui são apenas jogadinhas de ponteiros a ir para fazer o pop o que que eu tenho que fazer para fazer o pop eu tenho na minha lista alguém apontando para a cabeça da pilha eu tenho que obter essa

informação aqui para retornar pelo usuário no final da função e eu tenho que fazer esse nó aqui que está contando para essa preço elemento apontar para o próximo elemento feito isso eu não posso esquecer de deletar esse não aqui desalocar a memória como eu sei que eu vou ter que dizer logo a memória Eu Já criei aqui um node Type Tee PPR seguindo a ideia que eu fiz um destino todo esse tempo e PTR ele vai apontar para a cabeça da pilha porque porque no final quando acabar tudo eu vou deletar ele daí eu vou

colocar nesse item aqui a informação que eu preciso mandar de volta para o usuário que estampou a função tá então já salvei ela aqui e depois eu atualizo structure para ela apontar para o segundo elemento e até aqui eu já fiz tudo que precisava ser feito agora eu só preciso dar um jeito termino Entendeu Tchau Tchau veio e eu só preciso desalocar a memória que é o que eu fiz nas próximas linhas de código de um bilhete nessa região e retornei o item que precisava ser retornado é para imprimir o que é que eu vou

fazer para imprimir para imprimir eu vou começar da cabeça da Filha onde é a cabeça da pilha é o structure tá só que eu não vou poder mover o Street de lugar não vou poder fazer nenhuma atribuição para Estreito porque porque isso aqui tá curto bom então o que que eu fiz eu apontei para o do tempo e PTR para cabeça da pilha e daí esse tempo e PTR ele acaba interação ele vai apontar para os outros elementos que também estão na pilha O que é isso que eu vou fazer aqui dentro e vai imprimir

a informação em cada um desses desses Malditos então em quanto tempo em PTBR não por muro já que o último aqui vai apontar para nulo e em quanto tempo e PTR ele não for muro eu imprimo a informação e faça o tempo e PTR a apontar para o próximo elemento Essa é a ideia da impressão e isso é tudo para utilizar essa estrutura basta o mesmo código que a gente utilizava anteriormente se você for olhar esse código aqui ele é exatamente igual ao código que a gente viu na outra aula de pilha com o vetor

ele apenas coloca na pilha e retira da pilha nada vai crescer preciso mudar nesse código aqui e vamos falar um pouco sobre aplicações da estrutura na Bíblia na aula anterior eu falei que a pilha ela é uma boa estrutura para nós verificarmos a questão da sintaxe de parênteses aninhados em Strings Oi e eu vou utilizar Então essa ideia para implementação de agora com pilha só para formalizar um pouquinho mais o que que o que que é esse negócio de parentes desalinhados não a dia hoje eu vou utilizar parênteses Chaves e colchetes eu vou ter que

verificar se eles estão alinhados por exemplo esse daqui existe uma chave de abertura e uma chave de fechamento Então ela tá bem formada tá tudo bem adivinhar nesse daqui existe um colchete da abertura um colchete de fechamento ou Sertão que esse consciente está fechando a ficar testando é ser outro conceito que abriu essa chave de pensamento está prestando essa chave de abertura e assim por diante É eu sei também por exemplo que esse daqui está abrindo esse está pensando e se está abrindo esse está fechando Então está tudo bem formal aqui embaixo tem um pequeno

problema uma chave está abrindo em um colchete está fechando essa abertura E isso está mal formado eu tenho que identificar esse daqui também tem um colchete abrindo uma chave fechando uma chave abrindo um colchete fechando como eu faço isso utilizando a pilha aqui tá o fluxograma do algoritmo que a gente vai seguir supondo que eu tenho* A Chave B ou C antes e depois eu fecho esse consciente eu peço a chave toda ver eu vou ler um caractere de cada vez se for um caracter de abertura eu vou empilhar ou seja se eu for ver

essa chave eu vou empilhar aqui numa pilha Quando eu for e daí eu vou ler o outro caracter é um bebê quando eu ver ele não é nem de abertura e nem de fechamento então não faço nada depois a leitura do concerto o pedido de abertura então hein filho E se o caracter posto de fechamento por exemplo aqui o guia de fechamento então eu vou desempilhar esse daqui Quem é que tá no topo da pilha vou desempilhar e vou comparar com esse caractere que postou e desempilhamento eles formam um parzinho sim se eles formam um

parzinho paciência você pode continuar se eles não formam um parzinho você já sabe que ele é maior formada se ela é mal informada você já sai do já sai do laço você não precisa continuar se você conseguir desempilhar tudo que você precisava por causa da leitura dos caracteres de desempilhamento de fechamento e a pilha estiver vazia você sabe que ela está bem formadas se ela não estiver vazia significa que você colocou mas caracteres de abertura do que caracteres de fechamento então ela não é bem informado Então você viria para cá se a pilha está vazia

Ela é bem informado aqui se ela não está Butter faltam sim bem aqui se ela vazia está bem informada se ela não está vazia ela o formato então eu recomendo tem uma olhada nesse fluxograma aqui só para entender a ideia que eu fiz aqui seja abertura põe na pilha se é qualquer outra coisa não faz nada se é de fechamento tira da pilha e compara para verificar se você está fechando um parzinho de abertura e vamos ver a implementação aqui na nossa implementação eu vou ler caracteres do usuário da mesma maneira que eu fazia antes

então a cada caractere inserido eu lei se o caractere for e enquanto os médicos igual a true ou seja enquanto eu estiver quando tiver uma string é bem informada eu continuo dentro de um laço enquanto o cara que tem uma for Barra em ou seja usuária parou de inserir caracteres EA ideia que é o seguinte a mesma do fluxograma se o caracter for igual a chave de abertura parentes de abertura ou com sede da abertura simplesmente coloque na Bíblia não passa nada não precisa fazer mais nada é só colocar na Bíblia se o caracter por

exemplo que eu acabei de ler por de fechamento Ah tá o que é que eu tenho que fazer se a pena já tiver vazio seja não posso tirar nada da pilha então eu já sei olha eu não consigo parear com ninguém porque porque a pia já acabou então esse de fechamento aqui não tem nenhuma abertura para ele se não desempenho EA pilha e verifique se você está pareado por exemplo esses metros de aqui ele vai devolver true se o o caracter que saiu da pilha estiver fechando o caractere que acabei de seguir Acabei de receber

das 30 então se o carácter estava na pilha era uma chave de abertura e agora eu tenho uma chave de fechamento os mestre guatr ou seja pariu se o caracter que eu tenho agora é um parente de fechamento eu que estava no topo da pilha era um parente de abertura também e se era uma chave de fechamento uma chave de abertura um conceito de fechamento cortei de abertura também qualquer coisa diferente disso não é o clareamento bom então os médicos vai ser boa faux eu vou saber que eu vou sair do laço Então é assim

que eu estou verificando se está havendo um pareamento entre a minha Spring e o que estava na Bíblia basicamente Esse é o corpo Esse é o corpo do nosso código aqui até aqui é repetição do slide anterior não se confundam Então até aqui eu repetir o slide anterior o próximo passo seria continuar lendo alimentos e verificando se está havendo um clareamento quando eu sair do laço que o que que eu tenho que verificar se eu saio do laço Porque não houve o esmalte Ou seja eu já sei que não é bem formata ou se é

porque a pilha está vazia ou melhor eu sair do nosso eu tenho que verificar se a pilha está vazia se aprende está vazia é bem formada por quê Porque eu consumir todos os caracteres de abertura se ela não estiver vazia significa que eu coloquei mais caracteres de abertura e essa é basicamente a ideia EA implementação do algoritmo só para vocês verem uma pilha sendo utilizada numa aplicação real espero que vocês tenham entendido esses conceitos a gente se vê na próxima um abraço e E aí E aí E aí [Música]