quinta-feira, 9 de outubro de 2014

[Python] - Utilizando o módulo deque para implementar filas

Olá pessoal, nesse post iremos conhecer o módulo deque e com ele implementaremos a estrutura de dados fila.

Só para relembrar, fila é uma estrutura de dados que respeita o princípio FIFO (first in, first out), ou seja, o primeiro elemento a entrar é o primeiro a sair. Para não esquecer é só associar a uma fila de banco.

O código abaixo foi testado nas versões do Python 2.7 e 3.4.

Caso você esteja executando o código com algum interpretador Python versão 3.x, então não precisará da linha 1.

Linha 4: importação do módulo deque

Linha 8: é criada uma fila passando o tamanho máximo de 10 elementos. Esse tamanho é opcional, caso não especifique, então a fila não terá limites.

Linhas 11 à 14: utiliza-se o método "append" para inserir elementos na fila.

Linha 18: imprime a fila.

Linha 21: retira um elemento utilizando o método "popleft". Por que eu não utilizei o método "pop" ? Se utilizasse o método "pop", então seria retirado o elemento do final que seria o 40, mas como estamos implementando uma fila, então temos que retirar o elemento do início da fila, daí utilizar o método "popleft" que retorna o elemento removido.

Remover elemento da extremidade de uma fila tem complexidade O(1) enquanto remover de uma lista tem complexidade O(N).

Linha 22: impressão do elemento removido que foi o elemento 10.

Linha 26: imprime novamente a fila.

Linha 29: conta quantas vezes o número 20 aparece na fila.

Saída:


Quaisquer dúvidas deixem nos comentários, até a próxima.


Nenhum comentário: