Programação II
Prof. Mateus Raeder
Universidade do Vale do Rio dos Sinos
- São Leopoldo -
Listas especiais
• O armazenamento sequencial (estático) é útil
quando as estruturas sofrem poucas remoções ou
inserções, ou quando estas não acarretam grandes
movimentações de nós
– Não é exatamente o caso de listas que permitem inserção
em qualquer posição
– O armazenamento sequencial é mais utilizado para
implementas tipos especiais de listas:
• Filas (Queue em inglês)
• Pilhas (Stack em inglês)
• Deques (Deque em inglês)
Programação II – Prof. Mateus Raeder
Pilha
(Stack)
Programação II – Prof. Mateus Raeder
Pilhas
• Os elementos são inseridos e removidos sempre na
extremidade final, chamada de topo da pilha
• Contém um ponteiro (variável) que marca o topo
da pilha
• Implementa a norma LIFO (Last-In, First-Out)
– Último a entrar, primeiro a sair
• Pilha vazia: topo = -1
Programação II – Prof. Mateus Raeder
Pilhas
• Suponhamos uma pilha de números
inteiros P que, em certo momento,
possui os seguintes 7 elementos:
1 6 9 -3 0 3 5
• Declarando um array de inteiros de
nome P com MAX=10 elementos
(P[0..MAX-1]), teremos a seguinte
pilha:
5
3
0
-3
9
6
1
Programação II – Prof. Mateus Raeder
Operações sobre pilhas
- inserir número 2
- inserir número 8
- inserir número 4
- remover elemento
14
8
2
top
top
top
- inserir número 1
- remover elemento
- remover elemento
Programação II – Prof. Mateus Raeder
Exercício: Pilhas
• Dada a pilha ao lado, realize as
operações abaixo
(cumulativamente) e desenhe a
pilha resultante em cada passo:
–
–
–
–
–
–
Inserir 7
Retirar o primeiro elemento
Inserir -4
Inserir 6
Retirar o primeiro elemento
Retirar o primeiro elemento
3
Programação II – Prof. Mateus Raeder
Operações sobre pilhas
• public boolean isEmpty( )
– verifica se a pilha está vazia
• public boolean isFull( )
– verifica se a pilha está cheia
• public boolean push( int element )
– insere o nó no topo da pilha
Programação II – Prof. Mateus Raeder
Operações sobre pilhas
• public int pop( )
– retorna e remove o nó do topo da pilha
• public int getTop ( )
– retorna o nó do topo da pilha, sem removê-lo
• public void print( )
– exibe todos os nós da pilha
Programação II – Prof. Mateus Raeder
Estouros em pilhas
• Estouro negativo:
– Underflow (pilha vazia sofre operação de remoção)
• Estouro positivo:
– Overflow (pilha completamente preenchida sofre
operação de inserção)
Programação II – Prof. Mateus Raeder
Pilhas
• Supondo a existência da classe Stack, desenhe a
pilha criada através do código abaixo (a saída do
programa):
public static void main(String args[]){
Stack p = new Stack(5);
p.push(4);
p.push(7);
p.push(14);
p.pop();
p.push(3);
p.pop();
p.pop();
p.print();
}
Programação II – Prof. Mateus Raeder
Pilha
public class Stack {
private int s[];
private int top = -1;
public Stack (int size){
s = new int[size];
}
... //demais métodos
}
Programação II – Prof. Mateus Raeder
Pilha
• Verificar se está vazia ou se está cheia
– Vazia:
/* Retorna:
- true se a lista está vazia
- false caso contrário */
public boolean isEmpty(){
if(top == -1)
return true;
return false;
}
Programação II – Prof. Mateus Raeder
Pilha
• Verificar se está vazia ou se está cheia
– Cheia:
/* Retorna:
- true se a lista está vazia
- false caso contrário */
public boolean isFull(){
if(top == s.length - 1)
return true;
return false;
}
Programação II – Prof. Mateus Raeder
Pilha
• Inserir e remover elementos
– Inserir (push)
public void push(int element) throws OverflowException{
if(isFull())
throw new OverflowException();
else{
top++;
s[top] = element;
}
}
Programação II – Prof. Mateus Raeder
Pilha
• Inserir e remover elementos
– Remover (pop)
public int pop() throws UnderflowException{
if(isEmpty())
throw new UnderflowException();
else{
int element = s[top];
top--;
return element;
}
}
Programação II – Prof. Mateus Raeder
Pilha
• Retornar o elemento do topo, sem remover
public int getTop() throws UnderflowException{
if(isEmpty())
throw new UnderflowException();
else
return s[top];
}
Programação II – Prof. Mateus Raeder
Pilha
• Imprimir os elementos da pilha
public void print(){
for(int i=top; i>=0; i--)
System.out.println(s[i]);
}
Programação II – Prof. Mateus Raeder
Pilha
public static void main(String args[]) {
Stack s = new Stack(6);
try {
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.push(5);
s.push(6);
} catch (OverflowException e) {
System.out.println(e.toString());
}
try{
int removed = s.pop();
removed = s.pop();
s.print();
} catch (UnderflowException e) {
System.out.println(e.toString());
}
}
Programação II – Prof. Mateus Raeder