Tipos abstratos de dados

Objetivo

Ao final dessa aula você saberá o que são e como utilizar 2 estrutras muito comuns em vários problemas computacionais: pilhas e filas.

Tópicos

• Tipos abstratos de dados

  • Pilhas e filas

• Uso de listas em Python para representar Filas e Pilhas

• Definição de uma classe Fila Circular

Tipo abstrato de dados

Já vimos que, em Python, todos os tipos (como int, float, e str) são classes. Definir uma classe é basicamente criar um novo tipo de dado.

Um tipo abstrato de dados (TAD ou ADT do inglês abstract data type) define uma classe de objetos cujo comportamento lógico é dado por um conjunto de valores e um conjunto de operações (veja mais em Tipo Abstrato de Dado).

Nessa aula veremos como utilizar pilhas e filas.

Pilhas e Filas

Filas e Pilhas são tipos abstratos muito utilizados para modelar o comportamento do processamento de dados. Nas filas, o primeiro elemento que chega é o primeiro elemento a ser processado (conhecido como FIFO do inglês first-in first-out) e nas pilhas, o último elemento que chega é o primeiro a ser processado (conhecido como LIFO do inglês last-in first-out).

Para saber mais sobre usos desses tipos abstratos em computação veja a página do Prof. Paulo Feofilloff sobre Filas e Pilhas.

Embora seja relativamente simples implementar esses dois comportamentos utilizando listas em Python, a implementação de pilhas usando listas é bem mais eficiente por inserir e remover elementos do fim da lista. Por isso veremos como implementar pilhas primeiro.

Pilhas

Considere uma pilha de livros. Um novo livro deve ser colocado no topo, assim como o primeiro livro a ser retirado deve sair do topo também.

Para inserir um elemento no final de uma lista em Python podemos utilizar o método append e para remover o elemento do topo (e atribuí-lo a uma variável) podemos usar o método pop.

Exemplo

O seguinte programa recebe uma sequência de números e a inverte utilizando uma pilha, representada por uma lista em Python, utilizando os métodos append e pop.

def main(): ''' Esse programa mostra como um pilha pode ser utilizada para empilhar uma sequencia e imprimir a sequencia em ordem reversa ''' seq = [1, 2, 3, 4] pilha = [] for elemento in seq: pilha.append(elemento) while len(pilha) > 0: print(pilha) topo = pilha.pop() print("topo: ", topo) main()

(exemplo_pilha_para_inverter_seq)

Run Save Load

Exercício 21.1

Uma pilha pode ser utilizada para verificar se uma expressão aritmética contendo uma sequência de parênteses e colchetes está bem formada, ou seja, se todo parênteses (e colchetes) que abre é fechado.

Utilizando os métodos append e pop de listas, escreva uma função bem_formada que recebe um string s contendo apenas os caracteres de (, ), [ e ] e devolve True caso a expressão estiver bem formada e False caso contrário.

def main(): ''' programa para testar a funcao bem_formada''' exp1 = '(([]))' exp2 = '([)]' print("Teste exp1 = ", exp1, " resultado: ", bem_formada( exp1 )) print("Teste exp2 = ", exp2, " resultado: ", bem_formada( exp2 )) # escreva outros testes def bem_formada( s ): ''' (str) -> bool Recebe um string contendo (, ), [, e ] e retorna True caso a expressao esteja bem formada. Retorna False caso contrario.''' print("Vixe, ainda nao fiz essa funcao") main()

(ex21_1_tentativa)

Run Save Load

Notação polonesa ou posfixa

Na notação usual de expressões aritméticas como em (2+3)*4 os operadores são escritos entre os operandos; por isso, a notação é chamada de infixa. Na notação polonesa os operadores são escritos depois dos operandos. Eis alguns exemplos de expressões infixas e correspondentes expressões posfixas:

Exemplos de expressões em notação infixa e sua correspondente em notação posfixa

infixa	posfixa
2+3*4	2 3 4 * +
(2+3)*4	2 3 + 4 *
2*(3+4)/5-6	2 3 4 + * 5 / 6 -

Para reduzir uma expressão em notação polonesa em um valor, é possível utilizar uma pilha da seguinte maneira:

• números (operandos) são empilhados
• operadores desempilham 2 operandos da pilha, calculam e empilham o resultado.

A tabela abaixo mostra, passo-a-passo, como cada elemento da expressão é processado por esse algoritmo.

Exemplo de execução

exp polonesa	pilha	comentário
2 3 4 + 5 / * 6 -	[]	pilha vazia
3 4 + 5 / * 6 -	[2]	2 foi empilhado
4 + 5 / * 6 -	[2, 3]	3 foi empilhado
+ 5 / * 6 -	[2, 3, 4]	4 foi empilhado
5 / * 6 -	[2, 7]	3 e 4 foram desempilhados e 7 (3+4) foi empilhado
/ * 6 -	[2, 7, 5]	5 foi empilhado
* 6 -	[2, 1.4]	7 e 5 foram desempilhados e 1.4 (7/5)foi empilhado
6 -	[2.8]	2 e 1.4 foram desempilhados e 2.8 (2*1.4) foi empilhado
-	[2.8, 6]	6 foi empilhado
	[-3.2]	2.8 e 6 foram desempilhados e -3.2 (2.8-6) foi empilhado

Ao final, caso a expressão polonesa seja válida, a pilha de execução terá apenas um elemento, que corresponde ao resultado da expressão.

Exercício 21.2

Suponha que a sequência polonesa guarda uma expressão aritmética em notação posfixa. Suponha que polonesa não é vazia e contém somente números e os operadores +, -, * e / (todos exigem dois operandos).

Escreva uma função que calcule o valor da expressão polonesa. Cuidado com divisões por zero!

ADD = '+' SUB = '-' MUL = '*' DIV = '/' def main(): ''' Programa para teste da funcao polonesa ''' exp = [2, 3, ADD] print(exp, polonesa(exp)) def polonesa( exp ): ''' (list) -> float calcula o valor de uma expressao polonesa ''' return 0 main()

(ex21_2_tentativa)

Run Save Load

Filas

Para a implementação de filas, a documentação do Python recomenda o uso da classe deque do módulo collections. O tipo deque oferece o método popleft, para remover o primeiro elemento da deque de forma eficiente.

Mas quando o tamanho máximo de uma fila é conhecido, podemos utilizar uma lista em Python de tamanho fixo e índices para controlar a fila, evitando assim o trabalho de remover e inserir elementos. Uma possível implementação seria:

def main(): # testes da classe Fila f = Fila(10) f.insere("alho") f.insere("cebola") f.insere("pimenta") print(f.remove()) f.insere("sal") print(f.remove()) print(f.remove()) print(f.remove()) class Fila: def __init__(self, max): self.elemento = [0]*max # cria uma fila com max elementos, todos zero self.ini = 0 self.fim = 0 def insere(self, ele): self.elemento[self.fim] = ele self.fim += 1 def remove(self): obj = self.elemento[self.ini] self.ini += 1 return obj main()

(aula21_classe_Fila_basica)

Run Save Load

Exercício 21.3

A classe Fila como definida anteriormente tem vários problemas. Por exemplo, ao utilizá-la várias vezes, o índice fim chega ao tamanho máximo da fila, mas pode haver espaço sobrando. Uma forma de se evitar esse problema é usando uma fila circular. Nesse caso, quando o índice fim ou ini chegam ao tamanho máximo, eles voltam a zero.

Reescreva a classe Fila para que se torne circular.

def main(): # escreva testes para a classe FilaCircular print("Vixe! ainda nao escrevi os testes") class FilaCircular: def __init__(self, max): self.elemento = [0]*max # cria uma fila com max elementos, todos zero self.ini = 0 self.fim = 0 def insere(self, ele): self.elemento[self.fim] = ele self.fim += 1 if self.fim == len(self.elemento): self.fim = 0 def remove(self): # reescreva o metodo remove para fila circular main()

(aula21_ex21.1_tentativa)

Run Save Load

Exercício 21.4

Inclua os seguintes métodos na classe FilaCircular:

• vazia(): que retorna True se a fila está vazia e False caso contrário. Uma fila está vazia quando o índice ini == fim.
• cheia(): que retorna True se a fila está cheia e False caso contrário. Uma fila está cheia quando o índice fim+1 é igual ao tamanho da fila e ini igual a zero, ou quando fim+1 == ini. Ou seja, a fila está cheia quando (fim+1)%N == ini.

Modifique os métodos insere e remove para inserir apenas quando a fila não está cheia (e imprime uma mensagem de erro apropriada) e remover apenas quando a pilha não estiver vazia (retorna None caso esteja).

Exercício 21.5

Exercício 2.5 das notas de aula do Prof. Feofilloff sobre filas.

Imagine um tabuleiro quadriculado com m×n casas dispostas em m linhas e n colunas. Algumas casas estão livres e outras estão bloqueadas. As casas livres são marcadas com - e as bloqueadas com #. Há um robô na casa (1,1), que é livre. O robô só pode andar de uma casa livre para outra. Em cada passo, só pode andar para a casa que está ao norte, a leste, ao sul ou a oeste. Ajude o robô a encontrar a saída, que está na posição (m,n).

Sugestão: Faça uma moldura de casas bloqueadas.