Мы уже упоминали такую структуру данных как стэк(туть). Обычно его описание ведут в сравнении с Очередью. Предлагаю разобраться как они могут быть устроены изнутри.
Очередь.
Очередь(англ. Queue) – это структура данных основанная на принципе «первый пришел, первый ушел» (англ. FIFO – First In, First Out). Т.е. по принципу очереди в кабинет ко врачу (если не пропускать тех кому "Мне только спросить").
В Python есть свои встроенные реализации (о них в конце статьи), но мы попробуем написать свою.
И первое с чего следует начать это определить функциональность нашего класса.
· Size – Размер очереди (количество элементов внутри)
· Empty - проверка что очередь пуста
· Push - Помещение объекта в конец очереди (Кто же его пустит в начало то?)
· Pop - Извлечение объекта из начало очереди.
И остается последний вопрос: Как хранить поступающие элементы?
Самое простое решение – используем обычный список: list. Он обладает своими недостатками, но о них после.
Создаем класс queue:
Плюсы:
· Простота и наглядность реализации
Минусы:
· Большое время выполнения метода Pop, т.к. при извлечении элемента из начала мы сдвигаем все оставшиеся элементы в начало.
Сложность операции добавления элемента - Push - O(1), т.к. мы просто добавляем элемент в новую ячейку памяти. А вот операция извлечения почти в 40 раз медленнее, т.к. она состоит из двух этапов:
- извлечение элемента - О(1)
- перестановка всех элементов на один индекс назад - О(n)
Итого: О(1)+О(n) = O(n)
Попробуем ускорить Pop: избавимся от удаления элемента, путем отправки его в «невидимую зону». Введем индекс начального элемента и каждый раз при необходимости извлечь начальный элемент будем сдвигать индекс на +1.
Новая реализация класса:
Плюсы:
· Операции Push и Pop становятся сравнимыми по скорости.
Минусы:
· Требуется предусмотреть операцию очистки неиспользуемых элементов (от 0 до self.index). Например, производить удаление элементов по достижению self.index какого-либо порогового значения.
Само собой, на практике такой реализацией лучше не пользоваться. В начале уже упоминались встроенные в Python реализации. Вот одна из них называемая двухсторонней очередью Deque (двухсторонняя - потому что можно извлекать элементы как из начала ( popleft() ) так и из конца ( popright() ) очереди):
Стэк.
Стэк(англ. Stack) – это структура данных основанная на принципе «последний пришел, первый ушел» (англ. LIFO – Last In, First Out).
На базе list собрать свой Стэк можно по аналогии с Очередью:
И так же используя двухстороннюю очередь Deque, но уже с методом popright() получим более оптимизированную структуру.