Немногие структуры данных настолько распространены, как стек. Их легко понять и реализовать, но в их простоте есть сила. Цель этой статьи - объяснить, что такое стек и как его реализовать, а также представить три практических примера использования. Приступим!

Скопируйте репозиторий, сопровождающий эту статью, здесь.

Объяснение: Стеки против массивов

Стек - это структура, которая отвечает за динамический сбор данных в соответствии с принципом LIFO (последний пришел, первый ушел). В качестве аналогии вы можете представить себе стопку подносов в кафетерии: когда вы хотите добавить новый поднос, он помещается в верхнюю часть стопки (вместо того, чтобы вставляться где-то внутри). Поскольку последний лоток находится наверху стопки, он также будет первым, чтобы оторваться, когда потребуется отдельный лоток. Стеки выполняют две основные функции: «выталкивание» или введение нового элемента и «выталкивание» или удаление последнего элемента.

Если мы сравним эту структуру с типичным массивом, станут очевидны некоторые четкие различия. В то время как распределение памяти для массивов осуществляется Swift интеллектуальным образом, в основных языках емкость массива устанавливается во время инициализации и является статической. С другой стороны, стеки выделяют и освобождают память для отдельных узлов по мере необходимости, что делает их очень гибкими. Кроме того, массивы разрешают доступ к элементам по любому индексу, в то время как стеки взаимодействуют только с конечным узлом. Хотя это может показаться ограничивающим (это…), на самом деле доступ к данным становится очень легким и быстрым. Кроме того, поведение LIFO может быть очень полезным для решения конкретных ситуаций, которые мы рассмотрим позже в этой статье.

Стек: демонстрационная реализация

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

Сначала давайте посмотрим на наш класс (строки 1–14). Здесь мы используем общий заполнитель ‹›, чтобы экземпляр узла мог содержать значение любого типа, который нам нравится. Для наших целей мы ограничиваем тип данных CustomStringConvertible (строка 1) , чтобы мы могли легко печатать к консоли. Затем у нас есть два свойства типа Node ‹T›? (строки 4–5). Это сделано для того, чтобы мы могли связать наши узлы вместе по мере необходимости. Эти два свойства являются необязательными, поскольку первый и последний узлы будут указывать на ноль в своих свойствах previous и next соответственно. Поскольку каждая последующая пара узлов будет удерживать друг друга, нам нужно сделать одно из свойств слабым, чтобы избежать цикла сохранения (строка 4) . Также обратите внимание, что, поскольку мы создаем составной тип, в котором один узел содержит ссылки на другие узлы, мы должны использовать класс вместо структуры.

Затем наш класс (строки 17–23) просто содержит связанный список узлов. У нас есть rootNode для хранения начала списка, а затем endNode, который мы используем, чтобы вставлять и выталкивать узлы в конце списка. Опять же, эти свойства помечены как необязательные Узел ‹T›?, поэтому они могут быть нулевыми, когда список пуст. Визуальное представление нашего стека с тремя узлами в нем будет выглядеть так:

Теперь давайте посмотрим, как поместить новый элемент в наш стек. Шаг 1. Создайте новый узел с нужным нам значением. Шаг 2. Если endNode указывает на узел, мы можем назначить следующее свойство в нашем конечном узле новому узлу, а предыдущее свойство в нашем новом узле - обратно нашему конечному узлу. Помните, что предыдущее свойство является слабым, поэтому мы избегаем цикла сохранения. Шаг 3. Наконец, мы можем переместить указатель endNode на наш newNode, обратившись к его следующему свойству. Обратите внимание, что объем памяти, необходимый для нашего списка, увеличивается с выделением и инициализацией newNode.

Наш метод pop () удаляет конечный узел и возвращает значение, которое было в узле. Шаг 1. Мы сохраняем значение в нашем конечном узле во временной константе val. Шаг 2. Мы перемещаем указатель endNode на один элемент назад, используя его свойство previous. Шаг 3. Мы устанавливаем свойство endNodes next равным нулю. Теперь единственная ссылка между двумя последними узлами - через предыдущее свойство, которое было помечено как слабое. Это означает, что узел освобожден от памяти. Шаг 4: Мы возвращаем значение, которое было в нашем последнем узле.

После объяснения этих важных методов давайте взглянем на окончательную реализацию нашего класса Stack:

Методы push и pop отображаются точно так, как мы ожидали, (строки 13–32). Мы можем использовать наш метод push для создания настраиваемого инициализатора с некоторыми переменными значениями (строки 7–11). Кроме того, мы можем проверить наличие пустого стека, проверив, есть ли у нашего rootNode значение (строки 34–36) и базовый метод печати, который выполняет итерацию по нашему списку до тех пор, пока он может получить доступ к узлам через свойство next ( строки 38–44).

Базовый тест функциональности нашего стека выглядит так:

Примеры использования стека

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

Сценарий использования 1: изменение порядка

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

Пример использования 2: проверка симметрии

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

Мы начинаем с проверки того, что количество символов делится на два, как нечетное количество символов сразу после асимметричного (строка 6). Затем мы проверяем, что у нас есть допустимый ввод, определяя набор символов недопустимых символов, а затем проверяем, что наша строка ввода имеет нулевой диапазон недопустимых символов (строки 7–8). Чтобы проверить, совпадают ли закрывающая и открывающая скобки, мы помещаем их в словарь как пары "ключ-значение" (строка 10). В других ситуациях вы можете вычислить обратное значение, не сохраняя пары в словаре. Затем у нас есть стек (строка 11). В данном случае цель нашего стека - хранить открывающие скобки. По мере того, как мы перебираем нашу строку, мы можем проверить, является ли наш символ открывающей скобкой, проверив, является ли он ключом в нашем словаре. Если это так, мы помещаем его в наш стек. Как только мы находим нашу первую закрытую скобку, мы знаем, что прорабатываем вторую половину нашего шаблона, поэтому мы устанавливаем для нашего firstHalf логическое значение false (строка 12). Если после этого момента мы обнаружим еще какие-либо открывающие скобки, мы можем проверить логическое значение и указать на неудачный тест. Для каждой закрывающей скобки мы снимаем последнюю открывающую скобку и проверяем, являются ли они правильной парой "ключ-значение". Еще раз, нам нужно выполнить итерацию по строке только один раз, поэтому мы получаем много пользы от линейного алгоритма.

Сценарий использования 3: отмена команд

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

Вместо прямого вызова методов пополнения и снятия средств мы можем сохранить соответствующую информацию в команде. В приведенном ниже фрагменте мы указываем, какое действие мы хотим выполнить со свойством перечисления (депозит или снятие) и суммой. Мы также сохраняем логическое значение, чтобы указать, можно ли выполнить команду (строки 4–11). Обратите внимание, что если запрос на снятие средств превышает лимит овердрафта, с банковским счетом ничего не произойдет, и логическое значение, полученное успешно, останется ложным, в противном случае оно станет истинным после завершения команды (строки 18–26). У нас есть два метода для вызова или отмены команды, каждый из которых принимает в качестве аргумента банковский счет (строки 18 и 28). Эти методы принимают банковский счет и вызывают методы его экземпляра, которые мы видели в предыдущем фрагменте.

Вернувшись к банковскому счету, теперь мы можем ввести свойство commandStack, которое было инициализировано с помощью нашего BankAccountType (строка 47). . Мы помечаем наши методы пополнения и снятия средств как fileprivate , чтобы они были доступны только нашей BankAccountCommand (строки 62 и 66) . Теперь у нас есть два открытых метода: process (command :) и undoLastCommand (). Первый принимает команду в качестве входных данных, выполняет ее с банковским счетом в качестве входных данных, а затем помещает команду в стек. Тем временем метод undoLastCommand извлекает последнюю команду из стека и выполняет отмену (строки 51–60).

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

А теперь давайте посмотрим на схему в действии:

Заворачивать

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