Стек и очередь на Python: как решать + 4 задач с проверкой

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

Как распознать задачу

Частые признаки в условии:

• есть вложенность или «отмена последнего» (скобки, теги, пути, команды undo);
• нужно для каждого элемента найти ближайший подходящий слева/справа (больше/меньше/не слабее);
• идёт поток запросов «добавь в конец / убери из начала» или симуляция очереди;
• требуется минимум/максимум на скользящем окне — обычно намекает на монотонную очередь.

Суть приёма

Мы поддерживаем структуру, где «актуальный край» доступен за O(1): у стека — вершина, у очереди — голова/хвост. За счёт этого каждый элемент обычно добавляется и удаляется не больше одного раза, поэтому многие задачи решаются за O(n) вместо перебора всех пар за O(n^2).

С чего начать

• выучи операции: push/pop/top для стека, push/pop/front для очереди и очередь на двух стеках;
• отработай шаблон проверки правильной скобочной последовательности: кладём открывающие, закрывающие сверяем с вершиной;
• разберись с монотонным стеком (следующий больший/меньший) и монотонной очередью (минимум/максимум в окне);
• тренируй аккуратность на больших ограничениях: строки и массивы до 200000 требуют линейных решений.

Ниже — задачи с автопроверкой и разбором подхода.