Estruturas de Informação I - Aula 6

Estruturas de Informação I - Aula 6
Pilhas
João Araujo Ribeiro
[email protected]
Universidade do Estado do Rio de Janeiro
Departamento de Engenharia de Sistemas e Computação
João Araujo Ribeiro (UERJ)
Estruturas de Informação I
EstrInf
1 / 16
Resumo
1
EI05 - Pilhas
João Araujo Ribeiro (UERJ)
Estruturas de Informação I
EstrInf
2 / 16
EI05 - Pilhas
Pilhas
Uma
Pilha é uma coleção de objetos que são inseridos e retirados de
acordo com o princípio Last in, First out . Um usuário pode isnerir objetos
numa pilha a a qualquer momento, porém só tem acesso ou pode remover
o objeto inserido mais recente no topo da pilha.
João Araujo Ribeiro (UERJ)
Estruturas de Informação I
EstrInf
3 / 16
EI05 - Pilhas
Push e Pop
As operações fundamentais são Push e Pop nos objetos na pilha.
Quando precisamos retirar da pilha, fazemos um pop na pilha, que
recupera o elemento do topo da pilha. Quando acrescentamos um objeto à
pilha, fazemos um push e este objeto se torna o novo topo.
João Araujo Ribeiro (UERJ)
Estruturas de Informação I
EstrInf
4 / 16
EI05 - Pilhas
Exemplo 1 de pilha
Navegadores de Internet armazenam os endereços dos sites recentemente
visitados num pilha. Cada vez que o usuário visita um novo site, este site é
colocado (push ) no topo da pilha. O navegador permite então que o
usuário faça um pop de retorno para sites visitados anteriormente, com o
botão back .
João Araujo Ribeiro (UERJ)
Estruturas de Informação I
EstrInf
5 / 16
EI05 - Pilhas
Exemplo 2 - Undo
Editores de texto normalmente oferecem o recurso de undo, desfazer,que
cancela edições recentes do texto, revertendo o documento para um estado
anterior às modicações. Esta operação de desfazer pode ser realizada
mantendo as mudanças efetuadas no texto numa pilha.
João Araujo Ribeiro (UERJ)
Estruturas de Informação I
EstrInf
6 / 16
EI05 - Pilhas
TAD Pilha
Pilhas são a estrutura de dados mais simples, porém uma das mais
importantes. Elas são usadas em muitas applicações e são ferramentas
usadas por estruturas e algoritmos mais sosticados. Formalmente, uma
Pilha é um tipo abstrato de dados (TAD) que suporta os dois métodos
seguintes.
S.push(e) : Coloca o elemento e no topo da pilha
S.
S.pop( ) : Remove e retorna o elemento do topo da pilha
S; um erro
ocorrerá se a pilha estiver vazia.
João Araujo Ribeiro (UERJ)
Estruturas de Informação I
EstrInf
7 / 16
EI05 - Pilhas
Implementação da Pilha como Array 1/2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# coding=UTF-8
class Empty(Exception):
"""Erro na tentativa de ter acesso a um elemento vazio."""
pass
class ArrayStack :
"""Implementação usando list para armazenar a pilha"""
def __init__(self) :
"""Cria pilha vazia"""
self._data = []
def __len__ (self):
"""Retorna o número de elementos na pilha."""
return len(self._data)
def push(self, item) :
self._data.append(item)
def isEmpty(self) :
"""Retorna true se a pilha está vazia."""
return (self._data == [])
João Araujo Ribeiro (UERJ)
Estruturas de Informação I
EstrInf
8 / 16
EI05 - Pilhas
Implementação da Pilha como Array 2/2
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def top(self):
"""Retorna (mas não remove elemento no topo da pilha"""
if self.isEmpty( ):
raise Empty( Pilha vazia )
return self._data[-1]
def pop(self):
"""Remove e retorna o elemento do topo da pilha"""
if self.isEmpty( ):
raise Empty( Pilha vazia )
return self._data.pop( )
S = ArrayStack()
S.push(10)
S.push(20)
print S.pop()
print S.pop()
print S.pop() #causa exceção
João Araujo Ribeiro (UERJ)
Estruturas de Informação I
EstrInf
9 / 16
EI05 - Pilhas
Análise da Implementação
Push e pop podem ocasionar alocação de memória
Com isso, seus tempos não são O(1) sempre.
Podemos acrescentar código para limitar o tamanho da pilha na
inicialização.
João Araujo Ribeiro (UERJ)
Estruturas de Informação I
EstrInf
10 / 16
EI05 - Pilhas
Invertendo dados usando pilha
Como consequência de sua construção, podemos usar uma pilha para
inverter a ordem de elementos de uma sequência de dados.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# coding=UTF-8
from classepilha import *
import sys
def reverse_file(filename):
"""Substitui arquivo com seu conteúdo invertido linha a linha."""
S = ArrayStack()
original = open(filename)
for line in original:
S.push(line.rstrip(\n))
original.close( )
# Agora vamos substituir com o conteúdo em ordem LIFO
# reabrindo arquivo original
output = open(filename,w)
while not S.isEmpty( ):
output.write(S.pop( ) +\n) # reinsere novas linhas
output.close( )
reverse_file(teste.txt)
João Araujo Ribeiro (UERJ)
Estruturas de Informação I
EstrInf
11 / 16
EI05 - Pilhas
Testando Delimitadores
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# coding=UTF-8
from classepilha import *
def is_matched(expr):
"""Retorna True se todos delimitadores casam; False caso contrário."""
lefty = ({[ # abrindo delimitadores
righty = )}] # fechamentos respectivos
S = ArrayStack()
for c in expr:
if c in lefty:
S.push(c) #push delimitador na pilha
elif c in righty:
if S.isEmpty( ):
return False #erro
if righty.index(c) != lefty.index(S.pop()):
return False #erro
return S.isEmpty()
if is_matched([(5+x)-(y+z)]):
print "ok"
else:
print "Erro"
João Araujo Ribeiro (UERJ)
Estruturas de Informação I
EstrInf
12 / 16
EI05 - Pilhas
Testando tags Html 1/2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# coding=UTF-8
from classepilha import *
def is_matched_html(raw):
"""Retorna True se toda tag HTML tem seu fechamento correto; False caso contrári
S = ArrayStack()
j = raw.find(<) # procura primeiro <
while j != -1:
k = raw.find(>, j+1) # encontra próximo >
if k == -1:
return False # tag inválida
tag = raw[j+1:k] # retira < >
# this is opening tag
if not tag.startswith(/): #isto é uma tag de abertura
S.push(tag)
else: # tag de fechamento
if S.isEmpty():
return False # não casou
if tag[1:] != S.pop():
return False # Erro de delimitador
j = raw.find(<, k+1) # encontra próximo <
return S.isEmpty() # todas as tags casadas?
João Araujo Ribeiro (UERJ)
Estruturas de Informação I
EstrInf
13 / 16
EI05 - Pilhas
Testando tags Html 2/2
23
24
25
26
27
28
f = open("teste.html", "r")
if is_matched_html(f.read()):
print Ok
else:
print Problemas de delimitadores
João Araujo Ribeiro (UERJ)
Estruturas de Informação I
EstrInf
14 / 16
EI05 - Pilhas
Exercício 1
1 - Modique a implementação de ArrayStack para que a capacidade da
pilha seja limitada a
maxlen elementos, onde maxlen é um parâmetro
opcional para o construtor. Se um push é chamado quando a pilha está
cheia, lance uma exceção de Pilha cheia (denida de modo similar a Empty)
2 - Implemente uma função que inverta uma lista de elementos
colocando-os numa pilha em uma ordem e depois os escrevendo de volta à
lista na ordem inversa.
João Araujo Ribeiro (UERJ)
Estruturas de Informação I
EstrInf
15 / 16
EI05 - Pilhas
FIM
João Araujo Ribeiro (UERJ)
Estruturas de Informação I
EstrInf
16 / 16