Лекция 2. Структуры данных stack, deque и queue. Задачи на обработку последовательностей

На втором занятии разбираем задачи из тематического контеста к первой теме, а затем переходим к структурам данных stack, queue, deque и способам линейной обработки последовательностей. Вы узнаете: - как устроены и чем отличаются stack, queue и deque; - как выбрать подходящую структуру данных по набору нужных операций; - как работает очередь на минимум и почему она обрабатывает все запросы за O(n); - что такое монотонный стек и как находить ближайший больший или меньший элемент. Вы увидите, как с помощью этих структур строить эффективные алгоритмы обработки последовательностей, работающие за линейное время. После просмотра лекции я предлагаю вам решить задачи второго тематического контеста, чтобы закрепить полученные знания на практике и проверить усвоение темы. Для этого нужно войти в группу на Codeforces https://codeforces.com/group/MwZqR4Zf5z как «Участник» и приступить к решению контеста, отыскав его во вкладке «Соревнования»: https://codeforces.com/group/MwZqR4Zf5z/contests. Для тех, кому читать проще, чем смотреть видео, подготовили лекцию в текстовом формате: https://github.com/dmkz/competitive-programming/blob/master/mirea/cources/2026-2027/aii-july/02/README.md. Смотрите, вдохновляйтесь и учитесь вместе с нами! Таймкоды: 00:00:00 Разбор "А. Второй максимум" 00:02:45 Разбор "B. Чётная сортировка" 00:09:05 Разбор "C. Запросы к массиву" 00:14:30 Разбор "D. Сколько меньших?" 00:18:14 Разбор "E. Пары с ограниченной суммой" 00:29:30 Начало новой темы 00:31:30 Структура данных "Стек" 00:40:40 Структура данных "Очередь" 00:48:40 Пример использования std::stack 00:50:05 Пример использования std::queue 00:52:05 Структура данных "Двунаправленная очередь" 00:59:15 Общие советы по выбору структуры данных 01:06:20 Использование стека в линейных алгоритмах 01:14:35 Пример: скобочный баланс 01:26:47 Амортизированная оценка числа операций 01:30:10 Монотонный стек, ближайший меньший слева элемент 01:52:20 Реализация монотонного стека на C++ 01:54:55 Очередь на минимум (кратко) 01:57:00 Завершение