Biblioteca 1227622

Prévia do material em texto

ESTRUTURAS DE DADOS
Aula 06
Professor: Vinicius Moll.
Florianópolis, 19 de Fevereiro, 2018.
ESTRUTURA DE DADOS
Aula 6 – Pilha
ESTRUTURA DE DADOS
PILHA – Aula6
Atenção aos Temas Principais dessa Aula
ESTRUTURA DE DADOS
PILHA – Aula6
Conteúdo Programático desta aula
Apresentar o conceito de Pilha;
Apresentar aplicações da Pilha;
Apresentar o critério LIFO e suas limitações
 Implementar as funções empilhar, desempilhar, exibir topo
e outras;
ESTRUTURA DE DADOS
PILHA – Aula6
Direto ao Assunto
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
VOCÊ ERROU! NÃO ERA PILHA?
ESTRUTURA DE DADOS
PILHA – Aula6
ERA! E AGORA?
ESTRUTURA DE DADOS
PILHA – Aula6
USA AQUELAS TECLAS.
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
“A pilha é uma das estruturas de dados mais úteis em
computação.
… Uma pilha é um tipo especial de lista linear em que
todas as operações de inserção e remoção são realizadas
numa mesma extremidade, denominada topo”(PEREIRA,
S.L. 2004, p 17).
Conceito de Pilha
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
Considerações sobre a PILHA
ESTRUTURA DE DADOS
PILHA – Aula6
Inserção ou Remoção de um elemento sempre acontece na
mesma extremidade.
Considerações sobre a PILHA
ESTRUTURA DE DADOS
PILHA – Aula6
Inserção na Pilha
ESTRUTURA DE DADOS
PILHA – Aula6
Inserção na Pilha Remoção da Pilha
ESTRUTURA DE DADOS
PILHA – Aula6
Inserção ou Remoção de um elemento sempre acontece na
mesma extremidade.
Não existe movimentação na pilha quando inserimos, ou
removemos um elemento dela.
Considerações sobre a PILHA
ESTRUTURA DE DADOS
PILHA – Aula6
Inserção ou Remoção de um elemento sempre acontece na
mesma extremidade.
Podemos usar matrizes homogêneas ou heterogêneas,
alocação sequencial, e uma variável para controlar o topo.
Não existe movimentação na pilha quando inserimos, ou
removemos um elemento dela.
Considerações sobre a PILHA
ESTRUTURA DE DADOS
PILHA – Aula6
Um dos fatores que limita o crescimento da pilha é a
quantidade de memória alocada quando usamos matrizes.
Considerações sobre a PILHA
ESTRUTURA DE DADOS
PILHA – Aula6
Um dos fatores que limita o crescimento da pilha é a
quantidade de memória alocada quando usamos matrizes.
Quando formos empilhar um elemento, é preciso verificar
se a pilha não está cheia. Isso evita overflow.
Considerações sobre a PILHA
ESTRUTURA DE DADOS
PILHA – Aula6
Um dos fatores que limita o crescimento da pilha é a
quantidade de memória alocada quando usamos matrizes.
Quando formos empilhar um elemento, é preciso verificar
se a pilha não está cheia. Isso evita overflow.
Quando formos desempilhar um elemento, é preciso
verificar se a pilha não está vazia. Isso evita underflow.
Considerações sobre a PILHA
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
1
• Histórico de páginas visitadas num navegador.
2
• Sequencia de desfazer em vários softwares, o famoso atalho Ctrl Z.
3
• Implementação de recursividade (a torre de Hanói que vimos na disciplina de Algoritmos).
4
• A cadeia de chamadas de funções num programa.
5
• Avaliação de expressões aritméticas.
6
• Conversão de Decimal para Binário, etc.
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra?
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra? 1a vez
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra? 2a vez
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra? 3a vez
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra? 4a vez
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra?
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra? 1a vez
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra? 2a vez
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra? 3a vez
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra? 4a vez
ESTRUTURA DE DADOS
PILHA – Aula6
Avaliação de parênteses – um clássico
ESTRUTURA DE DADOS
PILHA – Aula6
#include <iostream>
#include <cstring>
using namespace std;
int expressaoCorreta( char s[]);
int main()
{
char p1[]={"((()))"}; 
char p2[]={"(()))"}; 
if(expressaoCorreta(p1)==1)
cout<<"\n"<<p1<<" Esta Correta\n";
else
cout<<"\n"<<p1<<" Nao esta Correta\n"; 
if(expressaoCorreta(p2)==1)
cout<<"\n"<<p2<<" Esta Correta\n";
else
cout<<"\n"<<p2<<" Nao esta Correta\n"; 
system("pause");
} 
Código
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 (
(
(
)
)
) 
\0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 (
0 0 (
(
)
)
)
\0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 (
0 0 (
(
)
)
)
\0 
s[0]== ‘)’?
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 (
0 0 (
(
)
)
)
\0 
s[0]== ‘)’?N
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 (
1 (
)
)
)
\0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 (
1 1 (
)
)
)
\0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 (
1 1 (
)
)
)
\0 
s[1]== ‘)’?
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 (
1 1 (
)
)
)
\0 
s[1]== ‘)’?N
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 (
2 )
)
)
\0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 (
2 2 )
)
)
\0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 (
2 2 )
)
)
\0 
s[2]== ‘)’?
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 (
2 2 )
)
)
\0 
s[2]== ‘)’?N
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 )
)
\0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
)
\0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
)
\0 
s[3]== ‘)’?
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
)
\0 
s[3]== ‘)’?S
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
)
\0 
t!=0 && pilha[t-1]==‘(‘?Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
)
\0 
t!=0 && pilha[t-1]==‘(‘?S
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
2 )
\0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
\0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
\0 
s[4]== ‘)’?
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
\0 
s[4]== ‘)’?S
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
\0 
t!=0 && pilha[t-1]==‘(‘?
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
\0 
t!=0 && pilha[t-1]==‘(‘?S
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
1 \0
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
5 1 \0
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
5 1 \0
s[5]== ‘)’?
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
5 1 \0
s[5]== ‘)’?S
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
5 1 \0
t!=0 && pilha[t-1]==‘(‘?
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
5 1 \0
t!=0 && pilha[t-1]==‘(‘?S
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
Função
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
5 1 \0
0
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
5 1 \0
6 0
0
1
2
3
4
5
6
retorna 1
Função
ESTRUTURA DE DADOS
PILHA – Aula6
Conversão decimal para binário – outro clássico
ESTRUTURA DE DADOS
PILHA – Aula6
#include <iostream>
#include <cstdlib>
#define TAM 40
using namespace std;
void empilha(int p[], int &t, int v);
void desempilha(int p[], int &t);
int main()
{
int topo=-1, pilha[TAM],num, resto;
cout<<"\nNumero em decimal:";
cin>>num;num=abs(num);
while(num > 0)
{
resto=num %2;
empilha(pilha, topo, resto);
num/=2;
} 
desempilha(pilha,topo);
cout<<"\n\n"; system("pause"); }
Código
ESTRUTURA DE DADOS
PILHA – Aula6
Função t resto num pilha
-1 ? 14 0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função t resto num pilha
-1 ? 14
-1 0 14
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função t resto num pilha
-1 ? 14 0
-1 0 14
0 0 14
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função t resto num pilha
-1 ? 14 0
-1 0 14
0 0 14
0 0 7
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função t resto num pilha
-1 ? 14 0
-1 0 14
0 0 14
0 0 7
0 1 7
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função t resto num pilha
-1 ? 14 0
-1 0 14 1
0 0 14
0 0 7
0 1 7
1 1 7
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função t resto num pilha
-1 ? 14 0
-1 0 14 1
0 0 14
0 0 7
0 1 7
1 1 7
1 1 3
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função t resto num pilha
-1 ? 14 0
-1 0 14 1
0 0 14
0 0 7
0 1 7
1 1 7
1 1 3
1 1 3
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função t resto num pilha
-1 ? 14 0
-1 0 14 1
0 0 14 1
0 0 7
0 1 7
1 1 7
1 1 3
1 1 3
2 1 3
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função t resto num pilha
2 1 1 0
1
1
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função t resto num pilha
2 1 1 0
2 1 1 1
1
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função t resto num pilha
2 1 1 0
2 1 1 1
3 1 1 1
1
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função t resto num pilha
2 1 1 0
2 1 1 1
3 1 1 1
3 1 0 1
0
1
2
3
4
.
FIM - empilha
ESTRUTURA DE DADOS
PILHA – Aula6
Função t pilha
3 0
1
1
1
0
1
2
3
4
5
ESTRUTURA DE DADOS
PILHA – Aula6
Função t pilha
3 0
1
1
1
0
1
2
3
4
5
Saída
ESTRUTURA DE DADOS
PILHA – Aula6
Função t pilha
3 0
2 1
1
1
0
1
2
3
4
5
ESTRUTURA DE DADOS
PILHA – Aula6
Função t pilha
3 0
2 1
2 1
1
0
1
2
3
4
5
Saída
ESTRUTURA DE DADOS
PILHA – Aula6
Função t pilha
3 0
2 1
2 1
1 1
0
1
2
3
4
5
ESTRUTURA DE DADOS
PILHA – Aula6
Função t pilha
3 0
2 1
2 1
1 1
1
0
1
2
3
4
5
Saída
ESTRUTURA DE DADOS
PILHA – Aula6
Função t pilha
3 0
2 1
2 1
1 1
1
0
0
1
2
3
4
5
ESTRUTURA DE DADOS
PILHA – Aula6
Função t pilha
3 0
2 1
2 1
1 1
1
0
0
0
1
2
3
4
5
Saída
ESTRUTURA DE DADOS
PILHA – Aula6
Função t pilha
3 0
2 1
2 1
1 1
1
0
0
-1
0
1
2
3
4
5
Saída
FIM - desempilha
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
1) Inicializa () ou Init()
2) Empilhar() ou Push()
3) Desempilhar() ou Pop()
4) acessoTopo() ou Top()
5) verificaPilhaCheia() ou isFull()
6) verificaPilhaVazia() ou isEmpty()
ESTRUTURA DE DADOS
PILHA –Aula6
0 PROBLEMA
Uma carreta que transporta cinco carros.
Cada carro, será preso a uma tranca que tem duas
chaves. Uma que foi enviada ao proprietário e a outra
com o motorista.
Cada carro tem um código de saída, identificação(nome
do proprietário, tipo de carro e endereço) e nota fiscal.
A solução será apresentada com struct , funções
matrizes(alocação contígua).
ESTRUTURA DE DADOS
PILHA – Aula6
A struct
ESTRUTURA DE DADOS
PILHA – Aula6
Inicialização
ESTRUTURA DE DADOS
PILHA – Aula6
Protótipos
Inicialização
ESTRUTURA DE DADOS
PILHA – Aula6
#include <iostream>
#include <cstdlib>
#define TAM 5
using namespace std;
struct atende
{
char identificacao[TAM][60];
long long notaFiscal[TAM];
int codigoSaida[TAM], topo;
};
void empilha(atende &pilha);
void desempilha(atende &pilha);
void mostraTopo(atende &pilha);
void lista(atende &pilha);
Código
1
ESTRUTURA DE DADOS
PILHA – Aula6
int main()
{
int op; atende carros;
carros.topo=-1;
do
{ system("cls");
cout<<"\nPILHA( LIFO- Last In - First Out )\n\n";
cout<<"\n1- Inserir carro";
cout<<"\n2- Remover carro";
cout<<"\n3- Mostrar o primeiro carro a sair";
cout<<"\n4- listar - QUESTAO DIDATICA. Remova depois
que testar";
cout<<"\n5- Sai";
cout<<"\nOpcao: ";
cin>>op;
system("cls");
Código
2
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
switch(op)
{
case 1: cin.get(); empilha(carros); break;
case 2: desempilha(carros); break;
case 3: mostraTopo(carros); break;
case 4: lista(carros); break;
case 5: cout<<"\nAplicacao da PILHA\ n"; break;
default: cout<<"\nOPCAO INVALIDA\n";
}
cout<<"\n\n";system("pause");
}while(op!=5);
}
Código
3
ESTRUTURA DE DADOS
PILHA – Aula6
void empilha(atende &pilha)
{
char id[60]; long long nf; int codS;
if(pilha.topo == TAM-1)
cout<<"\nATENCAO. Carreta Cheia\n";
else
{ cout<<"\nProprietatio/ Tipo de carro/ Destino:";
cin.getline(id, 60);
cout<<"\nNota Fiscal: "; cin>>nf;
cout<<"\nCodigo de saida: "; cin>>codS;
pilha.topo++; //atualiza o topo
// pilha recebe valor
strcpy(pilha.identificacao[pilha.topo], id);
pilha.notaFiscal[pilha.topo]=nf;
pilha.codigoSaida[pilha.topo]=codS;
}
}
Código
4
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
void desempilha(atende &pilha)
{
if(pilha.topo == -1)
cout<<"\nATENCAO. Carreta Vazia \n";
else
{
cout<<"\nCodigo do carro entregue: “; //*
cout<< pilha.codigoSaida[pilha.topo];
cout<<"\nNota fiscal do carro entregue: “; //*
cout<< pilha.notaFiscal[pilha.topo];
cout<<"\nIdentificacao do carro entregue: “; //*
cout<< pilha.identificacao[pilha.topo];
pilha.topo--; //atualiza o topo
}
}
//* MELHORAR O ENTENDIMENTO.
Código
5
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
void mostraTopo(atende &pilha)
{
if(pilha.topo == -1)
cout<<"\nATENCAO. Carreta Vazia \n";
else
{
cout<<"\nCodigo do carro: “; //*
cout<<pilha.codigoSaida[pilha.topo];
cout<<"\nNota fiscal do carro: “; //*
cout<<pilha.notaFiscal[pilha.topo];
cout<<"\nIdentificacao do carro: “; //*
cout<<pilha.identificacao[pilha.topo];
}
} //* MELHORAR O ENTENDIMENTO.
Código
6
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
void lista(atende &pilha)
{
if(pilha.topo == -1)
cout<<"\nATENCAO. Carreta Vazia \n";
else
{
cout<<"\nOrdem de Saida\n";
for(int x=pilha.topo; x>=0; x--)
{ cout<<"\n\n"<<x+1<<"o carro";
cout<<"\nCodigo do carro: "<<pilha.codigoSaida[x];
cout<<"\nNota fiscal do carro: "<<pilha.notaFiscal[x];
cout<<"\nIdentificacao do carro: “; //*
cout<<pilha.identificacao[x];
}
}
} //* MELHORAR O ENTENDIMENTO.
Código
7
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
Resumindo