ESTRUTURA DE DADOS
AULA 02 - PILHA
Conceito
Inserção
Remoção
Prof Ulisses Vasconcelos
AULA 02 - PILHA
Conceito
 Inserção
 Remoção

Prof Ulisses Vasconcelos
CONCEITO







Pilhas: São estruturas de dados dinâmicas que
possui duas regiões conhecidas como topo e base
(ou fundo).
Inserção (LIFO): Os itens sempre são inseridos no
topo da pilha
Remoção(LIFO): Os itens sempre são retirados do
topo da pilha
Estrutura dinâmica: Comprimento variável
O único elemento que se tem acesso é o elemento
que está no topo
A base é o primeiro elemento que foi inserido na
pilha
O topo é o ultimo elemento que foi inserido na
pilha
Prof Ulisses Vasconcelos
CONCEITO

Funcionamento de pilha utilizando
vetores:
• Vetores possuem um espaço
limitado para armazenamento
de dados.
• Necessitamos definir um espaço
grande o suficiente para a nossa
pilha.
• Necessitamos de um indicador
(sentinela) de qual elemento do
vetor é o atual topo da pilha.
Prof Ulisses Vasconcelos
24
89
12
4
55
20 -1
4
3
2
1
0
5
Pilha
cheia
Pilha
vazia
CONCEITO
Funcionamento de pilha utilizando
vetores:
Declaração da pilha

const max = 50;
var
pilha : record
topo : Byte;
dados = ARRAY [1..max] OF Integer
end;
Prof Ulisses Vasconcelos
CONCEITO

Operações







Colocar (PUSH) itens na pilha
Retirar (POP) itens da pilha
Obtêm o elemento do topo (TOP) da pilha
Verificar se a pilha está cheia
Verificar se a pilha está vazia
Iniciar ou limpar a pilha
Erros possíveis


Estouro de pilha (overflow): Tentar inserir em
pilha cheia
Underflow tentar acessar/excluir um item de
uma pilha vazia
Prof Ulisses Vasconcelos
CONCEITO
Implementação de funcionalidades de
uma pilha:
 Iniciação
Procedure Init(var P:pilha);
Begin
P.topo:=-1;
End;

Prof Ulisses Vasconcelos
CONCEITOS
Verifica se a pilha é vazia
Function IsEmpty(var P:pilha):boolean;
Begin
if P.topo = -1
then IsEmpty:=true
else IsEmpty:=false
End;

Prof Ulisses Vasconcelos
CONCEITOS
Verifica se a pilha está cheia
Function IsFull(var P:pilha):boolean;
Begin
if P.topo=max then
IsFull:=true
else
IsFull:=false
End;

Prof Ulisses Vasconcelos
Inserção
Inserção em pilha de array
Procedure Push(var P:pilha; x:char);
Begin
if not IsFull(P) then  Verificação para evitar overflow
begin
P.topo:=P.topo + 1;
P.dados[P.topo]:= x
end
else writeln(´Pilha Cheia!´)
End;
Prof Ulisses Vasconcelos

Exclusão
Exclusão em pilha de array
Function Pop(var P:pilha):char;
Begin
if not IsEmpty(P) thenVerificação para evitar underflow
begin
Pop:=P.dados[P.topo];
P.topo:=P.topo - 1;
end
else
writeln(´Pilha Vazia!´)
End;
Prof Ulisses Vasconcelos

Pilhas de Ponteiros

Criação da pilha usando ponteiros
type
apontador = ^celula;
celula = record
item:integer;
prox:apontador;
end;
tipopilha=record
fundo:apontador;
topo:apontador;
end;
Prof Ulisses Vasconcelos
Célula
celula = record
item:integer;
prox:apontador;
end;

Prox
Item
item: Variável que recebe valores inteiros
prox: Apontador que aponta para um registro do tipo célula
Utilização
Declaração:
c1.item := 3;
Var
c1.prox :=
c1 : celula;
Prof Ulisses Vasconcelos
Pilha
tipopilha=record
fundo:apontador;
topo:apontador;
end;
Ref. 0
Topo
Fundo

Ref. 1
Ref. 0
Ref. 1
Célula
Célula
fundo: Apontador que aponta para
um registro do tipo célula
topo: Apontador que aponta para
um registro do tipo célula
Prof Ulisses Vasconcelos
Pilhas de ponteiros
Inicia pilha
procedure iniciapilha(var pilha:tipopilha);
var
aux:apontador;
begin
new (aux);
pilha.fundo:=aux;
pilha.topo:=pilha.fundo;
pilha.topo^.prox :=nil;
end;

Prof Ulisses Vasconcelos
Topo
Fundo
{
Ref. 0
Prof Ulisses Vasconcelos
Prox
Item
procedure iniciapilha(var
Ref. 0 Ref. 0
pilha:tipopilha);
var
aux:apontador;
begin
NIL
new (aux);
pilha.fundo:=aux;
Ref. 0
pilha.topo:=pilha.fundo;
pilha.topo^.prox :=nil;
NIL
end;
aux
Ref. 0
Pilhas de ponteiros
Verifica se está vazia
function vazia(pilha:tipopilha):boolean;
begin
vazia:=pilha.fundo = pilha.topo;
end;

Prof Ulisses Vasconcelos
Pilhas de ponteiros
Inserção
procedure inserir(x:integer;var pilha:tipopilha);
var aux:apontador;
begin
new (aux);
pilha.topo^.prox:=aux;
aux^.prox := nil;
aux^.item :=x;
pilha.topo := aux;
end;

Prof Ulisses Vasconcelos
Ref. 0 Ref. 10
Prox
Item
procedure inserir(x:integer;var
pilha:tipopilha);
var aux:apontador;
Topo
Fundo
3
Ref.
NIL1
begin
Prof Ulisses Vasconcelos
Prox
new (aux);
pilha.topo^.prox:=aux;
aux^.prox := nil;
aux^.item :=x;
3
pilha.topo := aux;
end;
Item
Ref. 0
3 NIL
Ref. 1
aux
Ref. 1
Pilhas de ponteiros
Exclusão
procedure retirai(var x:integer; var pilha:tipopilha);

var
aux:apontador;
begin
aux:= pilha.fundo^.prox;
x:=aux^.item;
pilha.fundo^.prox := aux^.prox;
if(pilha.fundo^.prox = nil ) then
pilha.topo := pilha.fundo;
dispose(aux);
end;
Prof Ulisses Vasconcelos
Topo
Fundo
Ref. 0 Ref. 01
Prox
Item
procedure retirai(var
pilha:tipopilha);
var
Ref.
NIL1
aux:apontador;
Ref. 0
begin
aux:= pilha.fundo^.prox;
pilha.fundo^.prox := aux^.prox;
if(pilha.fundo^.prox = nil ) then
3 NIL
pilha.topo := pilha.fundo;
Ref. 1
dispose(aux);
Prox
Item
Valor de aux:
Ref. 1
end;
Prof Ulisses Vasconcelos
Pilhas de ponteiros
Exclusão
procedure retirar(var x:integer; var pilha:tipopilha);
var
aux:apontador;
begin
if ( pilha.fundo^.prox^.prox = nil ) then
retirai(x,pilha)
else
begin
aux:=pilha.fundo^.prox;
while (aux^.prox <>pilha.topo) do
aux :=aux^.prox;
pilha.topo :=aux;
aux:=aux^.prox;
x:=aux^.item;
pilha.topo^.prox:=nil;
dispose(aux);
end;
end;

Prof Ulisses Vasconcelos
Topo
Fundo
Ref. 0 Ref. 12
Ref. 21
Prof Ulisses Vasconcelos
Prox
Item
procedure retirar(var pilha:tipopilha);
var
aux:apontador;
begin
Ref. 1
if ( pilha.fundo^.prox^.prox = nil ) then
retirai(pilha)
Ref. 0
else
begin
aux:=pilha.fundo^.prox;
while (aux^.prox <>pilha.topo) do
aux :=aux^.prox;
pilha.topo :=aux;
Ref.
aux:=aux^.prox;
NIL2
3
pilha.topo^.prox:=nil;
dispose(aux);
Ref. 1
end;
end;
Valro de aux:
5 NIL
Ref. 2