terça-feira, 15 de outubro de 2013

[Python] - Implementação de Fila

Olá pessoal, nesse post veremos um código da implementação da estrutura de dados Fila utilizando listas do Python. Iremos simular uma fila com listas.

A estrutura de dados Fila é como uma fila de banco. Para implementar essa estrutura de dados temos que respeitar a propriedade "First In First Out" (primeiro a entrar, primeiro a sair). Isso quer dizer que sempre inserimos elemento no final da fila e removemos do início.

Veja o código:

# Estrutura de dados Fila
# First In First Out
# Primeiro a entrar, primeiro a sair

# classe da Fila
class Fila:
	def __init__(self): # construtor
		self.fila = []
	def inserir(self, n): # insere na fila
		self.fila.append(n) # insere no final
	def excluir(self): # remove da fila
		if not self.vazia(): # se a fila nao estiver vazia...
			del self.fila[0] # remove do inicio
	def tamanho(self): # retorna o tamanho da fila
		return len(self.fila)
	def vazia(self): # retorna True (vazia) ou False caso contrario
		return self.tamanho() == 0

# testando a fila...
fila = Fila()
print(fila.vazia()) # inicialmente fila vazia (True)
fila.inserir(1) # insere elemento 1 na fila
fila.inserir(2) # insere elemento 2 na fila
fila.inserir(3) # insere elemento 3 na fila
print(fila.vazia()) # fila NAO vazia (False)
print(fila.tamanho()) # tamanho da fila: 3
fila.excluir() # remove o elemento 1
fila.excluir() # remove o elemento 2
fila.excluir() # remove o elemento 3
print(fila.vazia()) # fila vazia (True)

Vídeo-aula explicando o código:



3 comentários:

Diogo disse...

Marcos o vídeo ficou muito legal!
Objetivo e simples de entender!

Mas tenho três dúvidas teria problema em respondê-las? Ou me dá pelo mesmos uma saída?

Em uma fila de dois elementos, um par ordenado (X,Y), é possível inserir/retirar simultaneamente o X e o Y?

Como posso determinar o tamanho da Fila()? Digamos que os valores (X,Y) sempre são inseridos(podendo pertencer a um espaço amostral de até infinitos pares) contudo quero que a minha fila tenha um tamanho de no máximo 100 pares, ou seja, quando chegar o 101 par ordenado(X,Y)vindo do infinito o primeiro seria substituído por este!

Por último: como fazer uma verificação da entrada de valores na fila e mostra-la como completa?
Não sei se isso vai fazer sentido mas seria algo assim: nas posições 1 até a 100 ao inserir o primeiro valor do par ordenado existe um meio de identificar que a fila foi completada até que o segundo par seja inserido?

Pensei em usar uma condição boleana mas isso seria viável!?

Desde já obrigado!

admin disse...

Sim, é possível ter uma fila onde cada elemento é um par ordenado (X,Y). Nesse caso seria uma lista de tuplas.

exemplo:
fila = []
fila.append((1,2))
fila.append((3,4))

Se você der um print em fila, então terá como resultado:

[(1,2), (3,4)]

(1,2) e (3,4) representam os pares ordenados (X,Y)

Se você quer que sua fila tenha um tamanho máximo de 100 pares, então sempre que for adicionar um par, verifica através do len(fila) se o tamanho não ultrapassou o número 100. Exemplo:

if len(fila) < 100: insira o par

Você falou que quer excluir o primeiro quando chegar a 101. É só fazer um else, retira o primeiro elemento através de um fila.pop(0) para retirar o primeiro elemento e faz um fila.insert(0, novo_par) para inserir o novo par no início.

Para verificar se a fila foi completada sempre faça verificação len(fila) == 100, se entrar nessa condição então é porque ela está completa.

Seria viável sim, obrigado pela visita, espero ter sanado suas dúvidas.

Diogo Santos Silva disse...

Sanou as dúvidas sim!
Ficou claro como devo construir o corpo do código.

Vou para a prática. Outra coisa, a lógica é mesma se os valores vem de fontes diferentes!?

Digo, quando os valores X e Y não são inseridos por mim e sim recebidos.
Seria algo assim:

Y_ são valores que recebo(a todo momento).
X_ são valores que eu relaciono aos valores de Y que recebo.

X Y
| |
\ /
Fila[,]