Стек и очередь

Стек (LIFO) и очередь (FIFO): скобочные последовательности и порядок обработки.

Две простейшие структуры данных различаются порядком извлечения: • Стек — LIFO (last in, first out): последним пришёл — первым ушёл. Как стопка тарелок. • Очередь — FIFO (first in, first out): первым пришёл — первым ушёл. Как очередь в магазине. Стек в C++ — std::stack (push, top, pop), очередь — std::queue (push, front, pop). Каноническая задача на стек — правильная скобочная последовательность: каждая закрывающая скобка должна соответствовать последней открытой. «Последней открытой» — это и есть вершина стека.

Попробуйте сами — код можно менять

Входные данные (пример — можно менять)

Проверка скобок трёх видов. Введите: ([]{}())

Обратите внимание на две проверки, которые часто забывают: закрывающая скобка при ПУСТОМ стеке (лишняя закрывающая) и НЕПУСТОЙ стек в конце (незакрытые скобки). Очередь вы уже видели, даже если не заметили: она лежит в основе обхода в ширину (BFS), который ждёт вас на уровне 4. Пока — минимальный пример порядка обслуживания.

Попробуйте сами — код можно менять

Очередь: кто пришёл первым, тот и обслужен первым

Задание: по строке из скобок найдите длину самого глубокого вложения (подсказка: это максимальный размер стека за всё время; для одного вида скобок хватит даже счётчика). Отметьте урок пройденным и переходите к set и map.