Texto Complementar 10 PILHAS

Prévia do material em texto

Disciplina: 
Estruturas de Dados 
Texto Complementar 
PILHAS 
 
 
- Objetivo desta leitura 
Proporcionar ao aluno uma visão mais abrangente sobre a importância das Estruturas de Dados. 
 
- Com isso você será capaz de (habilidades desenvolvidas): 
Através da presente leitura complementar, o aluno irá aprofundar seus conhecimentos em relação as Estruturas 
de Dados por meio da interpretação das informações e analise dos conteúdos e refletir sobre os resultados obtidos com 
a leitura. 
 
PILHAS 
 
 
Funcionamento 
 
Como já vimos, uma pilha é uma estrutura que permite armazenar dados de maneira que 
possamos recuperar primeiro o último elemento que colocamos nela. Por isso, o primeiro 
elemento colocado é o último que pode ser resgatado. Esse tipo de construção é chamado de 
LIFO, do inglês Last In First Out (primeiro a entrar, último a sair). 
 
Se não tiver a menor idéia do que estamos falando, pense numa caixa de papelão onde quer 
guardar livros. Na caixa cabe um livro deitado direitinho, mas tem altura para armazenar vários. 
Quando tiver um monte de livros nela, só consegue tirar o de cima, certo ? O livro de cima é o 
último que foi colocado lá. O primeiro que foi colocado está lá debaixo de todos os outros e por 
isso é preciso retirá-los todos para ter acesso a ele. 
Curiosidade 
O sistema de arquivo FAT, que foi o do windows e de seu antecessor, DOS, foi introduzido em 
1980 pela própria Microsoft. Hoje o sistema de arquivos padrão é NTFS, mas FAT ainda é 
utilizado na maioria dos pendrives e memórias removíveis como cartões de máquinas 
fotográficas. Nesses sistemas, toda pasta contém duas pastas especiais: "." aponta para pasta 
atual, ".." aponta para pasta mãe. Entrar na pasta ".." tem por efeito sair da pasta atual. 
 
O sistema de arquivos define a maneira com a qual são organizados os dados na memória do 
HD ou pendrive. 
Uma pilha pode ser útil por exemplo quando queremos tratar caminhos de diretórios e arquivos. 
Imagine uma situação na qual temos um caminho, digamos: 
c:\Arquivos de Programas\winamp\plugins 
 
Há quatro elementos aqui: o drive, "c:", e o caminho: "Arquivos de Programas", "winamp" e 
"plugins". 
 
Agora, imagine que queremos, de dentro da pasta plugins, acessar a pasta "c:\Arquivos de 
Programas\winamp\skins". O caminho relativo é "..\skins". Este caminho tem dois elementos, ".." 
e "plugins". Para quem não está acostumado com caminhos de pastas e caminhos relativos, o ".." 
quer dizer "voltar uma pasta". 
 
 
Se tivéssemos o caminho num array, precisaríamos procurar o fim do array, retirar um elemento 
e acrescentar "skins". 
Com uma pilha, o último elemento já está ao alcance das mãos, porque o que nos interessa 
numa pilha é o último elemento colocado. Basta mandar retirá-lo da pilha e empilhar "skins" em 
vez. Duas chamadas de função resolvem a nossa vida. 
 
Pilhas também são super práticas para inverter a ordem de um array. Imagine um array de ints 
ordenados do menor até o maior, e por algum motivo precisamos da ordem inversa, do maior até 
o menor. Basta varrer o array de 0 até o fim e empilhar cada elemento numa pilha, e depois 
retirar os elementos da pilha um a um e adicioná-los ao array, de 0 até o fim. 
 
Estrutura 
 
Antes de começar a implementar qualquer coisa, precisamos parar para pensar um pouco. Como 
vamos implementar isso tudo ? Como vão ser organizados os dados na memória ? A pilha deve 
ter um tamanho máxima e não aceitar mais dados quando estiver cheia ? Como fica uma pilha 
vazia na memória ? 
 
Estas perguntas todas vão orientar o design da pilha. Vamos tentar criar a pilha aos poucos, 
tentando fazer as coisas do jeito óbvio primeiro, vendo quais são os problemas e tentando 
melhorar passo a passo. Vamos cometer erros graves, tropeçar em armadilhas e cair em 
buracos, e encontrar soluções até que consigamos uma versão legal. 
 
 
A primeira idéia que vem à cabeça é manter nossa implementação da aula 18. Tínhamos uma 
estrutura com um array que continha os dados. Nesta implementação, havia um tamanho 
máximo, a pilha podia ficar cheia. Bem, isso não é muito prático... Não sabemos de antemão de 
que tamanho vamos precisar. Pode ser que escolhamos um tamanho X hoje e que funcione para 
algumas tarefas, e que de repente apareça uma tarefa que necessite um tamanho maior. "Basta 
aumentar o tamanho" vocês vão retrucar, mas até onde ? E se precisarmos por algum motivo 
inverter todo o conteúdo de um arquivo de 2GB ? Nossa pilha vai ter que usar 2GB de RAM ? 
Pode funcionar no PC barrudo que realize esta tarefa, mas quero poder utilizar nossa pilha em 
outros ambientes. Lembramos que o tamanho da nossa pilha antiga é fixo: uma vez criada, já 
ocupa toda a RAM que vai precisar, mesmo vazia. 
 
Não, não está certo. Precisamos de uma pilha cuja ocupação de RAM seja dinâmica. Uma pilha 
com poucos elementos precisa ocupa pouca memória, uma pilha com muito conteúdo usar mais, 
etc. 
 
Isso quer dizer que precisamos nos livrar daquele array de tamanho fixo. Uma solução legal é ter 
uma corrente de estruturas pequenas: 
 
 
Cada elemento da pilha é contido numa célula (células são às vezes chamadas de nó). Cada 
célula possui um valor e um ponteiro para a próxima célula. A última célula da pilha não aponta 
para nada, seu ponteiro next vale NULL. Um ponteiro NULL sempre é representado por um ponto 
sem seta. 
 
A pilha contém o número de células certo: uma célula por elemento da pilha, sem ocupar 
memória demais. Numa pilha vazia, não há nenhuma célula, e portanto nenhuma memória 
desperdiçada. 
 
A estrutura pode ser descrita em C assim: 
struct cell 
{ 
 int value; 
 struct cell* next; 
}; 
Neste exemplo, a pilha é uma pilha de inteiros. 
O valor carregado por cada célula é do tipo int. 
 
Com esse tipo de estrutura, fica fácil alocar e desalocar células com malloc e free. Ao inserir um 
novo inteiro na pilha, precisamos criar uma nova célula, dar ao seu campo value o valor do 
inteiro, e inserir a célula na corrente. Veremos mais tarde onde na corrente inserir a nova célula. 
 
Agora precisamos de um jeito de manipular esta corrente de valores. O programador que usar 
esta nossa pilha vai querer poder ter uma variável que represente sua pilha. Ele vai querer 
inicializar esta variável com uma pilha vazia e chamar funções para empilhar e desempilhar 
coisas usando aquela variável. 
 
Poderíamos imaginar que esta variável seja um ponteiro para o primeiro elemento da corrente. 
Algo do tipo: 
struct cell myStack; 
 
Há duas opçõe óbvia de como fazer, vamos ver primeiro a opção ruim... 
 
 
É tentador fazer isso, porque adicionar um elemento se torna fácil: 
1. Alocar uma nova célula 
2. Fazer o campo value da nova célula o valor a inserir na pilha 
3. Fazer o campo next da nova célula apontar para nada (valor NULL) 
4. Fazer o campo next da célula apontada por myStack apontar para a nova célula 
5. Fazer myStack apontar para a nova célula. 
Em C, isto é: 
void Push(struct cell *s, int v) 
{ 
 struct cell *newCell = malloc(sizeof(struct cell)); 
 newCell->value = v; 
 newCell->next = 0; 
 s->next = newCell; 
 s = newCell; // este e outro problema, 
 // veremos isso mais tarde 
} 
 
Mas tem um problema gravíssimo. As células anteriores são perdidas. Ninguém mais aponta 
para elas, seus endereços foram perdidos. Não há nenhum ponteiro pelo qual podemos acessar 
as três células que já existiam na pilha. E quando isso acontece, já sabe o que é... Vazamento de 
memória ! 
 
Além disso, com esta construção, não há como remover uma célula. Isso também vem do fato 
que as células anteriores não podem ser acessadas. Quando removemos uma célula, 
precisamos do endereço da célula anterior para recolocar myStack. 
 
Em vez daquela situação, precisamos de um jeito de manter um caminho graças ao qual todas as 
células podem seracessadas: 
 
 
Adicionar um valor na pilha nem mais complexo é: 
 
1. Criar uma nova célula 
2. Fazer o campo value da nova célula o valor a inserir na pilha 
3. Fazer o campo next da nova célula apontar para a primeira célula da corrente 
4. Fazer myStack apontar para a nova célula 
O que, em C, se escreve assim: 
 
 
void Push(struct cell *s, int v) 
{ 
 struct cell *newCell = malloc(sizeof(struct cell)); 
 newCell->value = v; 
 newCell->next = s; 
 s = newCell; 
} 
 
Ler o elemento do topo da pilha é trivial: 
 
 
int Peek(struct cell *s) 
{ 
 return s->value; 
} 
 
 
Retirar um elemento é um pouco mais complicado. A primeira coisa que vem à cabeça é: 
 
1. Destruir a primeira célula 
2. Fazer myStack apontar para a segunda célula, que assim se tornaria a primeira. 
Isto em C: 
 
void Pop(struct cell *s, int v) 
{ 
 free(s); 
 s = s->next; 
} 
Não faça isto. 
 
Mas quando fazemos isso, o ponteiro next da primeira célula é destruido junto com ela durante 
o free. E este ponteiro é a única coisa que dá acesso às demais células. Perder este ponteiro, mais 
uma vez, seria um vazamento de memória. Pior, quando chamamos free(s), o que é apontado 
por s (a primeira célula) é apagado da memória, mas scontinua contendo o antigo endereço da 
defunta célula. Tentar acessar o conteúdo de uma célula morta através de snão somente 
é necrofilia, mas é pedir para o sistema ler memória cujo conteúdo se tornou indefinido. Pode ter 
qualquer lixo lá dentro, e provavelmente não o endereço certo da próxima célula como queriamos. 
 
É preciso salvar o valor do campo next primeiro: 
 
1. Salvar o valor do campo next da primeira célula numa variável temporária (este valor é o 
endereço da segunda célula, que logo vai se tornar a primeira) 
2. Remover a primeira célula 
3. Fazer myStack apontar para a segunda célula, que assim se torna a primeira (usando a 
variável temporária) 
Isto é, em C: 
 
void Pop(struct cell *s) 
{ 
 struct cell *tmp = s->next; 
 free(s); 
 s = tmp; 
} 
 
Mas... Sempre vem um "mas", né? Veja como esta função seria usada: 
 
 
void main() 
{ 
 struct cell *myStack; 
 ... 
 Pop(myStack); 
 ... 
} 
 
Como já vimos, passar uma variável como parâmetro de uma função é passar o valor da variável, 
não a variável em si. Aqui o valor contido em myStack é copiado para a variável s da função Pop. 
Podemos alterar s o quanto queremos dentro de Pop, isso não vai afetar o myStack da função main. 
O problema é que queremos alterar sim. Do jeito que está, após a chamada à Pop, myStack acaba 
apontando para uma célula morta, que foi destruida por free. Mais necrofilia, né? 
 
A função Pop poderia retornar o novo ponteiro da pilha, e precaríamos usara Pop assim: 
 
 
struct cell* Pop(struct cell *s) 
{ 
 struct cell *tmp = s->next; 
 free(s); 
 return tmp; 
} 
 
void main() 
{ 
 struct cell *myStack; 
 ... 
 myStack = Pop(myStack); 
 ... 
} 
 
Mas isso é pedir para esquecer de recuperar o valor da função Pop. Já nós mesmo que 
implementamos isso vamos esquecer um dia ou outro. Imagine então quem nunca usou esta pilha e 
está tentando usar pela primeira vez! Não vai dar certo. Isto não é fool proof, é pedir para Murphy se 
manifestar ("se houver algum jeito de fazer que leve a uma catástrofe, alguém vai fazer desse 
jeito"). 
 
A conclusão é que uma pilha não pode ser representado por simples um ponteiro para a primeira 
célula. No módulo 3 veremos que em C++ existe um jeito de alterar o valor de uma variável dada 
em parâmetro de maneira que seja alterada também na função que chamou, mas por enquanto 
vamos ver soluções em C com as ferramentas que já temos. 
 
 
A solução 1 para este grande problema é criar uma nova estrutura que contenha o endereço da 
primeira célula: 
 
 
struct stack 
{ 
 struct cell *first; 
}; 
 
A implementação para adicionar e remover elementos seria então: 
 
 
void Push(struct stack *s, int v) 
{ 
 struct cell *newCell = malloc(sizeof(struct cell)); 
 newCell->value = v; 
 newCell->next = s->first; 
 s->first = newCell; 
} 
 
int Peek(struct stack *s) 
{ 
 return s->first->value; 
} 
 
void Pop(struct stack *s) 
{ 
 struct cell *tmp = s->first->next; 
 free(s->first); 
 s->first = tmp; 
} 
 
E o uso para remover um elemento seria dos mais simples, sem parâmetro extra nem valor de 
retorno a tratar: 
 
 
void main() 
{ 
 struct cell *myStack; 
 ... 
 Pop(myStack); 
 ... 
} 
 
Mas... Mais um "mas...", esta estrutura "intermediária" precisaria ser alocada antes de ser usada e 
também desalocada após uso para evitar vazamento de memória: 
 
 
void main() 
{ 
 struct cell *myStack; 
 myStack = malloc(sizeof(struct stack)); 
 if (myStack == NULL) return; 
 Pop(myStack); 
 free(myStack); 
} 
 
E isso não é lá muito legal. Qualquer trabalho a mais é indesejável e, mais importante, há risco de 
vazamento de memória, o que é péssimo, porque os riscos sempre se tornam realidade uma hora 
ou outra. 
 
< 3: Pilhas (meio) 5: Exercício > 
 
A solução 2 é o uso de ponteiro de ponteiro. Mas primeiro vamos voltar à situação anterior, aquela 
problemática, para relembrar qual era o problema: 
 
 
void Pop(struct cell *s) 
{ 
 struct cell *tmp = s->next; 
 free(s); 
 s = tmp; 
} 
void main() 
{ 
 struct cell *myStack; 
 ... 
 Pop(myStack); 
 ... 
} 
 
O problema é que mudar s dentro de Pop não altera myStack dentro da main. 
Porém myStack deveria ser alterado, porque a primeira célula da pilha mudou. Em vez de 
passar myStack em parâmetro de Pop, podemos passar oendereço de myStack: 
 
 
void main() 
{ 
 struct cell *myStack; 
 ... 
 Pop(&myStack); 
 ... 
} 
 
A Pop precisa então fica assim: 
 
 
void Pop(struct cell **s) // ponteiro para ponteiro 
{ 
 struct cell *tmp = (*s)->next; 
 free(*s); 
 (*s) = tmp; 
} 
 
Aqui, s aponta para myStack, portanto (*s) é o próprio myStack. Eureka! 
 
 
Existe mais uma pergunta a responder: como fica uma pilha vazia? Bem, a responsta praticamente 
já temos: uma pilha vazia não aponta para nenhuma célula. E um ponteiro que não aponta para 
nada precisa estar NULL. Se um ponteiro que não deveria apontar para nada não estiver NULL, ele 
aponta sim para alguma coisa. E sem dúvida é lixo. 
 
Então precisamos tratar isso em todas as três funções: 
 
 
void Push(struct cell **s, int v) 
{ 
 struct cell *newCell = malloc(sizeof(struct cell)); 
 newCell->value = v; 
 newCell->next = (*s); // Se s estiver vazia, vale NULL, o fundo da pilha 
 (*s) = newCell; 
} 
 
int Peek(struct cell **s) 
{ 
 if ( (*s) == NULL ) 
 return 0; // Nenhum elemento 
 else 
 return (*s)->value; // Lendo o valor do primeiro elemento 
} 
 
void Pop(struct cell **s) 
{ 
 struct cell *tmp; 
 
 if ( (*s) == NULL ) 
 return; 
 
 tmp = (*s)->next; // NULL se nao tiver outra celula 
 free(*s); // destroi a primeira celula 
 (*s) = tmp; // NULL se nao tiver outra celula 
} 
 
E para usar isso tudo: 
 
 
void main() 
{ 
 struct cell *s = NULL; 
 Push(&s, 667); 
 Push(&s, 53); 
 Push(&s, 10); 
 
 printf("Topo = %d\n", Peek(&s)); 
 Pop(&s); 
 printf("Topo = %d\n", Peek(&s)); 
 
 getchar(); 
} 
 
Existe um único requisito para que tudo dê certo: o ponteiro para a primeira célula precisa ser 
inicializado com NULL. Isto pode ser um problema, o usuário pode esquecer e comprometer o 
funcionamento de todo o resto. 
 
Bem, se esquecer, merece um tapão na orelha, porque estaria usando uma variável se tê-la 
inicializada. Toda variável precisa receber um valor inicial antes de entrar num cálculo ou de ser 
entregue a uma função. E todo ponteiro precisa ser inicializado com NULL, que seja um ponteiro de 
pilhaou não. 
 
 
Existe mais uma pendência, mas essa é cosmética. Na nossa main declaramos uma pilha 
como struct cell. Isso não é muito claro. Célula ? De que ? Deveríamos dar um nome mais óbvio à 
coisa. stack seria ótimo. Podemos alterar o nome da nossa struct e chamá-la de stack, sim. Mas e 
as células? Pensando bem cada célula é uma pilha por si só, pois tem todas as características. Esta 
é uma estrutura recursiva. Uma pilha é uma célula seguida de outra pilha menor. 
 
Ph34r, uma estrutura recursiva... Não precisa cagar as calças, mesmo que tenha levado uma surra 
na aula 6. Se tiver entendido tudo até agora esta mudança de nome não altera nada. Seu 
entendimento continua válido. 
 
 
Conclusão 
 
Aleluia, agora tudo está certo e funcionando. 
 
Num grande gesto de generosidade, forneço aqui o código completo da pilha. As próximas 
estruturas de dados serão por sua conta! 
 
 
#include<stdio.h> 
#include<stdlib.h> 
 
struct stack 
{ 
 int value; 
 struct stack *next; 
}; 
 
void Push(struct stack **s, int v) 
{ 
 struct stack *newCell = malloc(sizeof(struct stack)); 
 newCell->value = v; 
 newCell->next = (*s); // Se s estiver vazia, vale NULL, o fundo da pilha 
 (*s) = newCell; 
} 
 
int Peek(struct stack **s) 
{ 
 if ( (*s) == NULL ) 
 return 0; // Nenhum elemento 
 else 
 return (*s)->value; // Lendo o valor do primeiro elemento 
} 
 
void Pop(struct stack **s) 
{ 
 struct stack *tmp; 
 
 if ( (*s) == NULL ) 
 return; 
 
 tmp = (*s)->next; // NULL se nao tiver outra celula 
 free(*s); // destroi a primeira celula 
 (*s) = tmp; // NULL se nao tiver outra celula 
} 
 
void main() 
{ 
 struct stack *s = NULL; 
 Push(&s, 667); 
 Push(&s, 53); 
 Push(&s, 10); 
 
 printf("Topo = %d\n", Peek(&s)); 
 Pop(&s); 
 printf("Topo = %d\n", Peek(&s)); 
 Pop(&s); 
 printf("Topo = %d\n", Peek(&s)); 
 Pop(&s); 
 
 // Nesta altura s vale NULL, ou seja a pilha esta vazia 
 
 getchar(); 
} 
 
 
Segue uma ilustração de como vai ficar a estrutura toda passo a passo: 
 
 
 
 
 
 
Link: < http://cpp.drgibbs.com.br/cursos/1-c-para-iniciantes/25-introducao-a-estrutura-de-dados/2-
pilhas-inicio> Acesso em: 01 jan. 2016. 
 
 
	Curiosidade