Stack (Стек)

Стек — структура данных, работающая по принципу LIFO (Last In, First Out): последний добавленный элемент извлекается первым. Основные операции — push (добавить наверх), pop (снять верхний), peek (посмотреть верхний) — все за O(1).

Реализация и задача: проверка сбалансированности скобок

Напишите функцию isBalanced, которая принимает строку со скобками (), [], {} и определяет, сбалансированы ли они. Классический пример применения стека.

class Stack<T> {
    private items: T[] = [];
 
    push(item: T): void {
        this.items.push(item);
    }
 
    pop(): T | undefined {
        return this.items.pop();
    }
 
    peek(): T | undefined {
        return this.items[this.items.length - 1];
    }
 
    isEmpty(): boolean {
        return this.items.length === 0;
    }
 
    size(): number {
        return this.items.length;
    }
}
 
function isBalanced(str: string): boolean {
    const stack = new Stack<string>();
    const pairs: { [key: string]: string } = {
        ')': '(',
        ']': '[',
        '}': '{'
    };
 
    for (const char of str) {
        // Если это открывающая скобка
        if (char === '(' || char === '[' || char === '{') {
            stack.push(char);
        }
        // Если это закрывающая скобка
        else if (char === ')' || char === ']' || char === '}') {
            // Проверяем, есть ли соответствующая открывающая скобка
            if (stack.isEmpty() || stack.pop() !== pairs[char]) {
                return false;
            }
        }
        // Игнорируем другие символы
    }
 
    // Строка сбалансирована, если стек пуст
    return stack.isEmpty();
}
 
// Примеры использования
console.log(isBalanced("()"));        // true
console.log(isBalanced("()[]{}"));    // true
console.log(isBalanced("([{}])"));    // true
console.log(isBalanced("([)]"));      // false
console.log(isBalanced("((("));       // false
console.log(isBalanced(""));          // true
console.log(isBalanced("{[()]}"));    // true
console.log(isBalanced("({[}])"));    // false

Временная сложность: O(n) — проходим по строке один раз. Пространственная сложность: O(n) — в худшем случае все символы открывающие.

Где применяется стек

• Проверка сбалансированности скобок, парсинг выражений
• Undo/redo, история навигации браузера
• Call stack (стек вызовов функций)
• Обход дерева/графа в глубину (DFS) без рекурсии
• Monotonic stack — «следующий больший/меньший элемент»

См. также

• queue — очередь FIFO
• get-nodes — обход дерева на стеке