Dominando
Estruturas de Dados 1
Pilhas
Prof. dr. Samuel Martins (Samuka)
@xavecoding @hisamuka
Pilha
Lista linear na qual as operações de inserção e remoção são efetuadas sempre num mesmo extremo denominado
topo da pilha
2
Pilha
Lista linear na qual as operações de inserção e remoção são efetuadas sempre num mesmo extremo denominado
topo da pilha
Política de gerenciamento de elementos:
LIFO: Last In First Out
3
Aplicações
• Avaliação de Expressões
• 5 * ( 6 + 2 ) - 12 / 4
• Casamento de Parênteses
• (a+b)*(c+d)
• Conversão de Expressões
• Infix: a + b
• Prefix: + b a
• Postfix: a b +
• Gerenciamento de Memória
• Backtracking Problems
4
Tipos de Pilhas
Estáticas
• Implementadas com vetores
[n-1]
[n-2]
capacity = n
...
top 30 [2]
20 [1]
10 [0]
5
Tipos de Pilhas
Estáticas Dinâmicas
• Implementadas com vetores • Implementadas com listas encadeadas
30
[n-1]
[n-2]
capacity = n end
... S begin
20
top 30 [2]
20 [1] size = 3
10 [0] 10
6
Pilhas Estáticas
• A pilha S[0 .. n-1] possui parte ocupada S[0 .. top]
• O índice top define o topo da pilha
• A pilha está vazia se top == -1
[n-1]
• A pilha está cheia se top == n – 1
[n-2]
...
• Empilhar (push) um elemento y:
top 30 [2]
• S[++top] = y // idem a (top++; S[top] = y) 20 [1]
• Consultar (peek) um elemento da pilha sem desempilhá-lo: 10 [0]
• x = S[top]
• Desempilhar (pop) um elemento da pilha:
• x = S[top--] // idem a (x = S[top]; top--;)
7
Exemplo
push(10)
push(20)
push(30) [4]
pop [3]
push(40) [2]
push(50) [1]
pop [0]
top = -1
push(100) capacity = n = 5
push(200)
A pilha está vazia!
8
Exemplo
push(10)
push(20)
push(30) [4]
pop [3]
push(40) [2]
push(50) [1]
pop top 10 [0]
push(100) capacity = n = 5
push(200)
9
Exemplo
push(10)
push(20)
push(30) [4]
pop [3]
push(40) [2]
push(50) top 20 [1]
pop 10 [0]
push(100) capacity = n = 5
push(200)
10
Exemplo
push(10)
push(20)
push(30) [4]
pop [3]
push(40) top 30 [2]
push(50) 20 [1]
pop 10 [0]
push(100) capacity = n = 5
push(200)
11
Exemplo
push(10)
push(20)
push(30) [4]
pop [3]
push(40) 30 [2]
push(50) top 20 [1]
pop 10 [0]
push(100) capacity = n = 5
push(200)
12
Exemplo
push(10)
push(20)
push(30) [4]
pop [3]
push(40) top 40 [2]
push(50) 20 [1]
pop 10 [0]
push(100) capacity = n = 5
push(200)
13
Exemplo
push(10)
push(20)
push(30) [4]
pop top 50 [3]
push(40) 40 [2]
push(50) 20 [1]
pop 10 [0]
push(100) capacity = n = 5
push(200)
14
Exemplo
push(10)
push(20)
push(30) [4]
pop [3]
push(40) 50 top 40 [2]
push(50) 20 [1]
pop 10 [0]
push(100) capacity = n = 5
push(200)
15
Exemplo
push(10)
push(20)
push(30) [4]
pop top 100 [3]
push(40) 40 [2]
push(50) 20 [1]
pop 10 [0]
push(100) capacity = n = 5
push(200)
16
Exemplo
push(10)
push(20)
push(30) top 200 [4]
pop 100 [3]
push(40) 40 [2]
push(50) 20 [1]
pop 10 [0]
push(100) capacity = n = 5
push(200)
A pilha está cheia!
17
Codificando: TAD Pilha Estática
• create
• destroy
• is_empty
• is_full
• push
• pop
• peek
18
Pilhas Dinâmicas
• Empilhar (push) um elemento y:
• Adicionar um nó com o elemento y no final da lista
• Consultar (peek) um elemento da pilha sem desempilhá-lo:
30
• Retornar o valor do nó final da lista
• Desempilhar (pop) um elemento da pilha:
end
• Remover o nó final da lista retornando seu valor S begin
20
size = 3
10
19
Codificando: TAD Pilha Dinâmica
• create
• destroy
• is_empty
• push
• pop
• peek
20
Dominando
Estruturas de Dados 1
Pilhas
Prof. dr. Samuel Martins (Samuka)
@xavecoding @hisamuka