Estrutura de Dados: Pilhas

Prévia do material em texto

Estrutura de Dados
Pilhas
Jorge Campos
jorge@unifacs.br
Pilhas
Definição
Uma Pilha é uma seqüência mutável de zero ou mais itens na forma A1, A2,…,An, onde A1 é chamado de topo da pilha.
Uma pilha é uma estrutura linear onde inserções e remoções de elementos sempre ocorrem em uma das extremidades, conhecida como topo da pilha. O topo da pilha é também o único elemento que pode ser inspecionado.
Pilha é uma estrutura conhecida como LIFO (last in, first out)
Tipo Abstrato de Dados = (objetos, operações)
Operações Sobre Objetos Pilha
Criar uma Pilha vazia
Verificar se a Pilha está vazia 
Esvaziar a Pilha
Adicionar um elemento no topo da Pilha (push)
Remover o elemento no topo da Pilha (pop)
Inspecionar o elemento no topo da Pilha (top)
Inspecionar e remover o elemento no topo da Pilha (top e pop)
Imprimir a Pilha
*
Funcionamento de uma Pilha
Inserindo (PUSH)
Removendo (POP)
Inserindo (PUSH)
*
Especificação do TAD Pilha
public class Stack {
// Visão Geral: ver definição
// Construtores
public Stack()
// Efeito: Inicializa this como uma pilha vazia de Objects
// this.isEmpty()=true
// Métodos
public boolean isEmpty()
// Efeito: testa se a pilha está vazia
public void makeEmpty()
// Modifica: this
// Efeito: Esvazia a pilha this_post.isEmpty()=true
public void push (Object elem)
// Modifica: this
// Efeito: adiciona elem no topo da pilha
public void pop () ) throws EmptyStackException
// Modifica: this
// Efeito: se this.isEmpty() lança uma EmptyStackException, caso
 // contrário retira o elemento no topo da lista 
public object top ()
// Efeito: retorna o elemento no topo da lista ou null se this.isEmpty()
*
Especificação do TAD Pilha
public object topAndPop ()
// Modifica: this
// Efeito: retira e retorna o elemento no topo da lista ou null se this.isEmpty()
public void printStack ()
// Efeito: Imprime todos os elementos da pilha usando o método toSting()
*
Implementação do TAD Pilha com Apontadores
public class Stack{
 // Representação
 private StackNode topOfStack;
 private class StackNode {
 private Object element;
 private StackNode next;
 private StackNode (Object e, StackNode n) {
 element=e;
 next=n;
 }
 }
// Construtores
public Stack() {
 topOfStack=null;
}
// Métodos
public boolean isEmpty() {
 return topOfStack==null;
}
public void makeEmpty() {
 topOfStack=null;
}
Stack MinhaPilha = new Stack()
ListNode topOfStack
*
Implementação do TAD Pilha com Apontadores
public void push (Object elem) {
 topOfStack=new StackNode (elem,topOfStack);
}
MinhaPilha
ListNode topOfStack
element O2
next
element O3
next
MinhaPilha.push(O1) 
element O1
next
MinhaPilha.push(O2) 
MinhaPilha.push(O3) 
*
element O1
next
Implementação do TAD Pilha com Apontadores
public void pop () throws EmptyStackException {
 if (isEmpty()) throw new EmptyStackException(); 
 topOfStack= topOfStack.next;
}
MinhaPilha
ListNode topOfStack
MinhaPilha.pop() 
MinhaPilha.pop() 
MinhaPilha.pop() 
MinhaPilha.pop() 
EmptyStackException!
element O3
next
element O2
next
*
Implementação do TAD Pilha com Apontadores
public Object top () {
 if isEmpty() return null;
	return topOfStack.element;
}
public Object topAndPop () {
 if (isEmpty()) return null; 
 Object topElement=topOfStack.element;
 topOfStack= topOfStack.next;
 return topElement;
}
public void printStack () {
 if (this.isEmpty()) return;
 StackNode itr=topOfStack;
 while (itr!=null) {
 System.out.println(itr.element.toString());
 itr=itr.next;
 } 
}
*
Implementação do TAD Pilha com Arranjo
public class Stack{
 // Representação
 private int topOfStack;
 private Object[] elements;
 private int capacity=100;
}
// Construtores
public Stack() {
 elements =new Object[capacity];
 topOfStack=-1;
}
// Métodos
public boolean isEmpty() {
 return topOfStack==-1;
}
public void makeEmpty() {
 topOfStack=-1;
}
*
Implementação do TAD Pilha com Arranjo
public void push (Object elem) {
 topOfStack++;
 increaseCapacityIfNecessaray();
 elements[topOfStack]=elem;
}
private void increaseCapacityIfNecessaray() {
if (topOfStack==capacity) {
 Object[] newElements=new Object[capacity*2];
 for (int i=0;i,< capacity;i++) 
 newElements[i]=elements[i];
 elements=newElements;
 capacity*=2;
 }
}
*
Implementação do TAD Pilha com Arranjo
public void pop () throws EmptyStackException {
 if (isEmpty()) throw new EmptyStackException(); 
 topOfStack--;
}
public Object top () {
 if (isEmpty()) return null;
 return elements[topOfStack];
}
public Object topAndPop () {
 if (isEmpty()) return null;
 topOfStack--; 
 return elements[topOfStack+1];
}
public void printStack () {
 if (this.isEmpty()) return;
 for (inti=0;i<=topOfStack;i++) {
 System.out.println(elements[i].toString());
 } 
}
*
Aplicações de Pilha
	Utilizadas para balanceamento de símbolos { [ ( ) ] }
	Avaliação de expressões aritméticas
	Chamadas de métodos em uma aplicação
	…
*
Algoritmo para Balanceamento de Símbolos
Considere um algoritmo para balanceamento de símbolos de abertura e fechamento de um arquivo fonte em java. 
Os símbolos de abertura são { [ ( e os de fechamento são } ] ), respectivamente. 
	Crie uma Pilha vazia. 
	Para cada caractere lido faça
	Se o caractere é um Símbolo de abertura, empilhe o símbolo na pilha. 
	Se é um símbolo de fechamento e a pilha está vazia, gere um erro, caso contrário desempilhe um elemento da pilha. 
	Se o elemento desempilhado não for o símbolo correspondente ao símbolo de abertura, gere um erro.
	No final do arquivo, se a pilha não estiver vazia, reporte um erro.
*
Avaliações de Expressões Aritméticas
Uma das aplicações clássicas de pilhas é a avaliação de expressões aritméticas
Representações na forma tradicional são ambíguas e por isso obriga o pré-estabelecimento de “regras de prioridade”. 
Estas representações não são convenientes para uma pessoa
A ordem de execução das operações na expressão 
“A + B  C – 4 / 2” 
só torna-se clara se as regras de prioridade são conhecidas:
A mesma expressão na forma “A + (B  C) – (4 / 2)” seria mais facilmente interpretada em uma rápida leitura. 
*
Outras Notações
Seja a expressão na notação tradicional A  B – C / D 
Notação completamente Parentizada: acrescenta-se sempre um parênteses a cada par de operandos e seu operador. 
 ( (A  B) – (C / D) )
Notação Polonesa (ou infix): os operandos aparecem imediatamente depois dos operadores. Esta notação especifica quais operadores, e em que ordem, devem ser calculados. Por isso dispensa o uso de parênteses, sem ambigüidades.
 –  A B / C D
Notação Polonesa Reversa (ou postfix): é como a polonesa, mas os operadores aparecem após os operandos.
A B  C D / – 
*
Resolvendo Operações
Parentizada
((A  B) - (C / D))
( E - (C / D))
( E - F )
 G
Infix
-  A B / C D
- E / C D
- E F
 G
Postfix
A B  C D / - 
 E C D / - 
 E F -
 G
*
Avaliações de Expressões na Forma PRN
Considere a expressão em Notação Polonesa Reversa
6 5 2 3 + 8 * + 3 + *
1. Operandos são lidos e empilhados na pilha.
2. Quando um operador é lido, dois elementos são desempilhados:
3 e 2
4. O operando 8 é lido e empilhado
3. É realizada a operação: 2+3=5 
O resultado é empilhado
3
2
5
6
Topo
5
5
6
Topo
8
5
5
6
Topo
5
6
Topo
*
Avaliações de Expressões na Forma PRN
Considere a expressão em Notação Polonesa Reversa
6 5 2 3 + 8 * + 3 + *
5. Quando o operador * é lido, dois elementos são desempilhados:
8 e 5.
9. O número 3 é lido e empilhado
7. Quando o operador + é lido, dois elementos são desempilhados:
40 e 5.
6. É realizada a operação: 5*8=40
O resultado é empilhado. 
8. É realizada a operação: 5+40
O resultado é empilhado.
40
5
6
Topo
3
45
6
Topo
45
6
Topo
5
6
Topo
6
Topo
*
Avaliações de Expressõesna Forma PRN
Considere a expressão em Notação Polonesa Reversa
6 5 2 3 + 8 * + 3 + *
10. Quando o operador + é lido, dois elementos são desempilhados:
3 e 45
14. Quando se alcança o final da expressão o resultado é desempilhado: 288.
12. Quando o operador * é lido, dois elementos são desempilhados:
48 e 6
11. É realizada a operação: 45+3
 O resultado é empilhado.
13. É realizada a operação. 6*48=288
O resultado é empilhado. 
6
Topo
Topo
288
Topo
48
6
Topo
Topo
*