Estrutura de Dados #3 - Implementação de Fila.

Como já foi explicados em posts anteriores, a Fila é uma Estrutura de Dados do tipo FIFO (First-In-Fisrt-Out), onde o primeiro elemento a entrar, será o primeiro elemento a sair. A ideia fundamental da fila é que só podemos inserir um novo elemento no final da fila e só podemos retirar o elemento do início. Neste post será explicado a implementação da Fila com a linguagem Python.

Implementação:

Essa Fila será implementada usando uma lista e utilizando alguns métodos conhecidos para inserção/remoção de elementos que as listas oferecem.

• .append(elemento): adiciona elemento ao final da fila
• .insert(índice, elemento): insere elemento após a posição índice
• .pop(índice): remove remove e retorna o elemento contido na posição índice.

Para inserir elementos, podemos usar o método append(), que insere um elemento ao final de uma lista. Para a retirada de elementos, podemos utilizar o método pop(x), que retira e retorna um elemento da posição x. Em se tratando de uma fila em que estamos inserindo elementos no final, de qual posição devemos retirar os elementos? Acertou quem pensou “da primeira”. Isso mesmo vamos remover o primeiro elemento utilizando pop(0).

>>> fila = [10, 20, 30, 40, 50]

>>> fila.append(60)  # insere um elemento no final da fila

>>> print fila

[10, 20, 30, 40, 50, 60]

>>> print fila.pop(0) # remove o primeiro elemento da lista

10

>>> print fila

[20, 30, 40, 50, 60]

>>> print fila.pop(0) # remove o primeiro elemento da lista

20

>>> print fila

[30, 40, 50, 60]

>>> print fila.pop(0) # remove o primeiro elemento da lista

30

>>> print fila

[40, 50, 60]

Importante: segundo a própria documentação oficial Python, uma lista não é a estrutura mais recomendada para a implementação de uma fila, porque a inserção ou remoção de elementos do início da lista é lenta, se comparada à inserção/remoção do final da lista. Assim, é sugerido que seja usado um deque (collections.deque).

Texto retirado do site: https://pythonhelp.wordpress.com/2012/09/25/filas-e-pilhas-em-python/