Prévia do material em texto

UNICARIOCA
TEMA-05
PILHAS
ESTRUTURA DE DADOS PILHA
(STACK)
PILHA  é uma LISTA LINEAR onde
todas as inserções, remoções e
acessos são realizados em um ÚNICO
extremo (TOPO).
Listas com esta característica são
também denominados listas LIFO
(Last-In/First-Out: último que entre 
é o primeiro que sai).
É uma ESTRUTURA DINÂMICA 
pode aumentar ou diminuir durante a
sua existência.
EXEMPLOS
EXEMPLOS
• TOP  ACESSA o elemento do TOPO
• PUSH  INSERE um elemento no TOPO
• POP  REMOVE um elemento do
TOPO.
OPERAÇÕES BÁSICAS SOBRE PILHAS
ESTRUTURA DE DADOS - TEMA-05 1 MANUEL
• TOP(P)  acessa o elemento localizado
no TOPO da Pilha P.
• POP(P)  remove e retorna o elemento
posicionado no TOPO da Pilha P
(diminui o tamanho da pilha).
• PUSH(P,X)  insere o elemento X no
TOPO da Pilha P (aumenta o tamanho
da pilha).
EXEMPLOS DE INSTRUÇÕES EXEMPLO-01
PUSH(P, a)  P:[ a ]
PUSH(P, b)  P:[ b, a ]
PUSH(P, c)  P:[ c, b, a ]
POP(P)  P:[ b, a ]
POP(P)  P:[ a ]
P:[ ]  PILHA VAZIA 
EXEMPLO-01
PUSH(P, d)  P:[ d, a ]
PUSH(P, e)  P:[ e, d, a ]
TOP(P)  P:[ e, d, a ]
POP(P)  P:[ d, a ]
POP(P)  P:[ a ]
P:[ a ] LIMITES DA PILHA
• No mundo real uma pilha é
limitada pelo chão e pelo teto.
• Não é possível inserir elementos
infinitamente.
• Não é possível remover
elementos infinitamente.
• Init  inicializa uma pilha no
estado “vazia”; Init(P).
• IsEmpty  verifica se a pilha
está vazia; IsEmpty(P).
• IsFull  verifica se a pilha está
cheia. IsFull(P).
OPERAÇÕES ESSENCIAIS EM PILHAS EXERCÍCIO-01
Mostre a situação da pilha P, inicialmente vazia,
após a execução de cada uma das operações a
seguir:
Push (P, a); 
Push (P, b); 
Push (P, c); 
Push (P, Top (P));
Push (P, Pop (P)); 
Pop (P); 
Push (P, e); 
Pop (P);
ESTRUTURA DE DADOS - TEMA-05 2 MANUEL
PUSH (P, a); 
PUSH (P, b); 
PUSH (P, c); 
PUSH (P, Top (P));
PUSH (P, Pop (P)); 
POP (P); 
PUSH (P, e); 
POP (P);
EXERCÍCIO-02
Considere a pilha P que contém os elementos
15-6-2-9-17-3. No topo da pilha está o
elemento 15. Nesta pilha foram realizados as
operações Push(1), Push(3), Pop(), Push(8) e
Pop( ). Marque a alternativa que apresenta a
pilha final formada.
A) 1-15-6-2-9-17-3
B) 15-6-2-9-17-3
C) 8-1-15-6-2-9-17-3
D) 3-1-15-6-2-9-17-3
E) 6-2-9-17-3
P
15
6
2
9
17
3
Push(1)
P
1
15
6
2
9
17
3
P
3
1
15
6
2
9
17
3
Push(3) Pop
P
1
15
6
2
9
17
3
Push(8)
P
8
1
15
6
2
9
17
3
Pop
P
1
15
6
2
9
17
3
GABARITO - A
O elemento de dados A encontra-se no topo de uma pilha P e o
elemento B na base quando C e D são, nessa ordem, inseridos.
Em seguida, os dois elementos retirados serão:
EXERCÍCIO-03
a) D e C
b) B e C 
c) A e D 
d) A e C 
e) A e B 
ESTRUTURA DE DADOS - TEMA-05 3 MANUEL
P
A
B
O elemento de dados A encontra-se no topo de uma pilha e o
elemento B na base quando C e D são, nessa ordem, inseridos.
Em seguida, os dois elementos retirados serão:
P
C
A
B
P
D
C
A
B
P
A
B
GABARITO - A
Carpe Diem
ESTRUTURA DE DADOS - TEMA-05 4 MANUEL