Реализация дека в Python¶

Создадим новый класс для реализации АТД “дек”, как мы неоднократно делали в предыдущих разделах. Список Python вновь предоставит очень хороший набор методов, с помощью которых мы построим детализацию этой структуры данных. Наша реализация (листинг 1) будет предполагать, что хвост дека находится в нулевой позиции списка.

Листинг 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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

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

    def addFront(self, item):
        self.items.append(item)

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

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

    def removeRear(self):
        return self.items.pop(0)

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

В removeFront мы используем метод pop для удаления последнего элемента из списка. Однако, в removeRear метод pop(0) должен удалять первый из них. Также нам нужно использовать метод insert (строка 12) в addRear, поскольку append предполагает добавление нового элемента в конец списка.

CodeLens 1 демонстрирует класс Deque в последовательности действий, которую мы представили в таблице 1.

Можно найти много сходства в коде на Python, описывающем стеки и очереди. Вероятно, вы также заметили, что в этой реализации добавление и удаление элементов из головы имеет O(1), в то время как те же операции для хвоста - O(n). Это и следовало ожидать, учитывая какие распространённые методы использовались для этой цели. Опять же, главное, в чём мы должны быть уверены, так это в том, что в нашей реализации назначено хвостом, а что головой дека.