Я начала изучать алгоритмы (наконец-то доросла до них), так что буду иногда и про это теперь писать.
Для меня лучшая аналогия стека: пачка бумажных писем. Например, в Гарри Поттере, когда Гарри пошел забирать почту, то он взял все письма и просматривал их сверху вниз, откладывая письмо для Вернона и пропуская счета. Это и есть стек. Когда все элементы как стопочка и доступен только верхний элемент. Получить доступ к следующему можно только удалив верхний.
Стек работает по принципу LIFO (Last-In-First-Out). Т.е. элемент, который записали последним, будет первым извлечен. Идем сверху вниз.
Сложность стека: О(1). Время выполнения не зависит от количества элементов.
Самая простая реализация стека на котлине:
Стек реализован на базе массива, поэтому внутрь передаем размер массива.
Пройдемся по методам и переменным:
top — индекс элемента, который находится на вершине стека.
push() — добавляем в стек новое число. Перед добавлением увеличиваем top.
pop() — возвращает значение, которое находится на вершине стека и уменьшает top. Т.е. мы как бы уменьшили массив, хотя значение там осталось.
peek() — просто возвращает верхнее значение, ничего не уменьшая.
isEmpty() — возвращает true, если массив пустой. Для пустого стека top равна -1 (мы это написали в самом начале). Для заполненного стека top = maxSize - 1. Вычитаем единицу, потому что массив начинается с нуля.
Одна из самых популярных задач для стека: поиск парных скобок. Попробуйте самостоятельно решить задачу, используя стек:
Проверьте, что во входящей строке все скобки расставлены правильно. Если не правильно, то верните индекс первой ошибочной скобки.
Мой вариант решения, который не претендует на абсолютную правильность: https://gist.github.com/Ladgertha/83dfdf525871a1608d507a43c5b0271c. А еще можно погуглить задачи на скобки и потренироваться на разных сайтах. На литкоде точно есть такие задачи. Уже проверила: https://leetcode.com/problems/valid-parentheses/
