Pilha ligada

Prévia do material em texto

Pilha ligada
Observe a ilustração de uma pilha ligada, na figura – Ilustração de uma pilha ligada.
Customização Dúvidas ao tutorUnidade 2 / Aula 2
Pilhas
100%
Introdução da aula
Pilha
Pilha ligada
Funções “tamanho”, “topo”, “vazia” e
“liberar”
Vídeoaula: Pilha
Conclusão

Fe
ed
ba
ck
Ilustração de uma pilha ligada. Fonte: elaborada pelos autores.
Uma pilha ligada consiste em uma sequência de elementos, denominados nós
(representados por retângulos com uma seta em uma de suas extremidades na figura
– Ilustração de uma pilha ligada).
Cada nó tem uma informação (valor que aparece dentro do retângulo) e um ponteiro
para o próximo nó da pilha (seta na extremidade direita do retângulo). O último nó
da pilha (que está na sua base) aponta para NULL, representando que não existe um
próximo nó na pilha. 
A pilha propriamente dita é representada apenas por um ponteiro para o nó do que
está no topo da pilha, chamado de Topo na figura – Ilustração de uma pilha ligada.
Unidade 2 / Aula 2
Pilhas
100%
Introdução da aula
Pilha
Pilha ligada
Funções “tamanho”, “topo”, “vazia” e
“liberar”
Vídeoaula: Pilha
Conclusão
Fe
ed
ba
ck
_______
💭 Reflita
Se em uma ED pilha nós podemos acessar apenas o nó que está em seu topo, como
você faria para acessar os demais elementos da pilha sem perder os elementos?
_______
Chegou a hora de você implementar a sua primeira pilha ligada. Você pode iniciar
criando algumas structs. 
Vamos criar uma struct para representar cada nó da nossa pilha ligada e outra para
representar a pilha propriamente dita. Mas, antes disso, vamos importar todas as
bibliotecas que usaremos nos códigos desta aula.
#include <stdio.h> // para operações de entrada e saída
#include <stdlib.h> // para alocação dinâmica de memória
#include <stdbool.h> // para uso do tipo de dados “bool”
#include <assert.h> // para uso da instrução “assert”
Feito isso, agora podemos observar o conteúdo das structs criadas para a pilha.
struct No {
Unidade 2 / Aula 2
Pilhas
100%
Introdução da aula
Pilha
Pilha ligada
Funções “tamanho”, “topo”, “vazia” e
“liberar”
Vídeoaula: Pilha
Conclusão
Fe
ed
ba
ck
 int info;
 struct No* proximo;
};
struct Pilha {
 struct No* topo;
 int tamanho;
};
A struct “No” é idêntica à que foi criada para a lista simplesmente ligada. A struct
“Pilha” também é bastante similar, diferenciando apenas o nome da estrutura, bem
como o nome do ponteiro para a struct “No”, que aqui se chama “topo”, indicando
que ele aponta para o topo da pilha.
Assim como fizemos com a ED lista, partiremos para a implementação das funções
da pilha, uma a uma, comentando uma delas ao longo do texto. No código – Função
para criar uma pilha vazia, encontra-se o código da função “criar”.
Unidade 2 / Aula 2
Pilhas
100%
Introdução da aula
Pilha
Pilha ligada
Funções “tamanho”, “topo”, “vazia” e
“liberar”
Vídeoaula: Pilha
Conclusão
Fe
ed
ba
ck
Função para criar uma pilha vazia - Fonte: elaborada pelos autores.
Essa função é responsável por instanciar dinamicamente uma variável do tipo struct
“Pilha” na memória (linha 2) e configurar os valores de seus campos. Antes, porém,
de configurar os valores dos campos da struct “Pilha”, é preciso testar se a memória
foi corretamente alocada para a pilha (linha 3). 
O campo “topo”, que é um ponteiro, deve apontar para NULL, uma vez que estamos
criando uma pilha vazia (linha 4).
Analogamente, o campo “tamanho” deve ser inicializado com o valor igual a 0
(zero) – linha 5. Feito isso, deve-se retornar o endereço da memória alocado para a
Unidade 2 / Aula 2
Pilhas
100%
Introdução da aula
Pilha
Pilha ligada
Funções “tamanho”, “topo”, “vazia” e
“liberar”
Vídeoaula: Pilha
Conclusão
Fe
ed
ba
ck
variável do tipo “Pilha” (linha 7). 
Com isso, nós já somos capazes de criar uma pilha vazia na memória do
computador. Passemos, então para a implementação das duas funções mais
importantes da pilha, a saber “empilhar” e “desempilhar”.
O código dessas funções pode ser visualizado no código a seguir:
Funções para empilhar e desempilhar elementos em/de uma pilha. Fonte: elaborada pelos autores.
Unidade 2 / Aula 2
Pilhas
100%
Introdução da aula
Pilha
Pilha ligada
Funções “tamanho”, “topo”, “vazia” e
“liberar”
Vídeoaula: Pilha
Conclusão
Fe
ed
ba
ck
Tanto a função “empilhar” quanto a “desempilhar” inicialmente verificam se o
ponteiro para a pilha passada como parâmetro não é nulo (NULL) – linhas 2 e 12,
respectivamente. 
Feito isso, a função “empilhar” cria um novo nó dinamicamente, o que é feito na
linha 3, por meio da função “malloc”. Caso o novo nó tenha sido criado com
sucesso, isto é, se o valor do ponteiro “novo_no” é diferente de NULL (linha 4),
parte-se para o processo de empilhamento do nó.
Como vimos, em uma pilha os nós são inseridos apenas em seu topo. Por isso, deve-
se apontar o ponteiro “proximo” do novo nó para o topo da pilha (linha 6) e, depois,
apontar o ponteiro “topo” da pilha para o novo nó (linha 7). 
Esse procedimento fará com que o antigo topo da pilha passe a ser o segundo
elemento dela e o novo nó passe a ocupar o topo da pilha. Por fim, incrementa-se o
tamanho da pilha, na linha 8.
A função “desempilhar” faz o inverso da função “empilhar”. Ou seja, ela remove o
elemento que está no topo da pilha, fazendo com que o segundo elemento passe a
ocupar o topo da mesma pilha. Para isso, inicialmente é verificado se a pilha não
está vazia (linha 13).
Uma vez feito isso, cria-se um nó auxiliar que aponta para o topo de pilha (linha 14).
Isso é necessário, pois como o ponteiro “topo” da pilha será atualizado, precisamos
Unidade 2 / Aula 2
Pilhas
100%
Introdução da aula
Pilha
Pilha ligada
Funções “tamanho”, “topo”, “vazia” e
“liberar”
Vídeoaula: Pilha
Conclusão
Fe
ed
ba
ck
guardar a posição de memória do elemento que estava anteriormente no topo. 
Logo após, o valor do elemento que está no topo da pilha é armazenado na variável
“elemento” (linha 15) e o ponteiro “topo” da lista é atualizado (linha 16).
A partir de então, o topo da pilha passa a ser ocupado pelo segundo elemento, caso
haja um. Caso contrário, o topo da pilha passa a ser igual a NULL, indicando que a
pilha está vazia.
Contudo, ainda restam algumas instruções a serem executadas, como decrementar o
tamanho da pilha (linha 17), liberar a memória alocada para o nó que ocupava o topo
da pilha anteriormente (linha 18) e retornar o valor armazenado na variável
“elemento” (linha 19).
Com isso, já podemos começar a usar nossa pilha, cujo código completo se encontra
a seguir, na ferramenta Paiza.io.
Unidade 2 / Aula 2
Pilhas
100%
Introdução da aula
Pilha
Pilha ligada
Funções “tamanho”, “topo”, “vazia” e
“liberar”
Vídeoaula: Pilha
Conclusão
Fe
ed
ba
ck
https://paiza.io/projects/4hmXYfhsa7NO2DQ7yIwAeA
Para usar a ED pilha, crie uma função “main” em seu programa, com o código do
código - Função que usa uma ED do tipo pilha.
Unidade 2 / Aula 2
Pilhas
100%
Introdução da aula
Pilha
Pilha ligada
Funções “tamanho”, “topo”, “vazia” e
“liberar”
Vídeoaula: Pilha
Conclusão
Fe
ed
ba
ck
Função que usa uma ED do tipo pilha. Fonte: elaborada pelos autores.
Inicialmente, cria-se uma pilha vazia (linha 2). Logo após, os elementos 1, 2 e 3 são
empilhados, nessa ordem, por meio da função “empilhar” (linhas 3 a 5). Por fim,
todos os elementos da pilha são desempilhados e impressos na tela (linhas 7 a 9).
Teste o programa no Paiza.io, cuja saída esperada é a impressão dos números 3, 2 e
1, nessa ordem.
Unidade 2 / Aula 2
Pilhas
100%
Introdução da aula
Pilha
Pilha ligada
Funções “tamanho”, “topo”, “vazia” e
“liberar”
Vídeoaula: Pilha
Conclusão
Fe
ed
ba
ck
https://paiza.io/projects/XWGMstczNF1PuSr-7B5Y7A
_______
📝 Exemplificando
A seguir temos um exemplo de algoritmos com ED pilha que seja capaz de imprimir
uma sequência de 5 (cinco) números informados pelo usuário na ordem inversa da
entrada, ou seja, de trás para frente. 
Por exemplo, dada a sequência [1, 2, 4, 0, 3], seu programadeve imprimir [3, 0, 4, 2,
1].
Uma possível solução para esse problema encontra-se a seguir. 
Unidade 2 / Aula 2
Pilhas
100%
Introdução da aula
Pilha
Pilha ligada
Funções “tamanho”, “topo”, “vazia” e
“liberar”
Vídeoaula: Pilha
Conclusão
Fe
ed
ba
ck
Inicialmente, criamos um laço for para ler os dados de entrada, adicionando-os em
uma pilha. Depois, desempilhamos os elementos da pilha, imprimindo-os na tela. A
própria característica da ED pilha fará com que os elementos sejam impressos na
ordem inversa.
Pilha invertida. Fonte: elaborada pelos autores.
O código completo pode ser visto a seguir, utilizando a ferramenta Paiza.io.
Unidade 2 / Aula 2
Pilhas
100%
Introdução da aula
Pilha
Pilha ligada
Funções “tamanho”, “topo”, “vazia” e
“liberar”
Vídeoaula: Pilha
Conclusão
Fe
ed
ba
ck
https://paiza.io/projects/hO3h_zwmGA37gzIag8ItJg
Avalie este conteúdo Escolha de 1 a 5 estrelas
Unidade 2 / Aula 2
Pilhas
100%
Introdução da aula
Pilha
Pilha ligada
Funções “tamanho”, “topo”, “vazia” e
“liberar”
Vídeoaula: Pilha
Conclusão
Fe
ed
ba
ck
Conteúdo anterior Próximo conteúdoUnidade 2 / Aula 2
Pilhas
100%
Introdução da aula
Pilha
Pilha ligada
Funções “tamanho”, “topo”, “vazia” e
“liberar”
Vídeoaula: Pilha
Conclusão
Fe
ed
ba
ck