3.12. Implementando uma Fila em Python¶

É novamente apropriado criar uma nova classe para a implementação do tipo abstrato de dados fila, a classe Queue. Como antes, vamos usar o poder e simplicidade das listas de python (list) para construir a representação interna da fila.

Precisamos decidir qual extremidade da lista usar como parte de fim e qual usa como início. A implementação mostrada em Listagem 1 supõe que o fim está na posição 0 da lista. Isso nos permite usemos a função insert() nas listas para adicionar novos elemetos ao final da fila. A operação pop() pode ser usada para remover o elemento do início (o último elemento da lista). Lembre-se de que isso também significa que o consumo de tempo de enqueue() será O(n) e o consumo de tempo de dequeue() será será O(1).

Listing 1

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

CodeLens 1 mostra a classe Queue em ação durante uma sequência de operações da Tabela 1.

Outras manipulações de dessa fila produz os seguintes resultados:

>>> q.size()
3
>>> q.isEmpty()
False
>>> q.enqueue(8.4)
>>> q.dequeue()
4
>>> q.dequeue()
'dog'
>>> q.size()
2