|
Очередь collections.deque на PythonКурс по структурам данных: https://stepik.org/a/134212 Мы продолжаем знакомство с очередями. На этом занятии рассмотрим коллекцию deque модуля collections стандартной библиотеки языка Python. Класс deque, по сути, реализует двусвязный список со всеми наборами операций: добавления/удаления граничных элементов, вставки и удаления промежуточных, а также доступ к произвольным элементам. Поэтому коллекцию deque в Python также можно использовать, как полноценный двухсвязный список. Подробное описание всех методов класса deque можно найти на странице официальной документации: https://docs.python.org/3/library/collections.html#collections.deque В частности, там отмечается, что операции добавления/удаления граничных значений выполняется за O(1) операций, а вставки/удаления промежуточных элементов за O(n) операций. Доступ к произвольным элементам также требует O(n) операций. Все это следует учитывать, при использовании методов класса deque в своих приложениях. Давайте теперь познакомимся с основными методами очереди deque. Я выделил следующие:
Чтобы воспользоваться этими методами, вначале нужно импортировать класс deque, например, так: from collections import deque и создать объект двухсторонней очереди. Общий синтаксис следующий: class collections.deque([iterable[, maxlen]]) Здесь iterable – любой итерируемый объект для начальной инициализации очереди deque определенными значениями; maxlen – максимальная длина очереди (максимальное число элементов). Если значение maxlen не указывается или принимает значение None, то очередь не ограничена по числу элементов. В самом простом варианте пустая очередь создается командой: dq = deque() Или же можно сразу указать набор требуемых начальных значений: dq = deque([1, 2, 3, 4, 5]) а также дополнительно указать максимальное число элементов: dq = deque([1, 2, 3, 4, 5], maxlen=5) тогда коллекция dq будет содержать максимум 5 элементов. Примеры использования методов класса dequeВыведем объект dq на экран и убедимся, что он действительно содержит указанные начальные значения: print(dq) А что будет, если в конец очереди (справа) добавить еще один элемент: dq.append(6) Смотрите, теперь очередь содержит значения: deque([2, 3, 4, 5, 6], maxlen=5) То есть, при указании максимального числа элементов и добавлении граничного значения, другое крайнее значение удаляется. В этом легко убедиться, если выполнить добавление справа: dq.appendleft(6) и мы видим результат: deque([6, 1, 2, 3, 4], maxlen=5) Но, давайте уберем параметр maxlen и определим очередь с неограниченным числом элементов: dq = deque([1, 2, 3, 4, 5]) Тогда при добавлении новых значений в начало или в конец очереди прежние данные теряться не будут: dq.append(6) dq.appendleft(0) Если же нам нужно удалить граничный элемент справа или слева в двусвязном списке, то следует воспользоваться методами: right = dq.pop() left = dq.popleft() print(left, right) print(dq) Увидим результат два значения 0 и 6, а также оставшиеся элементы в очереди: deque([1, 2, 3, 4, 5]) Но, имейте в виду, что методы pop() и popleft() генерируют ошибку (исключение) IndexError, если элемент отсутствует, то есть, список пустой. Например: dq = deque() right = dq.pop() left = dq.popleft() приведет к ошибке. Поэтому правильнее будет эти операторы поместить в блок try/except: dq = deque() try: right = dq.pop() left = dq.popleft() print(left, right) print(dq) except IndexError as e: print(e) Следующие два метода extend() и extendleft() добавляют сразу несколько элементов в конец или начало очереди. Работают они подобно методам append() и appendleft(), только в качестве аргументов указывается коллекция с данными: dq = deque([1, 2, 3, 4, 5]) dq.extend((6, 7, 8)) dq.extendleft([-3, -2, -1]) print(dq) Увидим результат: deque([-1, -2, -3, 1, 2, 3, 4, 5, 6, 7, 8]) Обратите внимание, что в качестве итерируемого объекта мы можем указывать и кортеж и список и любой другой, например, множество, словарь и т.п. Следующий метод insert() позволяет вставлять новый элемент в произвольную позицию, например, так: dq.insert(1, 100) Получим результат: deque([1, 100, 2, 3, 4, 5]) То есть, первым аргументом указывается индекс вставляемого элемента, а вторым – его значение. Также можно указывать и отрицательные индексы: dq.insert(-1, 100) получим: deque([1, 2, 3, 4, 100, 5]) И несуществующие: dq.insert(77, 100) dq.insert(-77, -100) результат: deque([-100, 1, 2, 3, 4, 5, 100]) Далее, метод remove() позволяет удалять первый найденный по значению элемент в очереди, например: dq = deque([1, 2, 3, 4, 3, 5]) dq.remove(3) Получим результат: deque([1, 2, 4, 3, 5]) Если значение не находится: dq.remove(33) то генерируется исключение ValueError. Следующий метод clear() удаляет все элементы из очереди, то есть, очищает ее: dq = deque([1, 2, 3, 4, 3, 5]) dq.clear() получим пустую коллекцию: deque([]) И последний метод copy(), который мы рассмотрим на этом занятии, создает копию очереди: dq = deque([1, 2, 3, 4, 3, 5]) dq2 = dq.copy() dq2.append(100) print(dq) print(dq2) Увидим результат: deque([1,
2, 3, 4, 3, 5])
Реализация очередей типа FIFO и LIFOВот основные методы двухсторонней очереди deque языка Python. Используя их, легко можно построить очереди по принципу FIFO и LIFO. Например, реализацию FIFO можно выполнить следующим образом: dq.appendleft(10) # добавление в начало очереди value = dq.pop() # удаление с конца очереди Или, наоборот: dq.append(10) # добавление в конец очереди value = dq.popleft() # удаление с начала очереди Очередь типа LIFO можно сделать с помощью методов: dq.append(11) # добавление в конец value = dq.pop() # удаление с конца Или, наоборот: dq.appendleft(11) # добавление в начало value = dq.popleft() # удаление с начала Альтернативные подходы дают тот же самый эффект, поэтому на практике очереди типов FIFO и LIFO можно реализовывать как вам больше нравится или лучше соответствует структуре программы. Курс по структурам данных: https://stepik.org/a/134212 Видео по теме |
