Изучение стеков и очередей

"Секреты и уловки"

Изучение стеков и очередей

Дополните свои программы двумя очень полезными инструментами

В нашем последнем посте мы рассмотрели структуры данных или способы, которыми языки программирования хранят данные в памяти. Мы коснулись абстрактных типов данных, теоретических сущностей, которые реализуются через структуры данных. Понятие транспортное средство можно рассматривать как абстрактный тип данных, например, с велосипедом в качестве структуры данных.

В этом посте мы рассмотрим два распространенных абстрактных типа данных: стеки и очереди. Мы начнем с теории этих абстрактных типов, прежде чем реализовывать их в Python. Наконец, мы рассмотрим некоторые вопросы Leetcode, которые поначалу могут показаться сложными, но аккуратно раскрываются в чистых решениях при использовании стека или очереди. Давайте начнем!

Обзор

Стеки и очереди представляют собой наборы значений, подобные массивам, например [1, 2, 3] или [a, b, c]. Но в отличие от массива, где любое значение в коллекции может быть доступно за время O(1), у стеков и очередей есть ограничение: сразу доступно только одно значение: первый элемент (для очередей) или последний элемент (для стеков). Как для стеков, так и для очередей значения всегда добавляются в конец.

Визуальные эффекты могут помочь объяснить. Ниже мы видим процесс добавления и удаления значения из стека. Блок C добавляется в стек, а затем извлекается. Стеки следуют схеме Последним пришел — первым ушел: последний элемент, добавляемый в стек, удаляется первым. Классическая аналогия — это стопка тарелок: тарелка сверху была добавлена ​​последней, а убрана первой.

При этом очередь — это первым пришел — первым обслужен. Ниже мы видим, что блок C снова добавлен в конец очереди. Но на этот раз блок А уходит: он был первым, значит, он и вышел первым. Распространенным примером очереди является очередь на кассе в продуктовом магазине — из всех людей, ожидающих в очереди, человек, который был там раньше всех, будет тем, кого увидят следующим (т. е. первым пришел — первым обслужен).

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

Мы можем видеть это в основных случаях использования стеков и очередей. Стеки используются для отмены и повторения операций в текстовых редакторах, проверки синтаксиса компилятора, выполнения рекурсивных вызовов функций, поиска в глубину и другие случаи, когда нам важно последнее выполненное действие.

Тем временем очереди используются для асинхронного взаимодействия с веб-службой, планирования процессов ЦП, отслеживания N последних добавленных элементов, поиска в ширину и в любое время, когда мы заботимся об обслуживании запросов в в порядке их получения.

Поскольку стеки и очереди не требуют немедленного доступа к каждому элементу, они часто реализуются со структурой данных связанный список, а не с массивами. Это позволяет стеку или очереди неограниченно расти, а также состоять из нескольких типов данных, если нам нужно.

Выполнение

Создание связанного списка

Давайте создадим классы Stack и Queue Python, использующие связанные списки. Мы начнем с определения узла списка, который состоит из значения (self.val) и указателя на следующий узел в списке (self.next). Мы также добавим магический метод __repr__, чтобы упростить визуализацию содержимого узла.

Мы можем создавать связанные списки, объединяя ListNode экземпляров вместе. Вот простой пример создания и визуализации списка со значениями 1, 2 и 3.

Со структурой узла списка у нас есть центральный строительный блок для наших классов стека и очереди.

Создание стеков

Как мы видели, основной операцией для стеков является добавление или удаление самого последнего элемента, также называемое удалением и выталкиванием. Также часто бывает полезно просмотреть верхний элемент в стеке, не удаляя его немедленно, концепция, называемая заглянуть.

Давайте начнем. Ниже мы определяем класс Stack с одним атрибутом _stack, который содержит наш связанный список. Атрибут начинается с подчеркивания, сигнализируя другим разработчикам, что этот атрибут следует считать приватным и не вызывать непосредственно вне класса.

Скорее, мы будем взаимодействовать с _stack только через наши методы push, peek и pop. [1] Чтобы выполнить эти операции за время O(1), мы поместим самый последний элемент в стеке в голову связанного списка в нашем классе Stack, чтобы к нему всегда был легкий доступ .

Наш метод push создает узел для нового значения, указывает атрибут узла next на существующий список, затем переопределяет self._stack как новый узел.

peek и pop требуют некоторого потока управления, чтобы избежать возникновения ошибки, если вы вызываете их в пустом стеке. Оба позволяют нам вызывать атрибуты val и next только в том случае, если self._stack не пусто, что в противном случае вызовет ошибку.

Наши методы возвращают None, если стек пуст, но было бы удобно иметь способ явно указать, есть ли в стеке данные. Поэтому давайте добавим метод is_empty. Мы также добавим методы, которые обходят список: один определяет, содержит ли стек запрошенное значение (contains), а другой печатает содержимое списка (__repr__). Обратите внимание, что методы обхода будут выполняться за время O(n) — чем длиннее список, тем больше времени требуется для сканирования или печати всех элементов. [2]

(Мы могли бы проявить фантазию и добиться времени O(1) для contains, сославшись на dict, который отслеживает количество экземпляров каждого добавляемого нами значения, но пока давайте не будем усложнять.)

is_empty просто проверяет, имеет ли self._stack какие-либо значения. contains и __repr__ используют цикл while для итеративного перемещения по списку, устанавливая node в его атрибут next либо после проверки того, равно ли значение узла искомому значению, либо после добавления значения в список.

Ниже мы поиграем с нашим классом и убедимся, что он работает должным образом.

Создание очередей

Как и в случае со стеками, нашему классу Queue потребуется способ быстрого добавления и удаления элементов. Но в то время как добавление и удаление элементов происходят в начале списка для стеков, эти операции выполняются на противоположных концах списка для очередей.

Итак, должен ли заголовок нашего связанного списка быть самым новым или самым старым элементом в очереди? Если это самое новое, то добавление займет O(1) времени, а удаление — O(n). Если голова является самым старым элементом, то удаление будет быстрым, а добавление — медленным.

На самом деле это ложная дихотомия — мы можем достичь того и другого за время O(1), если будем хранить указатели как на начало, так и на конец нашего списка. Ниже мы начинаем наш класс Queue с атрибутами _head и _tail, а также методами для элементов enqueue (добавление), peek и dequeue (удаление).

Эти операции немного сложнее нашего стека, особенно когда наши указатели _head и _tail указывают на один и тот же узел. Поэтому мы используем дополнительную логику для обработки, когда очередь пуста или содержит только один элемент.

Обратите внимание, что методы is_empty, contains и __repr__ идентичны нашему классу Stack. Единственное отличие состоит в том, что __repr__ будет печатать наши элементы в том порядке, в котором они были получены для очереди, а не в обратном порядке для стека. В любом случае они печатаются в том порядке, в котором будут удалены.

Теперь мы можем поиграть с нашим классом Queue следующим образом:

Случаи использования

Выше мы определили классы Python для стеков и очередей, используя связанные списки для хранения содержимого объектов. В этом разделе мы продемонстрируем мощь этих абстрактных типов данных, решив несколько вопросов Leetcode. По крайней мере, мне эти вопросы показались неразрешимыми головоломками, когда я впервые увидел их. Однако как только я понял, как работают стеки и очереди, головоломки аккуратно развернулись в четкие решения. Надеюсь, я смогу поделиться частичкой этого ах-ха чувства в этом посте.

Стеки

Одной из областей, где стеки невероятно полезны, является проверка кода. Как вы, несомненно, знаете, если вы все еще читаете этот пост в блоге, языки программирования используют изогнутые (( )), квадратные ([ ]) и фигурные ({ }) скобки для функций, индексации, циклов и многого другого. Каждой открытой скобке нужна соответствующая закрытая скобка, и вы не можете поставить закрытую скобку перед открытой скобкой.

Как уследить за всеми открытыми и закрытыми скобками, изогнутыми, квадратными или фигурными, не сойдя с ума? Как мы можем автоматически определить, что скобки внизу слева правильные, а справа нет?

Этот вопрос, LC 20: Действительные скобки, экзистенциально мучителен без стека и удивительно прост с ним. Ниже мы напишем функцию, которая принимает строку скобок и возвращает логическое значение, указывающее, допустимы ли скобки.

Наше решение работает так на высоком уровне: каждый раз, когда мы видим открытую скобку, мы добавляем ее в стек. Каждый раз, когда мы видим закрывающую скобку, мы проверяем, соответствует ли последняя открытая скобка, которую мы видели, закрывающей скобке. Если это не так, мы знаем, что строка недействительна. Если это так, мы извлекаем эту открывающую скобку из стека и продолжаем сканирование строки. Если мы дойдем до конца, последней проверкой будет подтверждение того, что стек пуст, т. е. нет непарных открытых скобок.

Для простоты мы используем встроенный Python list для нашего стека, не забывая всегда добавлять и извлекать с конца. Мы также используем Python dict для поиска наших закрывающих скобок — всякий раз, когда мы видим закрывающую скобку, мы можем быстро найти соответствующую ей открытую скобку.

Мы отслеживаем два случая, когда мы можем выйти из цикла for и объявить, что строка недействительна: 1) если мы встретим закрывающуюся скобку, а стек пуст, и 2) если последняя открывающая скобка не соответствует нашей закрывающей скобке. скобка. Последняя проверка заключается в том, чтобы убедиться, что стек пуст после того, как мы прошли строку.

Давайте посмотрим на это в действии:

Давайте попробуем немного более сложный вариант этого вопроса. В LC 1249: минимальное удаление, чтобы сделать скобки действительными, вместо того, чтобы выводить простое логическое значение да/нет для определения правильности строки, нам нужно сделать строка действительна, если удалить неуместные скобки. Строки также будут содержать смесь букв и скобок, но в качестве небольшой уступки нам придется иметь дело только с изогнутыми скобками. На изображении ниже нам нужно удалить красные скобки, чтобы сделать каждую строку действительной.

Вот как мы это сделаем. На высоком уровне мы будем перемещаться по строке, добавляя в стек, когда видим открывающую скобку, и удаляя из стека, когда видим закрывающую скобку. Если мы встречаем закрывающую скобку без открывающей скобки, мы немедленно удаляем ее — в дальнейшем не будет открытой скобки, которая могла бы соответствовать этой закрытой скобке. Как только мы просмотрим строку, мы удалим все оставшиеся открытые скобки, так как у них не было соответствующих закрывающих скобок.

Давайте посмотрим на код более внимательно. Начнем с преобразования строки в список, поскольку изменять элементы в изменяемых списках гораздо проще, чем в неизменяемых строках. (Нам пришлось бы каждый раз создавать новую строку, а не изменять список на месте.)

Затем мы фактически сохраняем индексы открытых скобок в нашем стеке, а не сами скобки, так как нам нужно знать, где именно удалить неуместную скобку. Мы обращаемся к неуместным закрывающим скобкам при перемещении по строке, поскольку из пустого стека мы знаем, что в строке нет соответствующих открытых скобок из более раннего. Для открытых скобок нам нужно пройти через всю строку, прежде чем узнать, есть ли у них соответствующая закрывающая скобка.

«Удаление» происходит путем замены скобки пустой строкой — поскольку мы отслеживаем индекс неуместных скобок, сдвиг индексов существующих элементов при перемещении по списку может вызвать огромную головную боль. Вместо этого мы удаляем все пустые строки на последнем шаге, когда преобразуем список в строку с ''.join(s).

Наконец, давайте убедимся, что это работает:

Очереди

Давайте теперь переключим наше внимание на варианты использования очередей. Одним из распространенных вопросов, когда очереди полезны, является обход по уровням для деревьев. Как мы можем вывести значение каждого узла в дереве, уровень за уровнем? Обычно нам предоставляется только корневой узел, поэтому мы заранее не знаем, как выглядит дерево. Поэтому мы хотим правильно обрабатывать дерево по мере его изучения.

Как и в нашем предыдущем посте, мы будем использовать следующую реализацию для узла дерева. Этот узел будет бинарным узлом, поскольку он имеет не более двух дочерних элементов, но наш алгоритм обхода по уровням можно легко распространить на узлы с любым количеством дочерних элементов.

Определив TreeNode, давайте напишем функцию, которая выполняет обход по уровням, учитывая корневой узел дерева. Решение восхитительно короткое, если вы используете очередь.

На высоком уровне мы начинаем с постановки в очередь корневого узла. Мы удаляем узел из очереди, добавляем его значение к нашему ответу, затем ставим в очередь его потомков. Затем мы просто повторяем этот процесс, пока не обработаем все узлы. Вот и все!

Как и в наших примерах стека, мы снова используем встроенный list, на этот раз не забывая всегда ставить в очередь в конце (т. е. .append) и удалять из очереди с начала (т. е. .pop(0)). Поскольку новые дочерние узлы всегда добавляются в конец, мы гарантируем, что все узлы на уровне обрабатываются раньше узлов с более низкими уровнями. Ниже мы визуализируем процесс удаления узла B из очереди, добавления его значения к ответу и постановки его дочерних узлов в очередь.

И давайте подтвердим, что это работает:

Более хитрая версия этого вопроса состоит в том, чтобы вернуть только самый правый узел на каждом уровне дерева. Например, в дереве на диаграмме выше мы хотели бы вернуть [A, C, E]. Общая структура ответа LC 199: бинарное дерево, вид справа аналогична нашему ответу выше, но нам нужна дополнительная логика, чтобы проверить, находимся ли мы в самом правом узле.

Обратите внимание, что теперь есть два цикла: цикл while, который перебирает очередь до тех пор, пока она не станет пустой, и цикл for, который обрабатывает все узлы на заданном уровне. «Хитрость» в этом вопросе заключается в том, что если мы сделаем снимок очереди (строка 9) до того, как начнем обрабатывать ее узлы (строка 12), мы сможем увидеть все узлы на заданном уровне, что позволит нам идентифицировать самый правый узел. Этот моментальный снимок имеет решающее значение, так как мы изменяем очередь по мере ее прохождения (строки 21-24).

Ниже мы визуализируем очередь (справа), поскольку наш алгоритм обрабатывает большое дерево (слева). Обратите внимание, как создаются моментальные снимки, когда очередь содержит все узлы уровня (и не более того).

Наконец, давайте подтвердим, что код работает:

Выводы

В этом посте мы подробно рассмотрели два наиболее распространенных абстрактных типа данных: стеки и очереди. Мы рассмотрели их широкий спектр вариантов использования, прежде чем реализовывать их на Python и самостоятельно решать некоторые сложные проблемы.

Если вам интересно узнать больше, очереди с приоритетом — отличный следующий шаг. Этот абстрактный тип данных присваивает ранжирование каждому элементу в очереди, позволяя нам отдавать приоритет одним элементам над другими. Например, линия досмотра в аэропорту работает как классическая очередь в порядке очереди, поскольку пассажиры проходят через металлодетекторы. Но когда прибывает пассажир с TSA PreCheck, он может пропустить вперед и быть обработанным первым. Наличие у пассажира PreCheck определяет его приоритет в очереди.

Наконец, важно повторить, что существует множество способов реализовать стек или очередь. Мы решили использовать связанный список для наших классов Stack и Queue, чтобы отразить то, как эти классы часто реализуются в таких языках, как Java или C, в то время как мы использовали встроенный Python list для наших вопросов Leetcode, чтобы упростить задачу. Но ничто не мешает вам реализовать стек с помощью дерева или очереди с графом! Если подумать, то, что вы можете реализовать очередь с графом, не означает, что вы должны…

Лучший,
Мэтт

Сноски

1. Создание стеков

Это весь код чести, что вы не будете напрямую вызывать методы и атрибуты, начинающиеся с подчеркивания! Python на самом деле не применяет это правило; мы можем легко изменить содержимое и нанести ущерб.

На самом деле в Python нет реального способа защититься от этого. Самое близкое, что мы можем сделать, это немного запутать, используя декоратор @property. Мы можем написать правила для того, как пользователь может получить доступ к псевдониму _password, например, блокируя доступ для чтения или требуя, чтобы входные данные соответствовали некоторым критериям, прежде чем они перезапишут _password. Но если пользователь запрашивает _password напрямую, мы не можем запретить ему просматривать или изменять его.

Также мало надежды дать атрибуту какое-то сумасшедшее имя, так как злоумышленник может просто использовать команду vars, чтобы раскрыть все пикантное содержимое. Хотя они могут не сразу понять, для чего предназначен этот атрибут, у них уже есть аккуратный набор пар ключ-значение для использования.

В конечном счете, любые данные, даже отдаленно важные, должны храниться за API со строгими требованиями безопасности. Если ваша программа действительно хранит конфиденциальные данные в классе Python, например, когда они передаются между базами данных или API-интерфейсами, вы должны убедиться, что нет возможности взаимодействовать с этим классом из внешнего интерфейса.

2. Создание стеков

Важно помнить, что нотация Big O определяет эффективность в наихудшем случае. В наихудшем случае наш поиск потребует сканирования всего стека, чтобы найти искомое значение (то есть все значения n). Это отличается от случая среднего: если значения, которые мы ищем, случайно распределены по всему стеку, мы должны ожидать найти значение в среднем в середине (т. е. n/2 шагов).