Реализация очереди на Python¶

Для реализации АТД очереди подходящим решением вновь станет создание нового класса. Как и раньше, для построения внутреннего представления очереди мы будем использовать мощь и простоту коллекции “список”.

Нам надо определиться, какой конец списках считать головой, а какой - хвостом. Реализация, показанная в листинге 1 предполагает, что последний элемент очереди находится на его нулевой позиции. Это позволяет использовать функцию `insert` для добавления новых элементов в конец очереди. Операция `pop` будет использоваться для удаления переднего элемента (последнего элемента в списке). Напомним, что также это означает постановку в очередь за O(n), а извлечение - за O(1) времени.

Листинг 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 демонстрирует класс Queue в действии для последовательности операций из таблицы 1

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

q = Queue()
q.enqueue('hello')
q.enqueue('dog')
q.enqueue(3)
q.dequeue()