Реализация очереди на 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()