Pilhas: Estrutura de Dados

Prévia do material em texto

Estrutura de Dados 
UNIP - Ciência da Computação e Sistemas de Informação 
 
 
 
 
AULA 5 
Pilhas 
Estrutura de Dados 
 
A Estrutura de Dados Pilha 
• Pilha é uma estrutura de dados usada em programação, que 
tem uma regra para o acesso aos dados: o acesso dá-se por 
um único extremo, chamado topo. 
 
• Dizemos que uma pilha é uma estrutura LIFO (Last In, First 
Out), ou seja, o último elemento inserido é o primeiro 
elemento a ser consultado ou removido. 
 
• Vamos analisar o comportamento de uma pilha olhando o 
exemplo a seguir. 
 
A Estrutura de Dados Pilha 
• Vamos supor uma pilha de números inteiros 
8 
7 
6 
5 
4 
3 
2 
1 
0 
Topo = -1 
A Estrutura de Dados Pilha 
• Vamos supor uma pilha de números inteiros 
8 
7 
6 
5 
4 
3 
2 
1 
0 
Topo = -1 
8 
7 
6 
5 
4 
3 
2 
1 
5 0 
Insere 5 
Topo = 0 
A Estrutura de Dados Pilha 
• Vamos supor uma pilha de números inteiros 
8 
7 
6 
5 
4 
3 
2 
1 
0 
Topo = -1 
8 
7 
6 
5 
4 
3 
2 
1 
5 0 
Insere 5 
Topo = 0 
8 
7 
6 
5 
4 
3 
2 
23 1 
5 0 
Topo = 1 
Insere 23 
A Estrutura de Dados Pilha 
• Vamos supor uma pilha de números inteiros 
8 
7 
6 
5 
4 
3 
2 
1 
0 
Topo = -1 
8 
7 
6 
5 
4 
3 
2 
1 
5 0 
Insere 5 
Topo = 0 
8 
7 
6 
5 
4 
3 
2 
23 1 
5 0 
Topo = 1 
8 
7 
6 
5 
4 
3 
2 
1 
5 0 
Topo = 0 
Insere 23 Remove 
A Estrutura de Dados Pilha 
• Vamos supor uma pilha de números inteiros 
8 
7 
6 
5 
4 
3 
2 
1 
0 
Topo = -1 
8 
7 
6 
5 
4 
3 
2 
1 
5 0 
Insere 5 
Topo = 0 
8 
7 
6 
5 
4 
3 
2 
23 1 
5 0 
Topo = 1 
8 
7 
6 
5 
4 
3 
2 
1 
5 0 
Topo = 0 
8 
7 
6 
5 
4 
3 
2 
15 1 
5 0 
Topo = 1 
Insere 23 Remove Insere 15 
Operações em uma Pilha 
• As operações de inserção e remoção em uma pilha são 
comumente designadas empilhar e desempilhar 
• Além das operações de empilhar e desempilhar, uma pilha 
suporta também outras operações: 
• empilhar – insere um elemento na pilha; 
• desempilhar – remove um elemento da pilha; 
• pilha vazia – verifica se a pilha está vazia; 
• pilha cheia – verifica se a pilha está cheia; 
• elemento do topo – devolve o elemento que está no topo da pilha, sem 
retirá-lo da pilha; 
 
• Iremos estudar uma pilha implementada através de um vetor. 
Operação pilhaVazia 
• pilhaVazia é um módulo função sem parâmetros da operação pilha vazia. 
Esse módulo retorna verdadeiro se a pilha estiver vazia e retorna falso se 
a pilha não estiver vazia. 
 
lógico pilhaVazia( ) 
início_módulo 
se (topo = - 1) 
então 
retornar verdadeiro; 
senão 
retornar falso; 
fimse; 
fim_módulo; 
Operação pilhaCheia 
• pilhaCheia é um módulo função sem parâmetros da operação pilha cheia 
que retorna verdadeiro se a pilha estiver cheia, ou falso se a pilha estiver 
vazia. 
 
lógico pilhaCheia( ) 
início_módulo 
se (topo >= tamanho - 1) 
então 
retornar verdadeiro; 
senão 
retornar falso; 
fimse; 
fim_módulo; 
 
Operação empilhar 
• empilhar é um módulo procedimento da operação empilhar que recebe 
como parâmetro um objeto elemento a ser empilhado. 
 
empilhar (Objeto elemento) 
início_módulo 
se (não pilhaCheia( )) 
então 
topo  topo + 1; 
vetor[topo]  elemento; 
senão 
escrever ("Pilha Cheia"); 
fimse; 
fim_módulo; 
 
Operação desempilhar 
• desempilhar é um módulo função sem parâmetros da operação 
desempilhar. Se a pilha não estiver vazia, o elemento do topo é 
desempilhado e retornado 
 
objeto desempilhar () 
início_módulo 
Declarar 
objeto desempilhado  nulo; 
se (pilhaVazia()) 
então 
escrever ("Pilha Vazia"); 
senão 
Desempilhado vetor[topo]; 
Topo  topo - 1; 
fimse; 
retornar desempilhado; 
fim_módulo; 
 
 
Operação elementoTopo 
• elementoTopo é um módulo função da operação elemento do topo que 
devolve o elemento que está no topo da pilha. 
 
Objeto elementoTopo( ) 
início_módulo 
 se (pilhaVazia()) 
 então 
 escrever(“PilhaVazia”); 
 senão 
 retornar vetor[topo]; 
fimse; 
fim_módulo; 
 
 
 
método pilhaVazia em Java 
public boolean pilhaVazia( ){ 
if (topo == -1){ 
return true; 
} else { 
return false; 
} 
} 
método pilhaCheia em Java 
public boolean pilhaCheia( ){ 
if (topo >= tamanho-1){ 
return true; 
} else { 
return false; 
} 
} 
 
método empilhar em Java 
public void empilhar (Object elemento){ 
if (! pilhaCheia( )){ 
topo = topo + 1; 
vetor[topo] = elemento; 
} else { 
System.out.printf ("Pilha Cheia"); 
} 
} 
public void empilhar (Object elemento)throws PilhaCheiaException{ 
if (! pilhaCheia( )){ 
topo = topo + 1; 
vetor[topo] = elemento; 
} else { 
throw new PilhaCheiaException(); 
} 
} 
 
 
método desempilhar em Java 
public Object desempilhar (){ 
Object desempilhado = null; 
if (pilhaVazia()){ 
System.out.printf ("Pilha Vazia"); 
} else { 
desempilhado = vetor[topo]; 
topo = topo - 1; 
} 
return desempilhado; 
} 
 
 
método elementoTopo 
public Objeto elementoTopo( ){ 
 return vetor[topo]; 
} 
 
 
Pilha em Java 
• Pilha implementada em Java, como uma classe 
import javax.swing.*; 
public class Pilha{ 
private int tamanho; 
private int topo; 
private Object vetor [ ]; 
 
public Pilha (int tam){ 
topo = -1; 
tamanho = tam; 
vetor = new Object[tam]; 
} 
public Objeto elementoTopo( ){ 
 return vetor[topo]; 
} 
 
Pilha em Java 
public boolean pilhaVazia( ){ 
if (topo == -1){ 
return true; 
} else { 
return false; 
} 
} 
public boolean pilhaCheia( ){ 
if (topo >= tamanho-1){ 
return true; 
} else { 
return false; 
} 
} 
 
Pilha em Java 
public void empilhar (Object elemento){ 
if (! pilhaCheia( )){ 
topo = topo + 1; 
vetor[topo] = elemento; 
} else { 
System.out.printf ("Pilha Cheia"); 
} 
} 
public Object desempilhar (){ 
Object desempilhado = null; 
if (pilhaVazia()){ 
System.out.printf("Pilha Vazia"); 
} else { 
desempilhado = vetor[topo]; 
topo = topo - 1; 
} 
return desempilhado; 
} 
} 
 
Pilha em Java 
Exemplo: imprimir 5 números na ordem inversa em que foram lidos. 
 
 
public class TestaPilha2{ 
 
public static void main (String arg []){ 
 
 PilhaObj objPilha = new PilhaObj (5); 
 Modulos m = new Modulos (); 
 Object num, numInt; 
 
 for (int i = 0 ; i < 5 ; i++){ 
 m.txtInteiro(); 
 num = m.lerNumInt(); 
 objPilha.empilhar(num); 
 } 
 
 while (!objPilha.pilhaVazia()){ 
 numInt = objPilha.desempilhar(); 
 System.out.printf("%nMostra Ordem Inversa: %s",numInt); 
 } 
 System.exit(0); 
}//fim main 
}//fim classe 
 
Exercícios 
• Exercício: desenhe a representação da pilha para a seguinte 
seqüência de operações, considerando que a pilha está 
inicialmente vazia: 
a. ElementoTopo ( ); 
b. Empilhar (3); 
c. Empilhar (7); 
d. Desempilhar( ); 
e. Empilhar (25); 
f. Empilhar (18); 
g. Desempilhar ( ); 
h. ElementoTopo ( ); 
i. Desempilhar ( ); 
j. MostrarPilha ( ); 
k. Desempilhar ( ); 
Exercícios 
• Exercício: Faça uma função que recebe um vetor de String 
representando uma expressãoaritmética (cada elemento do 
vetor é um item da expressão), e avalia se os parênteses da 
expressão estão corretos. 
 
 
• Por exemplo: 
• (( 2 + 3 ) * ( 4 / 2 ))  correta 
• (( 2 + 3 ) * 4 / 2 ))  errada 
• ) 2 + 3 ( * (4 / 2 )  errada