03.Pilhas

Prévia do material em texto

Aula 03
Pilhas
Rodolfo Carneiro Cavalcante
Universidade Federal de Alagoas – UFAL
Campus Arapiraca
19 de Abril de 2015
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 1 / 50
Suma´rio
1 Introduc¸a˜o
2 Implementac¸a˜o com Arranjos
3 Implementac¸a˜o com Estruturas Auto-Referenciadas
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 2 / 50
Introduc¸a˜o
Suma´rio
1 Introduc¸a˜o
2 Implementac¸a˜o com Arranjos
3 Implementac¸a˜o com Estruturas Auto-Referenciadas
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 3 / 50
Introduc¸a˜o
Estruturas de Dados Ba´sicas
Conjuntos sa˜o fundamentais para a computac¸a˜o assim como o sa˜o
para a matema´tica
Conjuntos manipulados por algoritmos podem crescer, encolher e
sofrer outras mudanc¸as
Algoritmos exigem va´rios tipos diferentes de operac¸o˜es sobre
conjuntos
Estruturas de dados descrevem conjuntos de dados relacionados entre
si
O estudo de estruturas de dados e´ parte fundamental para o
desenvolvimento de algoritmos
Programas sa˜o compostos por algoritmos e estruturas de dados
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 4 / 50
Introduc¸a˜o
Estruturas de Dados Ba´sicas
As operac¸o˜es sobre conjuntos dinaˆmicos podem ser agrupadas em
duas categorias
consultas – retornam informac¸o˜es sobre os conjuntos
modificac¸o˜es – alteram o conjunto
Operac¸o˜es t´ıpicas
BUSCA(k) – busca por um elemento com valor de chave k e retorna
uma posic¸a˜o ou um ponteiro para o elemento
INSERE (x) – insere o elemento x no conjunto
REMOVE (x) – remove o elemento x do conjunto
MINIMO() – retorna o elemento do conjunto com a menor chave
MAXIMO() – retorna o elemento do conjunto com a maior chave
VAZIO() – verifica se o conjunto esta´ vazio
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 5 / 50
Introduc¸a˜o
Estruturas de Dados Ba´sicas
A escolha de uma estrutura afeta:
quantidade memo´ria para armazenamento
tempo de processamento
Conhecer va´rias estruturas e´ importante
conhecer vantagens e aplicabilidade de cada estrutura
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 6 / 50
Introduc¸a˜o
Estruturas de Dados Ba´sicas
Nesta disciplina sera˜o vistas va´rias estruturas de dados
Vetores
Pilhas
Filas
Listas
A´rvores
Grafos
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 7 / 50
Introduc¸a˜o
Estruturas de Dados Ba´sicas
Vetores
ja´ bem conhecidos
tipo de dados composto homogeˆneo
armazena uma sequeˆncia de objetos de mesmo tipo em posic¸o˜es
consecutivas de memo´ria
estrutura de dados linear e esta´tica
tempo de acesso para ra´pido e constante (acessado pelo ı´ndice do
vetor)
estrutura indicada quando o tamanho e´ sabido de antema˜o e na˜o
mudara´ com frequeˆncia
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 8 / 50
Introduc¸a˜o
Pilhas
Algumas aplicac¸o˜es requerem inserc¸o˜es, retiradas e acessos em apenas
um dos extremos de uma lista
Exemplos:
implementac¸a˜o de recursividade pelo SO
mecanismo de fazer/desfazer de editores de texto
Navegac¸a˜o de pa´ginas Web
Pilhas (stack) sa˜o estruturas de dados LIFO
last-in, first-out
ultimo elemento a entrar e´ o primeiro a sair
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 9 / 50
Introduc¸a˜o
Pilhas
Analogia: pilha de pratos
inserc¸a˜o ou remoc¸a˜o de pratos na pilha e´ mais conveniente na parte
superior
o prato mais recentemente inserido sempre fica no topo, acima dos
demais
o primeiro a entrar e´ o u´ltimo a ser lavado
Existe uma ordem linear para pilhas, que e´ a ordem do “mais recente
para o menos recente”
Essa propriedade torna a pilha uma ferramenta ideal para
processamento de estruturas aninhadas
subestruturas mais internas devem ser processadas antes da estrutura
que as contenham
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 10 / 50
Introduc¸a˜o
Pilhas
Principais operac¸o˜es do TAD pilha:
1 Criar uma pilha vazia
2 Verificar se a pilha esta´ vazia
3 Empilhar o item x no topo da pilha
4 Desempilhar o item x que esta´ no topo da pilha
5 Verificar o tamanho atual da pilha
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 11 / 50
Introduc¸a˜o
Pilhas
Existem va´rias opc¸o˜es de estruturas de dados que podem ser usadas
para implementar pilha
As mais utilizadas sa˜o:
implementac¸a˜o por meio de arranjos (vetor)
implementac¸a˜o por meio de estruturas auto-referenciadas
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 12 / 50
Implementac¸a˜o com Arranjos
Suma´rio
1 Introduc¸a˜o
2 Implementac¸a˜o com Arranjos
3 Implementac¸a˜o com Estruturas Auto-Referenciadas
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 13 / 50
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Utilizac¸a˜o de um vetor para armazenar itens
Itens sa˜o armazenados em posic¸o˜es consecutivas de memo´ria
Inserc¸o˜es e retiradas acontecem na u´ltima posic¸a˜o do vetor (topo da
pilha)
Vetor deve ter tamanho suficiente para armazenar itens da pilha
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 14 / 50
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Implementac¸a˜o da estrutura de dados Pilha (arranjo)
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 15 / 50
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 1: Estrutura de dados Pilha (arranjo)
template <class T> class Pilha{
private:
T *itens;
int topo, maxTam;
public:
Pilha(int maxTam);
bool vazia();
void imprime();
void empilha(T item);
T desempilha();
int tamanho();
};
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 16 / 50
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
a estrutura que guarda a pilha e´ um vetor
T* itens;
o ı´ndice topo indica o topo atual da pilha
o tamanho ma´ximo da pilha (maxTam) e´ usado para indicar o limite
do vetor
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 17 / 50
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Implementac¸a˜o da estrutura de dados Pilha (arranjo)
Func¸a˜o para criar a pilha
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 18 / 50
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 2: Estrutura de dados Pilha: criar pilha vazia
template <class T> Pilha<T>::Pilha(int maxTam){
this->topo=0;
this->maxTam = maxTam;
this->itens = new T[this->maxTam];
};
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 19 / 50
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
O construtor da classe Pilha faz as devidas inicializac¸o˜es
o topo da pilha sera´ a posic¸a˜o 0
o tamanho ma´ximo sera´ passado como paraˆmetro para o construtor
o vetor itens e´ inicializado dinamicamente
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 20 / 50
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 3: Estrutura de dados pilha: verificar se esta´ vazia
template <class T> bool Pilha<T>::vazia(){
return this->topo==0;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 21 / 50
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Implementac¸a˜o da estrutura de dados Pilha (arranjo)
Func¸a˜o para inserir item no topo da pilha
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 22 / 50
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 4: Estrutura de dados pilha: empilhar item no topo da pilha
empilha(T item){
se (topo == tamanho maximo)
“pilha cheia!”
senao{itens[topo] = item;
topo++;
}
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 23 / 50
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Implementac¸a˜o da estrutura de dados Pilha (arranjo)
Func¸a˜o para retirar item do topo da pilha
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 24 / 50
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 5: Estrutura de dados pilha: desempilhar item no topo da pilha
desempilha(){
se(nao vazia){
topo−−;
item = itens[topo];
retorne item;
}
senao{
“pilha vazia!”;
}
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 25 / 50
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 6: Estrutura de dados Pilha: verificar o tamanho atual da pilha
tamanho(){
retorne topo;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 26 / 50
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Exemplo de aplicac¸a˜o: pareˆntesis e colchetes
E´ preciso decidir se uma sequeˆncia de pareˆnteses e colchetes esta´
bem-formada
Ou seja, pareˆntesis e colchetes sa˜o fechados na ordem inversa em que
sa˜o abertos
sequeˆncia bem-formada: ( ( [ [ ( ) ] ] ) )
sequeˆncia mal-formada: ( ( [ ) ] )
Como implementar esse algoritmo?
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 27 / 50
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Exemplo de aplicac¸a˜o: pareˆntesis e colchetes
Observac¸o˜es:
1 se o nu´mero de itens for ı´mpar → na˜o esta´ bem-formado
2 os primeiros itens da sequeˆncia sera˜o avaliados por ultimo
3 os itens mais internos e seus correspondentes sera˜o avaliados primeiro
Que estrutura utilizar?
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 28 / 50
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Exemplo de aplicac¸a˜o: pareˆntesis e colchetes
Soluc¸a˜o:
Sempre que encontrar um pareˆntese ou colchete abrindo, empilhe-o
Quando encontrar pareˆntese ou colchete fechando, desempilhe o
s´ımbolo do topo da pilha
Compare se eles sa˜o equivalentes
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 29 / 50
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 7: Expressa˜o bem formada com pilha
bool bem formada(char seq[], int tam){
Pilha<char>pilha(tam);
if(tam%2!=0)
return false;
else{
for(int i = 0; i<tam; i++){
if(seq[i]==’(’ || seq[i]==’[’)
pilha.empilha(seq[i]);
else{
char simbolo = pilha.desempilha();
if(seq[i]==’)’ && simbolo == ’[’)
return false;
if(seq[i]==’]’ && simbolo == ’(’)
return false;
}
}
return true;
}
}Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 30 / 50
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Considerac¸o˜es sobre implementac¸a˜o de pilhas com arranjos
Economia de memo´ria – apontadores sa˜o impl´ıcitos e na˜o precisam
ser armazenados na memo´ria
Problema: tamanho da pilha e´ fixo
aplicac¸o˜es que na˜o possuem previsa˜o sobre crescimento da pilha
requerem realocac¸a˜o de memo´ria
operac¸a˜o de alto custo de tempo e memo´ria
criar nova a´rea com mais posic¸o˜es e copiar todos os itens para esta a´rea
O que fazer quando o crescimento da pilha e´ dinaˆmico e na˜o previsto?
e agora, Jose´?
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 31 / 50
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Considerac¸o˜es sobre implementac¸a˜o de pilhas com arranjos
Economia de memo´ria – apontadores sa˜o impl´ıcitos e na˜o precisam
ser armazenados na memo´ria
Problema: tamanho da pilha e´ fixo
aplicac¸o˜es que na˜o possuem previsa˜o sobre crescimento da pilha
requerem realocac¸a˜o de memo´ria
operac¸a˜o de alto custo de tempo e memo´ria
criar nova a´rea com mais posic¸o˜es e copiar todos os itens para esta a´rea
O que fazer quando o crescimento da pilha e´ dinaˆmico e na˜o previsto?
e agora, Jose´?
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 31 / 50
Implementac¸a˜o com Estruturas Auto-Referenciadas
Suma´rio
1 Introduc¸a˜o
2 Implementac¸a˜o com Arranjos
3 Implementac¸a˜o com Estruturas Auto-Referenciadas
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 32 / 50
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Pilha e´ organizada em ce´lulas
Cada ce´lula guarda um item de dado e uma refereˆncia para a pro´xima
ce´lula
Permite utilizar posic¸o˜es na˜o cont´ıguas de memo´ria
Na˜o e´ necessa´rio definir a priori o tamanho ma´ximo da pilha
A pilha guarda uma refereˆncia para a ce´lula no topo
As demais ce´lulas apontam para a pro´xima ce´lula
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 33 / 50
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 34 / 50
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Para desempilhar um item (topo)
desliga-se a ce´lula xn
faz a ce´lula xn−1 ser o topo da pilha
Para inserir um item
cria-se uma nova ce´lula para o item
faz a pilha apontar para a nova ce´lula como sendo o topo
faz essa nova ce´lula apontar para o topo anterior como pro´ximo item
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 35 / 50
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Cada ce´lula da pilha conte´m um item da pilha e uma refereˆncia para
a pro´xima ce´lula
Algoritmo 8: Estrutura de dados Pilha: ce´lula
template <class T> class Celula{
public:
T item;
Celula* prox;
Celula(){
prox = NULL;
}
};
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 36 / 50
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o de uma ce´lula
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 37 / 50
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Cada ce´lula da pilha conte´m um item da pilha e uma refereˆncia para
a pro´xima ce´lula
Algoritmo 9: Estrutura de dados Pilha: ce´lula
template <class T> class Celula{
public:
T item;
Celula* prox;
Celula(){
prox = NULL;
}
};
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 38 / 50
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
A classe Celula possui um campo item para guardar o item a ser
armazenado na pilha
Possui um ponteiro prox que aponta para a pro´xima ce´lula da pilha
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 39 / 50
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Algoritmo 10: Estrutura de dados Pilha
template <class T> class Pilha{
private:
Celula<T> *topo;
int tam;
public:
Pilha();
bool vazia();
void imprime();
void empilha(T item);
T desempilha();
int tamanho();
};
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 40 / 50
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
A pilha guarda apenas um ponteiro para a ce´lula no topo
A varia´vel tam e´ utilizada para se guardar o tamanho atual da pilha,
sem precisar percorreˆ-la
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 41 / 50
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o do construtor
Rodolfo Carneiro Cavalcante(UFAL) Aula 03Pilhas 19 de Abril de 2015 42 / 50
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Algoritmo 11: Estrutura de dados Pilha: Construtor
template <class T> Pilha<T>::Pilha(){
this->topo = NULL;
this->tam = 0;
}
template <class T> bool Pilha<T>::vazia(){
return this->topo==NULL;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 43 / 50
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o da func¸a˜o de empilhar
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 44 / 50
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Algoritmo 12: Estrutura de dados Pilha: Empilhar
empilha(item){
Celula *aux = topo;
topo = new Celula();
topo->item = item;
topo->prox = aux;
tam++;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 45 / 50
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o da func¸a˜o de desempilhar
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 46 / 50
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Algoritmo 13: Estrutura de dados Pilha: Desempilhar
desempilha(){
se(nao vazia){
item = topo->item;
topo = topo->prox;
tam−−;
retorne item;
}
else{
”pilha vazia!”;
}
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 47 / 50
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Considerac¸o˜es sobre estruturas auto-referenciadas
Implementac¸a˜o u´til em aplicac¸o˜es em que na˜o existe previsa˜o sobre o
crescimento da pilha
Desvantagem – utilizac¸a˜o de memo´ria extra para armazenar as
refereˆncias (os ponteiros prox)
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 48 / 50
Implementac¸a˜o com Estruturas Auto-Referenciadas
Exerc´ıcio
Reconhecedor para linguagem L = {ambncndm|m ≥ 1, n ≥ 0}
L = {ad , abcd , aabcdd , aaaadddd , abbbcccd , ...}
Func¸a˜o deve receber uma cadeia e retornar true ou false se a cadeia
pertence a linguagem
Dado que essa linguagem e´ infinita, utilize uma pilha encadeada para
resolver o problema
voceˆ na˜o sabe de antema˜o o tamanho da pilha
Entrega na pro´xima sexta-feira (24/04) a`s 23:55
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 49 / 50
Implementac¸a˜o com Estruturas Auto-Referenciadas
Exerc´ıcio
Formato da entrega
Ambiente Virtual de Aprendizagem
Envie os arquivos fontes (mesmo que apenas um) compactados com
rar ou zip, com o nome LP3 2014.1 nome aluno1 e nome aluno2.zip
Exemplo: alunos Wilcklison Jonesclayson e Joilson dos Teclados
Arquivo zip: LP3 2014.1 Wilcklison e Joilson.zip
O seu programa deve ser executado em uma ma´quina com Ubuntu
com compilador gcc(g++)
Se o arquivo na˜o esta´ compilando/executando, envie assim mesmo e
informe no corpo do email o problema e onde suspeita estar
localizado o problema no co´digo.
Rodolfo Carneiro Cavalcante (UFAL) Aula 03Pilhas 19 de Abril de 2015 50 / 50
	Introdução
	Implementação com Arranjos
	Implementação com Estruturas Auto-Referenciadas