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

В этой статье ознакомимся с 2 ключевыми базовыми техниками:

1. Bracket Matching (Algorithmic Technique)

2. Stack Simulation (Pattern)

Техника 1. Bracket Matching

Мотивация

Очень часто в задачах требуется проверить правильность скобочной последовательности.
Пример постановки: дана строка, содержащая символы (), [], {}, и нужно определить, является ли она корректной — то есть каждая открывающая скобка должна иметь соответствующую закрывающую в правильном порядке.

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

Эта проблема эффективно решается техникой Stack Bracket Matching.

Как это работает?

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

Пример: строка "([{}])"

Шаги работы стека:

• ( → push → ['(']

• [ → push → ['(', '[']

• { → push → ['(', '[', '{']

• } → pop { → ['(', '[']

• ] → pop [ → ['(']

• ) → pop ( → []

Итог: стек пуст → последовательность корректна.

Пошаговая логика

1. Создать пустой стек.

2. Для каждого символа строки:

   • если это открывающая скобка → push в стек;

   • если закрывающая → проверить:

     • стек не пуст,

     • верхний элемент соответствует типу скобки,

     • затем выполнить pop.

3. После обхода строка корректна, если стек пуст.

Псевдокод

function isValid(s):
    stack = new Stack()    // создаём пустой стек для открывающих скобок
    for ch in s:           // перебираем каждый символ строки
        if ch in ['(', '[', '{']:
            stack.push(ch)    // открывающая скобка → кладём в стек
        else if ch in [')', ']', '}']:
            if stack.empty():    // стек пуст, а встретилась закрывающая
                return false
            top = stack.pop()    // снимаем верхнюю открывающую скобку
            if not matches(top, ch):    // проверка типов скобок
                return false
    return stack.empty()    // итог: все пары закрыты

Сложность

• Время: O(n), где n длина строки.

• Память: O(n) в худшем случае (все символы тут открывающие скобки).

Подводные камни

• Попытка вызвать pop() на пустом стеке.

• Неправильное соответствие типов скобок (например, [ и )).

• Забыть в конце проверить, что стек пуст.

LeetCode задачи

• 20. Valid Parentheses

• 1021. Remove Outermost Parentheses

Используйте JUMBAQ Framework для систематичного решения leetcode задач

Техника 2. Stack Simulation Pattern

Мотивация

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

• символ # означает удалить предыдущий символ,

• команда может «отменить» результат,

• несколько последних значений нужно пересчитать.

Решение «в лоб» через строки или массивы неэффективно: приходится пересоздавать результат заново, что может привести к O(n²).

Стек позволяет моделировать состояние пошагово и делать это за O(n).

Варианты применения

У паттерна Stack Simulation выделяют два основных варианта:

1. State Tracking: отслеживание состояния строки (Backspace, удаление дубликатов).

2. History Calculations: хранение истории и пересчёт числовых операций (Baseball Game).

В этой статье разберём State Tracking.

Как работает State Tracking?

Правило:

• обычный символ → push в стек,

• управляющий символ (например, #) → pop (если стек не пуст).

Таким образом, в стеке всегда хранится текущее состояние строки.

Пример: строка "ab#c"

Шаги стека:

• a → ['a']

• b → ['a', 'b']

• # → pop b → ['a']

• c → ['a', 'c']

Итоговая строка: "ac".

Пошаговая логика

1. Создать пустой стек.

2. Для каждого символа:

   • если это буква → push;

   • если это # и стек не пуст → pop.

3. Итоговая строка = соединение символов из стека.

Псевдокод

stack = new Stack()
for ch in s:
    if ch != '#':
        stack.push(ch)      // обычный символ
    else if not stack.empty():
        stack.pop()         // удаление предыдущего
return join(stack)

Сложность

• Время: O(n).

• Память: O(n) в худшем случае.

Подводные камни

• Проверять, что стек не пуст перед pop.

• Несколько # подряд → нужно обрабатывать корректно.

• Итоговую строку собирать эффективно (через StringBuilder или join).

LeetCode задачи

• 844. Backspace String Compare

• 1047. Remove All Adjacent Duplicates In String

• 1544. Make The String Great

Используйте JUMBAQ Framework для систематичного решения leetcode задач

Итог

Эти две техники, Bracket Matching и Stack Simulation (State Tracking), формируют фундамент работы со стеком. Они встречаются в десятках задач и собеседований, и, освоив их, вы сможете уверенно решать целый класс проблем.