Прежде чем мы поговорим о технологии, которая может чувствовать себя довольно абстрактно, пока вы не познакомитесь с понятиями, давайте заземлимся в чем -то реальном. Давайте поговорим о блинах.
Представьте, что вы делаете блины. Каждый раз, когда вы заканчиваете, делая блин, вы кладете его на тарелку «Готовы к еде» прямо на вершине последнего. Вы не поднимаете все блины, чтобы скользить новой под ними, и вы не разделяете блины пополам, чтобы сжать его посередине. Вы просто добавляете в верхнюю часть кучи, один за другим.
Теперь пришло время поесть. Вы снимаете блин на вершине, затем тот, который внизу, и так далее. Вы не простираетесь в середину и не вытаскиваете один на дне; Вы берете их в обратный заказ, вы поместили их на тарелку.
Это основная идея стека. Создание и употребление блинов следует последним в принципе первого (LIFO). Lifo просто означает, что последний добавленный пункт — первый извлечен.
Почему стеки имеют значение в программировании
Да, в примере блинов вы можете добавить или удалить блин из любого места в стеке блинов, но в стеке программирования доступен только верхний элемент в стеке. Их архитектура LIFO делает стеки идеальными для:
- Обращение данных Как использование «отменить», чтобы обратить вспять действия в приложениях, таких как Photoshop или Google Docs.
- Переселение деревьев или графиков Чтобы завершить поиск по глубине (DFS) при навигации структур папок или иерархических данных (JSON, XML)
- Управление функциональными вызовами Использование стека вызовов, которое отслеживает, где каждая функция должна вернуться после выполнения
Стеки легко реализовать. У Python есть несколько встроенных способов работать с ними.
Внедрение стека в Python
У Python нет встроенного класса стека, такого как список или SET, но вы можете создать пользовательский класс при необходимости. Есть несколько способов создать стек на основе того, для чего вы его используете.
Использование нативных списков (Append / Pop)
Нативные списки делают простые, быстрые маленькие стеки. Нативные списки являются отличным выбором, когда вам нужна быстрое реализация стека для малых и средних наборов данных. Подумайте об отдельных сценариях и небольших приложениях. Нативные списки неэффективны, когда речь идет о безопасности резьбы и больших объемах данных.
Вы можете составить собственный список, используя встроенную структуру данных Python с такими операциями стека, как push (), чтобы добавить элемент и pop (), чтобы удалить элемент из верхней части стека.
Вывод: 2
Использование коллекций
Используйте collections.deque, когда вам понадобится быстрый, эффективный стек памяти. Collections.Deque отлично подходит для больших стеков в приложениях, которые требуют высокой производительности. Примером этого варианта использования является то, что приложение включает в себя одну продюсер/ однопонаправленную потоку.
Коллекции. Deque быстрее и более эффективна память, чем добавляет и проходит через нее, требует немного большего накладного расхода. Он безопасен для одного процесса/ одного потребителя, но не для многопоточных сценариев.
Вывод: 2
Стеки-защитники с Queue.lifoqueue
queue.lifoqueue создает стеки для программ, где безопасность потока имеет решающее значение, и вам нужны встроенные механизмы блокировки, чтобы избежать условий гонки. Это отличный вариант для многопоточных приложений, где несколько потоков push () и pop () одновременно. queue.lifoqueue немного медленнее, чем нативные списки или collection.deque из -за механизмов блокировки.
Вывод: 2
Создание пользовательского класса стека
Если вы хотите создать пользовательское поведение, проверку или ограничения применения, ваш лучший вариант-создать пользовательский класс стека. Пользовательские классы дают вам большее управление операциями стека, такие как добавление пользовательской обработки ошибок или работа с дополнительными методами.
Основные операции стека
Понимание фундаментальных операций стека является ключом к максимизации возможностей вашего стека.
толкать
Добавляет или вставляет элемент в верхнюю часть стека
поп ()
Удаляет и возвращает верхний элемент
Peek/ Top
Возвращает верхний элемент, не удаляя его
is_empty и проверки размера
Быстро проверяйте, пусто, или сколько элементов он содержит.
Приведенный ниже код проходит через то, как будут выглядеть все операции в одном стеке.
Выход:
Оригинальный стек: [‘a’, ‘b’, ‘c’]
После толчка (‘D’): [‘a’, ‘b’, ‘c’, ‘d’]
После Peek (): d
После поп (): d
Текущий стек: [‘a’, ‘b’, ‘c’]
Пусто? ЛОЖЬ
Размер: 3
Реальные варианты использования стеков
Стеки, как блины, везде. Вам просто нужно знать, где иногда смотреть.
Расположение выражения и оценки
Стеки помогают оценить экспрессию Infix/Postfix и разрабатывать вложенные структуры, такие как скобки, теги HTML или синтаксис программирования.
Вы можете найти вариант использования стекла выражения и оценки в компиляторах/ интерпретаторах, приложениях калькулятора, синтаксисе и валидации тегов HTML/ XML.
Отсутствие функциональности
Два стека могут отслеживать действия пользователя, один для Undo, а второй для Redo.
Большинство людей (если не все люди) знакомы с этим. Вы можете найти его в текстовых процессорах, инструментах проектирования и редакторах кода.
Выходы:
Отменить стек: []
Повторный стек: [‘typed: hello’]
Отменить стек: [‘typed: hello’]
Повторный стек: []
Поиск и возврат глубины и возврат
Стеки могут исследовать пути и принимать решения в алгоритмах DFS или обратно.
Вы можете найти поиск и возврат и возврат глубины в играх в рельефе лабиринта и головоломки, логике ИИ и поисковых системах.
Выход:
Начало: стек =[‘A’]посещение = set ()
Выскочил:
Посещение: {‘a’}, Stack: [‘B’, ‘C’]
Выскочил: c
Посещение: {‘a’, ‘c’}, Stack: [‘B’, ‘E’, ‘F’]
Выпал: ф
Посещение: {‘a’, ‘c’, ‘f’}, Stack: [‘B’, ‘E’]
Выпал: e
Посещение: {‘a’, ‘c’, ‘f’, ‘e’}, Stack: [‘B’]
Выпал: б
Посещение: {‘e’, ‘c’, ‘f’, ‘b’, ‘a’}, Stack: [‘D’]
Выпал: D.
Посещение: {‘e’, ‘c’, ‘f’, ‘b’, ‘a’, ‘d’}, стек: []
{‘A’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’}
Соображения производительности и сложности
Часть выбора правильной реализации стека означает понимание ее производительности и характеристик памяти.
Временная сложность
Операции с основным стеком, такие как Push, POP и PEEK, являются O (1) независимо от того, используете ли вы нативный список, Collections.Deque или Queue.Lifoqueue. Все они занимают примерно одинаковое количество времени независимо от размера стека.
Это не означает, что все они предлагают одинаковые возможности производительности. Collections.deque и queue.lifoqueue предлагают более надежную производительность при тяжелой нагрузке или в многопоточных сценариях.
Накладные расходы на память и коллекция мусора
Использование памяти варьируется более заметно между различными реализациями.
Collections.Deque оптимизирован для управления памятью. Он эффективно обрабатывает дополнения и удаления без значительных накладных расходов.
queue.lifoqueue была разработана для безопасности нити и поставляется с дополнительными механизмами блокировки. Это вводит небольшие накладные расходы на память на элемент по сравнению с Collections.Deque или нативным списком. Компромисс стоит для многопоточных приложений.
Нативные списки иногда могут вызывать шипы в памяти, когда стеки растут и часто сокращаются. Это происходит потому, что они чрезмерно выделяют память, чтобы оптимизировать операции Push и POP, иногда удерживая память, в которой они не нужны.
Эффективная обработка больших объемов данных
Collections.deque- самый эффективный вариант памяти и скорость для больших или постоянных стеков. Это избегает оттока памяти, который поставляется с изменением размера списка.
Тестирование и сравнение вашего стека
Со всем, что указано выше, вот несколько советов о том, как тестировать и сравнить стеки, которые вы создаете.
Микробенкинг с Timeit
Timeit измеряет скорость ваших операций стека. Это полезно при сравнении различных реализаций или оптимизации производительности в высокочастотных операциях.
Timeit-отличное решение, когда точная настройка кода для критических ситуаций. Подумайте об игровых петлях, обработке данных и API с высоким трафиком.
Базовый синтаксис
Пример
Вывод будет варьироваться в зависимости от вашей системы.
ЕДИНИЦА
Pytest ловит ошибки. Это хорошая идея, чтобы использовать Pytest, прежде чем нажимать код. Это особенно полезно при работе с индивидуальной логикой стека или обработкой краев. Подумайте о приложениях, которые нуждаются в целостности данных, такие как банковское дело и электронная коммерция.
Базовый синтаксис
Пример
stack.py — пользовательский стек
Test_stack.py — тестовый файл
Запустите Pytest в терминале с командой $ pytest -v
Вывод будет варьироваться в зависимости от вашей системы.
Общие ловушки и советы отладки
Столько, сколько я лично не могу выдержать эту часть, это естественная часть процесса кодирования …
Пустое стек и индексные ошибки
Если вы попытаетесь выйти из пустого стека, Python поднимет индексерр. Всегда проверяйте, есть ли в стеке элементы перед тем, как выскочить.
Изменные аргументы по умолчанию в методах класса
Избегайте использования [] (или другие изменчивые типы) в качестве аргумента по умолчанию в методе или конструкторе. Это может вызвать общее состояние в разных случаях вашего класса.
Заключение
Стеки популярны для использования в приложениях Python, потому что они просты в создании, использовании и предлагают много функциональности. Тем не менее, даже если они менее сложны, чем некоторые из других структур данных Python, важно понять, какой инструмент использовать для каких обстоятельств. Этого руководства более чем достаточно, чтобы начать. Счастливого кодирования!
Trending Stories youtube.com/thenewstack Tech движется быстро, не пропустите эпизод. Подпишитесь на наш канал YouTube, чтобы транслировать все наши подкасты, интервью, демонстрации и многое другое. Группа подпишитесь с эскизом. Джессика Вахтел — писатель по маркетингу разработчиков в InfluxData, где она создает контент, который помогает сделать данные о мире временных рядов более понятными и доступными. Джессика имеет опыт работы в разработке программного обеспечения и технической журналистике. Подробнее от Джессики Вахтел
