Estruturas de Dados - Pilha (Vetores)

Olá caros alunos sejam bem-vindos a mais uma aula da nossa disciplina de estrutura de dados hoje nós vamos falar sobre a nossa primeira estrutura de dados que é estrutura de dados pilhas como roteiro da aula de hoje nós temos uma motivação para o uso de pilhas nós vamos entender como vamos implementar essa pilha comum tipo abstrato de dados depois vamos ver algumas aplicações dessa nossa estrutura e depois nós falaremos um pouco sobre detalhes de implementação e um pouco do próprio código dessa estrutura em C Matos Bom primeiramente um pouco de motivação que que é uma pilha uma pilha é uma estrutura de dados II né quando eu digo de né a significa que ela tem no máximo um predecessor cada elemento dessa estrutura tem no máximo um predecessor e um sucessor Então ela é uma estrutura linear na qual inserções e remoções ocorrem no topo da pilha só para entender um pouco o que que é uma pilha Vamos pensar no seguinte cenário Suponha que tem duas pessoas lavando e enxaguando pratos uma pessoa lava prato e a outra pessoa está enxugando os pratos ao terminar de lavar o prato a pessoa que está lavando prato ela pega aquele prato que parou de lavar Terminou de lavar e coloca em cima da pilha de outras provas e a pessoa que está enxugando os pratos o que que ela vai fazer ela vai pegar o o prato que está em cima da pilha e vai começar enxugar em todas as operações de colocar um prato e retirar um prato elas vão ocorrer no topo da pilha isso então eu quero que vocês Imaginem Quando eu digo olha as operações ocorrem do topo da pilha pensa em uma pilha de pratos tá a pessoa não vai pegar o prato do Meio ou prato debate bom então o que que a gente tenha Então as duas pessoas que estão lavando e enxugando prato a pessoa que está lavando o prato quer que ela faça ela terminar de lavar o prato e ela dá um passe o que que significa então o peixe O Peixe significa colocar no topo da pilha um novo prato vamos supor que essa nossa filha ela tem limites então o que que essa pessoa ela precisa se preocupar também ela precisa se preocupar se a pilha não está cheia então por exemplo eu tenho que colocar o prato no topo da pilha se a filha já tiver prato demais eu dou uma parada eu relaxo um pouco provavelmente a outra pessoa que está enxugando ela tá demorando um pouco mais do que eu então o que que essa pessoa que vai fazer ela vai verificar se a filha está cheia se não estiver chegando Ela consegue dar um fosse tão pensem essas duas operações aqui serão implementadas no nosso e no nosso contexto Oi e essa outra pessoa que está enxugando os pratos ela vai pegar uma prato que está no topo da pilha pegar um prato só no topo da pilha significa remover o prato do topo da pilha Essa é a operação pop operação pop significa vou pegar no prato do topo da pilha e vou fazer alguma coisa com ele tá só que para pegar um prato eu tenho que verificar se o prato existe então eu vou dar uma olhada aqui nesse tempo diz se arrepender não está vazia eu sei que eu posso pegar um prato que tá no topo da fila é uma maneira mais específica aqui supondo que eu tenho uma pilha inicialmente vazia o Bush por exemplo do elemento dois significa que após a operação a pilha vai ficar nesse formato aqui então tá aqui a minha pilha e tá aqui o elemento no topo da pilha se eu der um post três então o que que vai acontecer o elemento dois ele vai deixar de ser o topo da pilha por quê Porque o elemento três ele vai passar a ser o topo da pilha se eu colocar um peixe cinco os cinco agora vai passar a ser o topo da pilha vai ficar cima do três e se eu der um copo perceba pop não precisa de nenhum parâmetro por quê Porque se eu vou remover da pilha Só existe uma posição Onde eu posso remover da pilha aqui é doutor então pop significa remover quem está no topo da pilha quem é que está no topo da pilha é o elemento número 5 então eu tiro o símbolo topo E então de volta até apenas os elementos dois e os elementos de três do modo como estava antes de eu colocar o elemento por cinco Então é isso que a pilha todas as operações vão ocorrer no topo dela ah e tem algumas frases que a gente sempre associa quando a gente pensa numa pilha o primeiro elemento a entrar na estrutura de dados no caso a pilha ele tem que ser um último elemento a saída essa estrutura o último elemento a entrar tem que ser então o primeiro a sair da mesma coisa dizer Force Force in last out the last in first out então primeiro entrar tem que ser o último a sair e o último entrar tem que ser o primeiro a sair é um comportamento parecido com o botão de desfazer de qualquer editor de texto você tá lá digitando o seu texto percebeu Ops errei não era com as tempo você precisa dar um contra o z que que eu contra usei vai fazer que eu deixo fazer tanta meu caso é comando de dizer mas tudo bem que que o contra usei vai fazer que vai tirar aquela vai remover aquela última edição que você fez é uma coisa se lembrar é isso é ações de remoções sempre em um mesmo Ponto que no caso é o que eu estou chamando de um Topo da pilha bom então o que é que o nosso tipo abstrato de dados vai ter que implementar o nosso tipo abstrato dele para implementar o exemplos que Eu mencionei anteriormente o is full também mencionei anteriormente print porque eu gosto do printy o peixe para incluir um elemento e um Pop para remover um elemento e daí eu tenho outros métodos que estão por aqui por exemplo eu tenho um método Construtor nós já conhecemos que que é um Construtor serve para gente poder criar instâncias do objeto e temos um método aqui que é o método de instrutor para que serve o método de instrutor o método destrutor serve para gente disal a cara de memórias depois que o programa aqui é seu objeto ou o de leite por exemplo por chamado nesse objeto se alguém chamar de Elite nesse objeto sempre foi alô a dinâmica então o de instrutor vai ser chamado em alguns casos esse de instrutor vai ser chamado por exemplo de uma variável estática quando essa variável sair do escopo e vamos entender só que a gente precisa fazer aqui o jogo falei para vocês em aulas anteriores que tudo que a gente ao acaba usando mil a gente desloca utilizando deles aqui vai ser exatamente a mesma coisa tudo que você coloca no Construtor alocando usando New aqui no destrutor a gente vai deslocar utilizando deles ó e aqui a gente também tem algumas variáveis privadas que que são essas variáveis privadas aqui tem um lento aqui só para eu saber o tamanho ocupado dessa pilha tá já gente fala sobre ele e eu tenho aqui um itemtype* Street você vai ver que esse tentar ipe aqui ele tá aparecendo em todos os lugares O que que significa esse tentar é o tipo da variável que eu estou colocando na pilha ou removendo da pilha eu prefiro colocar itemtype aqui para ficar genérico para não colocar por exemplo Tchau mas no caso da implementação que vocês forem ver no meu na implementação que eu mandei para vocês é o caso da implementação que eu vou que eu dei para vocês o item Type conto h e eu coloquei ele sendo apenas um caractere aqui tem typedef Charme e tentar significa Olha o charme na o itemtype na verdade é como se fosse um apelido aqui puxar então é interessante ver o código de uma maneira mais genérica mas saibam que na verdade nesta implementação aqui porque eu estou usando como itemtype Na verdade é um um caractere Ah tá E aqui dentro desse estética. H tem o que tem justamente essa declaração dessa classe aqui não declarei uma constante aqui Max item só para dizer o tamanho máximo do vetor que eu vou colocar nessa aula de hoje eu vou implementar a pilha como um vetor o tamanho máximo desse vetor vai ser de 100 e entretanto essa pilha não vai ocupar todos esses sem vetores por exemplo se eu e ser um elemento Então dentro da pilha como se tivesse apenas lento é igual a um silencia o segundo esse lento aqui vai virar 2 e assim por diante então Max aí tu vai me dizer quais Qual é o número de elementos aqui no máximo nessa nessa pilha e Olaf vai ser o número de elementos em que realmente estão na pilha naquele determinado o único e nós estamos a prestando demais vamos dar uma olhada aqui nós já falamos sobre o tipo abstrato de dados acho que já ficou claro o que todos esses métodos são e vamos falar agora um pouco sobre a aplicação da estrutura para que serve uma pilha uma pilha na verdade é uma estrutura bastante útil Principalmente quando precisamos garantir alinhamento de componentes em processos O que que significa isso significa que se você quiser manter uma alinhamento mas minha mente seria por exemplo Chaves ou parentes uma linguagem de programação todos os escopos precisam estar bem alinhado se um escopo se abre ele se fecha aqui se por exemplo eu abrir algo que seja um parênteses aqui ele tem que se fechar antes de eu poder fechar essa chave então eles têm que estar alinhado se ao invés de fechar o parênteses aqui ele foi fechado bem aqui isso significa que ele não estará ele não está alinhado tá então é isso aqui está bem alinhado Enquanto aqui isso aqui não está bem adiantado uma pilha é muito útil para verificar se este alinhamento ele não foi violado bom então adiamentos a gente usa bastante pilhas chamadas de funções da execução de programas que na verdade também é uma espécie de alinhamento a gente chama uma função essa função se essa função chama outra então essa outra precisa retornar para anterior retornar Então as funções a que as chamadas de funções fragmentadas análise de sintaxe de linguagens de programação por conta por exemplo dos escopos um escopo se fecha o que eu falei agora da chave dos parentes e verificação de alinhamento de parênteses em Strings e agora que a gente já entendi mais ou menos um de a gente usa uma pilha Vamos falar agora sobre alguns detalhes de implementação nós implementar emos na aula de hoje uma pilha comum vetor coisa que eu acabei de adiantar para vocês a posição do topo da pilha Ela depende do número de elementos que estão na pilha que que eu quero dizer com isso você vai entender Já já só saiba isso a posição do topo da pilha Depende o número de elementos nessa pilha na nossa implementação com de todos nós queremos o que nós queremos que inserções e remoções ou povão em tempo constante e outras palavras independem do número de elementos na estrutura o tanto na nossa implementação com vetor quanto na nossa implementação com lista encadeada que eu vou propor para vocês em aulas futuras nós queremos que interações e remoções na pilha ocorram sempre em tempo constante e e aqui tem um cenário só pra gente entender mais ou menos como vamos implementar temos aqui um vetor toda vez que eu devo um curso por exemplo se eu tô tá vazio toda vez que eu devo post 35 quem vai ser o topo da pilha vai ser o elemento para Acabei de inserir o 35 Ah tá eu 35 ele está em que posição está numa posição que eu posso achar usando o número de elementos do vetor só tem um elemento no vetor ele tá na posição um o topo da pilha eu vou colocar agora o 10 o número de elementos no vetor passou de um para dois o tamanho do vetor número de elementos passou de um para dois o índice do elemento que estava no topo da pilha também mudou como eu acho assim de Sônia anteriormente ele tava no índice zero quando eu só tinha um elemento agora eles estão no índice um quando eu tenho dois elementos E se eu colocar mais elementos por exemplo eu coloquei o 94 12:45 Quantos elementos eu tenho aqui um dois três quatro cinco Qual é a posição que está no topo da pilha Ah tá é o elemento 45 que estão no topo da pilha ele tem o índice 4 Isso quer dizer então o que que se eu tiver a variável lento bem preenchida tal número de elementos nesse meu vetor então eu consigo achar o elemento que está no topo por quê Porque ele está na posição lenta menos um então isso quer dizer que eu só preciso de um atributo para saber quem está no topo da pilha e como esse atributo eu sei como colocar elementos e como remover elementos por quê Porque para colocar a memento basta colocar na posição leite e depois de incrementar O Lento é precisar eu coloquei mais um se eu quiser remover um elemento basta eu remover Quem tá na posição lento menos um e depois da incrementar o lenço 1 bom então é simplesmente isso e como nós implementamos essa ideia vou dar uma olhada aqui no nosso código eu vou colocar o código CPP então eu tô step trás vetor. CPP aqui dentro desses Tec vetor.

CPP já falei em aulas anteriores O que que tem que ter a primeira vez ele vai ter que ter um implante para os segue. H que que tem mais daquele tem um implante para aí ou extrair para eu poder jogar coisa na saída padrão e aquele tenha se usa e nem me Space SPD Para quê Para eu colocar se out ao invés de St de dois pontos: altos e e o que é que eu preciso colocar no Construtor nesse Construtor eu vou precisar criar a estrutura a vocação que eu estou fazendo há uma alocação dinâmica no. hu Eu apenas declarei o nome da variável o nome da variável do que eu coloquei no ponto H era stripper e eu declarei aqui essas Tracker seria um ponteiro e agora eu estou declarando eu estou a fazendo ao a questão utilizando New então New e tem Type que na verdade é um apelido para caracteres Nossa tirar e eu coloco aqui o Max ai tons que eu declarei como constantes de valor sem então isso daqui faz alocação dinâmica do meu vetor dentro do Construtor e aqui eu coloco lendo igual a zero por quê Porque eu não coloquei nada nessa pilha Então eu tenho espaço para 100 elementos mas por enquanto ele está vazio depois que sai do Construtor no destrutor o que que eu faço e como não Construtora teclado em 1 mil no destrutor tendo que colocar um deles então não deixa eu coloquei Phillips coloquei assim táxi aqui para deletar um Array e eu quero dizer quem é que eu quero que ele delete que é o Stitch que foi alocado aqui sim e não pensa em isso para não se perder mil no controle do Construtor significa de elite no de instrutor o que mais existem as funções exemplos e esse full declarados lá no nosso tipo abstrato de dados como eu verifico se está vazio se o lenço foi igual a zero significa que tá vazio então retorna Então coloca o Victor bem aqui nem igual é igual a zero isso vai me devolver trouxe lente foi igual a zero e false Caso contrário eu já retorno esse resultado para verificar se está cheio faço a mesma coisa se o lento foi igual a Max ainda mas Deus é que tá cheio caso contrário não tá cheio na consigo colocar mais um essa verificação eu uso no push e no ponto que também são comando são métodos bastante simples no push eu quero colocar um novo item então quê que eu faço o primeiro eu verifico se não está cheio se não estiver cheio então eu faço aquilo que eu disse para Bom vamos lá eu coloco novo elemento na posição lento Tá que é a posição que tá na frente do elemento que está no topo da pilha Então se o elemento estava no topo era esse Então vou colocar na posição lenta e depois eu acrescento mais oo dizendo que ele sendo Olha eu coloquei mais um se eu coloquei mais um então não importa quando tinha antes eu sei que agora eu tenho mais o caso contrário eu tô estou utilizando Esse trio aqui esse trouxe significa olha vai lançar um erro um erro que pode ser tratado posteriormente por outra pessoa por outro método utilizando um tricats então eu lanço um erro dizendo Olha a pessoa tentou inserir dentro de uma pilha cheia então eu tô lançando um erro programa abortar para essa procurar essa pessoa ou esse outro método que tentou fazer esse essa sensação saiba que é a função dele e tratar esse erro aqui sabe eu poderia pensar em outra coisa poderá simplesmente remover isso daqui e em caso de post em um vetor cheio nada acontece só que eu prefiro seu mais claro possível dizer Olha tem um erro aqui você tentou e não verificou a e agora o pop e o que é que eu pop faço o pop para remover um elemento e retornar percebo Qual é o retorno é 80 Ai tá eu vou pegar o elemento que está no YouTube retornar o pobre verifica primeiro olha está vazio se estiver vazio então lance um erro caso contrário Existe algum elemento realmente para retornar o que que eu vou fazer pegue o elemento que eu coloquei essa elemento na variável passe onde estava o elemento que estão no topo da pilha está na posição lendo - 1 dentro das Trotter Ele está na posição lente menos um tá então pegue esse elemento e coloca na variável passe Porque já já eu vou retornar uma cópia dele depois eu coloco lento menos menos dizendo que eles Jesus principalmente olha remover um elemento então não sei quanto tinha antes agora tem um aumento oi e daí o retorno esse aos para quem pediu um Oi e o próximo passo aqui é o nosso príncipe como é que a gente está imprimindo a gente está imprimindo assim a nossa pilha é um vetor então eu posso fazer um for para interar sobre os elementos do meu Beetle então para I índice zero até um índice menor do que lento ou seja um instrumento menos um jogue o que tá na pilha na saída padrão Ah tá e no final coloca uma quebra de vim aqui para quebrar não ficar o pronto da linha de comando de uma posição errado para isso que foi implementado e para executar essa estrutura não existe Assistec Teste Ponto CPP nesse teste.

CPP eu estou declarando aqui e tentar ele ficar aqui até é uma variável do tipo e tentar que eu sei que tentar epi é um pior depois eu declaro uma variável do tipo estepe que a nossa variável que a gente acabou de criar Então essa é a nossa pilha então o nosso Tarde Nosso tipo abstrato de dados que a gente implementou é para variar dois CEP e eu também declarei o outro isso aqui ai tanto aqui vamos ver onde eu estou usando o estou usando da seguinte maneira eu estou pedindo para o usuário inserir vários caracteres na linha de comando e toda vez que o usuário seria um caracter eu verifico Olha esse caractere é uma quebra de linha se não for uma quebra de guinha eu coloco ele dentro da pia Ah tá então quando os olhos The Winter eu sei que eu vou sair desse olho aqui encontre não der tenta eu em vídeo e depois quer que eu faço eu só tiro da pilha verificando olha enquanto a pilha não estiver vazia eu vou remover o elemento que está na pilha e eu vou imprimir esse elemento que eu acabei de retornar da pilha na saída para ela e vamos ver como isso aqui vai ser comportar e aqui estão os códigos eu vou colocar as gemas +* pontos CPP dizendo olha gemas mais eu vou passar todos os CPS Lembrando que eu não passo o ponto h2g + +*. CPP e aqui eu vou colocar.