Стек, дек, очередь: исследование структур данных и их алгоритмов
Цели и задачи
- Цель по SMART: к концу урока учащиеся смогут различать стек, очередь и дек, объяснять принцип доступа к элементам и применять операции добавления и удаления элементов в алгоритмах и программах на Python.
- Сформировать представление о моделях LIFO и FIFO и связать их с реальными информационными процессами.
- Научить определять допустимую последовательность операций для стека, очереди и дека и прогнозировать состояние структуры после выполнения команд.
- Развивать алгоритмическое мышление, умение исследовать готовый код, находить ошибки и аргументированно выбирать подходящую структуру данных.
- Формировать ответственное отношение к точности программного решения и готовность проверять результат тестированием.
Планируемые результаты
Личностные
- Осознают значение структур данных для будущей учебной и профессиональной деятельности в сфере информационных технологий.
- Проявляют познавательную мотивацию при исследовании практических моделей хранения данных.
- Понимают ценность точности, последовательности и проверки результата при разработке алгоритмов.
- Готовы самостоятельно выбирать способ решения и обосновывать его перед одноклассниками.
Метапредметные
- Выделяют существенные признаки стека, очереди и дека, сравнивают их и строят обобщающую модель.
- Читают и анализируют фрагменты программного кода, прогнозируют результат и сопоставляют его с фактическим выполнением.
- Планируют последовательность действий, распределяют роли в группе и контролируют достижение результата.
- Аргументированно формулируют выводы, задают уточняющие вопросы и используют цифровые инструменты для проверки гипотез.
Предметные
- Знать определения стека, очереди и дека, а также принципы LIFO и FIFO.
- Уметь определять результаты операций push, pop, enqueue, dequeue, appendleft и popleft.
- Уметь моделировать состояние структуры данных после заданной последовательности команд.
- Уметь выбирать стек, очередь или дек для решения алгоритмической задачи и объяснять свой выбор.
- Владеть базовыми приёмами реализации стека и очереди средствами списка и модуля collections языка Python.
Универсальные учебные действия (УУД)
Личностные УУД
- Определяют личный учебный результат и соотносят его с интересом к программированию и будущей профессии.
- Осознают необходимость аккуратного обращения с данными и ответственности за корректность алгоритма.
- Проявляют инициативу при выборе способа представления и проверки решения.
- Оценивают собственную готовность применять изученные структуры в новых задачах.
Регулятивные УУД
- Формулируют цель исследования и составляют план проверки гипотезы.
- Прогнозируют состояние структуры после серии операций.
- Сверяют полученный результат с эталоном или выполнением программы.
- Находят причину ошибки и корректируют алгоритм.
- Оценивают степень достижения цели по предложенным критериям.
Познавательные УУД
- Классифицируют структуры данных по способу доступа к элементам.
- Моделируют работу структур с помощью схем, таблиц и последовательностей команд.
- Анализируют код на Python и устанавливают соответствие между операцией и изменением структуры.
- Выявляют закономерности LIFO и FIFO на основе эксперимента.
- Переносят принцип работы структуры на новую практическую ситуацию.
Коммуникативные УУД
- Распределяют роли в исследовательской группе и согласуют порядок действий.
- Формулируют объяснение алгоритма с использованием предметных терминов.
- Задают вопросы к решению другой группы и аргументированно отвечают на них.
- Сравнивают варианты решений и корректно указывают на обнаруженную ошибку.
- Представляют общий вывод в краткой устной форме.
Подготовка учителя к уроку
- Подготовить презентацию с изображениями стопки книг, очереди покупателей и двусторонней очереди, а также с таблицей операций структур данных.
- Распечатать карточки трёх типов с последовательностями операций — по одной карточке на каждого ученика и дополнительно по одному комплекту на группу.
- Подготовить цветные карточки с обозначениями «стек», «очередь», «дек» — по три комплекта на группу.
- Распечатать лист исследования для каждой группы: исходное состояние, последовательность операций, прогноз, фактический результат, вывод.
- Подготовить карточки с фрагментами кода Python с использованием списка и deque — по одной на группу.
- Вывести на доску памятку: стек — LIFO, очередь — FIFO, дек — доступ с обоих концов.
- Подготовить проектор, компьютер учителя и среду выполнения Python или онлайн-интерпретатор без необходимости регистрации.
- Организовать группы по 3–4 человека и заранее назначить рабочие места для представления результатов.
- Подготовить лист самооценки и три задания для самостоятельной работы: минимальный, базовый и повышенный уровни.
Ход урока
Этап 1. Организационный момент и мотивация (4 мин)
Цель этапа: включить учащихся в исследовательскую деятельность и создать мотивацию через реальные модели хранения и обработки данных.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель приветствует класс и показывает на экране три изображения: стопку книг, очередь людей у кассы и колоду карт, из которой можно брать карту сверху или снизу. Учитель говорит: "Сегодня мы не начнём с готовых определений. Представьте, что вы проектируете программу для библиотеки, службы поддержки и игровой системы. В каждом случае данные поступают и извлекаются по-разному. Как компьютеру описать эти правила так, чтобы алгоритм не нарушал порядок обработки?" | Рассматривают изображения, называют жизненные ситуации и предполагают: "Из стопки первой берут последнюю добавленную книгу", "в очереди первым обслуживается тот, кто пришёл раньше", "из колоды можно брать карту с двух сторон". |
2 мин | Учитель организует приём "Подумай — обсуди в паре — поделись": "Сначала 30 секунд сформулируйте индивидуально, чем отличаются три ситуации. Затем обсудите ответ с соседом и выберите одну точную формулировку для класса. Не называйте пока термины, опишите именно правило доступа к данным." | Индивидуально записывают по одному правилу, обсуждают его в парах и предлагают формулировки: "последний вошёл — первый вышел", "первый вошёл — первый вышел", "добавлять и удалять можно с обоих концов". |
Завершение этапа: учитель подводит итог: "Мы увидели, что одинаковый набор элементов может обрабатываться по разным правилам. Сегодня выясним, как эти правила называются, какими операциями задаются и какую структуру выбрать для алгоритма."
Этап 2. Актуализация знаний и фиксация затруднения (6 мин)
Цель этапа: актуализировать знания о списках, индексах и последовательностях команд и выявить затруднение при моделировании доступа к данным.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель выводит на экран код: `a = [10, 20, 30]`, `a.append(40)`, `x = a.pop()`. Учитель спрашивает: "Как изменится список после каждой строки? Какое значение окажется в переменной x? Почему метод pop без индекса удаляет именно этот элемент?" Затем показывает `a.pop(0)` и просит сравнить операции. | Записывают состояния списка после каждой команды, отвечают: "После append список равен [10, 20, 30, 40], после pop переменная x получает 40, потому что удаляется последний элемент". Сравнивают удаление с конца и начала. |
3 мин | Учитель раздаёт карточки с последовательностью: `push(5)`, `push(8)`, `pop()`, `push(3)`, `pop()`. Говорит: "Не выполняйте команды механически. Нарисуйте структуру после каждого шага и отметьте значения, которые удаляются. Где возникнет первая трудность, если мы запретим удалять элемент из середины?" | В парах моделируют последовательность на карточке, получают удалённые значения "8" и "3", формулируют затруднение: "Нужно точно задать, с какого конца добавлять и удалять элементы". |
Завершение этапа: учитель подводит итог: "Мы умеем изменять список, но для алгоритма важно не только наличие элементов, а строгое правило доступа к ним. Теперь сформулируем вопрос, на который должны ответить в ходе исследования."
Этап 3. Постановка проблемы и целеполагание (4 мин)
Цель этапа: сформулировать учебную проблему, цель и план исследования трёх структур данных.
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель записывает на доске проблемный вопрос: "Как выбрать структуру данных, если порядок добавления и удаления элементов заранее задан условием задачи?" Учитель спрашивает: "Какие сведения нам нужно получить, чтобы ответить на этот вопрос? Какие операции нужно исследовать?" | Предлагают план: "Определить правило доступа", "назвать операции добавления и удаления", "проверить работу на примерах", "сравнить структуры и выбрать подходящую". |
2 мин | Учитель объединяет ответы в цель урока и распределяет роли в группах: оператор команд, аналитик, программист, докладчик. "Каждая группа исследует карточки, затем подтверждает вывод выполнением кода. Ошибка в прогнозе — не повод скрывать результат, а материал для анализа." | Записывают цель и распределяют роли. Формулируют ожидаемый результат: "К концу урока мы сможем распознать стек, очередь и дек по операциям и применить их в задаче". |
Завершение этапа: учитель подводит итог: "План исследования готов: сначала построим модели, затем сопоставим их с кодом и в конце проверим себя на новой задаче. Переходим к открытию понятий."
Этап 4. Открытие нового знания: стек, очередь и дек (10 мин)
Цель этапа: вывести и зафиксировать принципы работы стека, очереди и дека через групповое исследование и программный эксперимент.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | Учитель раздаёт группам листы исследования и карточки с операциями. Говорит: "Первая группа исследует стек, вторая — очередь, третья — дек. На листе сначала запишите прогноз, не запуская код. Для каждой структуры укажите, откуда добавляется элемент и откуда удаляется. Используйте условные обозначения стрелками." | В группах моделируют структуру. Для стека фиксируют принцип LIFO и операции push/pop; для очереди — FIFO и enqueue/dequeue; для дека — добавление и удаление с левого и правого концов. |
3 мин | Учитель выводит на экран три фрагмента: `stack.append(x); stack.pop()`, `queue.append(x); queue.pop(0)`, `from collections import deque; d.append(x); d.popleft()`. Обращается к классу: "Сопоставьте фрагмент с моделью. Какие операции опасны для большой очереди по времени выполнения и почему?" | Сопоставляют код и модели, отвечают: "Первый фрагмент реализует стек, второй — очередь, третий — дек". Формулируют, что удаление `pop(0)` требует сдвига элементов списка, поэтому для очереди удобнее `deque`. |
3 мин | Учитель организует представление групп: "Докладчик за одну минуту объясняет правило доступа, показывает одну последовательность операций и называет область применения. Остальные группы записывают общий признак и задают по одному уточняющему вопросу." | Представляют результаты: стек используют для истории действий и возврата, очередь — для обслуживания запросов и задач печати, дек — для обработки данных с двух концов. Задают вопросы о направлении операций и порядке удаления. |
Запись в тетрадях
- Стек — структура данных, в которой последний добавленный элемент извлекается первым: LIFO; основные операции — push и pop.
- Очередь — структура данных, в которой первый добавленный элемент извлекается первым: FIFO; основные операции — enqueue и dequeue.
- Дек — двусторонняя очередь, в которой добавление и удаление выполняются с левого и правого концов.
- Для реализации стека в Python удобно использовать список и методы append, pop; для дека — `collections.deque` и методы append, appendleft, pop, popleft.
Завершение этапа: учитель подводит итог: "Теперь у нас есть не просто названия, а точные правила и операции. Проверим, умеем ли мы применять их к последовательностям команд без подсказки готового рисунка."
Этап 5. Первичное закрепление: моделирование операций (7 мин)
Цель этапа: закрепить алгоритмы выполнения операций и научиться пошагово прогнозировать состояние структуры.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | Учитель раздаёт каждой паре одну из карточек. Карточка А: стек пуст; `push(4)`, `push(7)`, `pop()`, `push(2)`, `pop()`. Карточка Б: очередь пуст; `enqueue(4)`, `enqueue(7)`, `dequeue()`, `enqueue(2)`, `dequeue()`. Карточка В: дек пуст; `append(4)`, `appendleft(7)`, `pop()`, `popleft()`. Учитель говорит: "Заполните таблицу: команда, состояние структуры, удалённое значение. Каждая строка должна быть проверяема." | Пошагово заполняют таблицы и получают: для стека удаляются 7 и 2; для очереди — 4 и 7; для дека сначала удаляется 4, затем 7. Сверяют результат с соседом. |
3 мин | Учитель приглашает представителей трёх пар к доске и проводит взаимопроверку: "Покажите не только ответ, но и место, из которого был удалён элемент. Если не согласны, укажите конкретный шаг и объясните правило." | Представляют решения, указывают направление доступа стрелкой, исправляют ошибки. Формулируют вывод: "Ответ зависит не от значения элемента, а от его положения относительно конца или начала структуры". |
Эталон решения
Для стека: после `push(4)` получаем [4], после `push(7)` — [4, 7], команда `pop()` удаляет 7, затем `push(2)` даёт [4, 2], следующий `pop()` удаляет 2. Для очереди элементы удаляются в порядке поступления: после добавления 4 и 7 команда `dequeue()` удаляет 4, затем после добавления 2 следующая команда удаляет 7. Для дека после `append(4)` и `appendleft(7)` получаем [7, 4]; `pop()` удаляет 4, а `popleft()` — 7.
Завершение этапа: учитель подводит итог: "Мы проверили операции на бумажной модели и увидели, что последовательность нельзя угадывать по последней строке — нужно проследить каждый шаг. Теперь каждый самостоятельно проверит, насколько уверенно применяет правила."
Этап 6. Самостоятельная работа с самопроверкой (9 мин)
Цель этапа: диагностировать индивидуальное понимание структур данных и обеспечить самопроверку по критериям.
Время | Действие учителя | Действие учеников |
|---|---|---|
6 мин | Учитель раздаёт индивидуальные карточки трёх уровней. Базовый уровень: определить структуру по описанию и назвать принцип LIFO или FIFO. Средний уровень: определить состояние стека после `append(6)`, `append(1)`, `pop()`, `append(9)`, `pop()`. Повышенный уровень: выбрать структуру для обработки запросов сервера, истории переходов браузера и проверки палиндрома, обосновав каждый выбор. Учитель напоминает: "Сначала решите самостоятельно, затем отметьте место, где возникло сомнение." | Решают выбранный уровень индивидуально. В базовом задании записывают «стек» и «очередь»; в среднем получают удалённые значения 1 и 9; в повышенном объясняют: очередь — для запросов, стек — для истории, дек или сочетание дека со сравнением концов — для палиндрома. |
3 мин | Учитель показывает эталон на экране и проводит приём "Светофор": "Зелёная карточка означает, что вы можете объяснить выбор без подсказки; жёлтая — что нужна проверка одного шага; красная — что необходимо разобрать модель ещё раз. Отметьте также одну ошибку, если она была." | Сверяют решения с эталоном, исправляют записи другим цветом, поднимают карточку нужного цвета и формулируют индивидуальную трудность. |
Завершение этапа: учитель подводит итог: "Самостоятельная проверка показала, что правило доступа уже можно применять к новым ситуациям. Осталось связать структуры с выбором алгоритма и объяснить, почему одна и та же задача не всегда решается одинаково эффективно."
Этап 7. Включение в систему знаний и рефлексия (5 мин)
Цель этапа: обобщить различия структур, связать их с практическими задачами и осмыслить результат урока.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель предлагает заполнить устную таблицу сравнения: "Назовите структуру, если в условии сказано: отменить последнее действие; обслужить клиентов по порядку поступления; добавлять элементы с обоих концов. Какой вопрос нужно задать себе перед выбором структуры?" | Отвечают: "Стек", "очередь", "дек". Формулируют алгоритм выбора: "Нужно определить, с какого конца добавляются и удаляются элементы и сохраняется ли порядок поступления". |
2 мин | Учитель проводит "Билет на выход": "Запишите три короткие фразы: одно определение, одну операцию и один пример применения. Дополните предложение: «Теперь я понимаю, что…», а также укажите вопрос, который ещё требует пояснения." | Заполняют билет на выход: например, "Стек работает по LIFO; pop удаляет верхний элемент; стек используется для истории действий". Отмечают оставшийся вопрос или пишут, что затруднений нет. |
Завершение этапа: учитель подводит итог: "Сегодня вы исследовали структуры данных как разработчики: выдвигали гипотезу, моделировали операции, проверяли код и исправляли ошибки. На следующем уроке мы применим стек и очередь при решении алгоритмических задач и оценим эффективность разных реализаций."
Критерии оценивания практической работы
- «5» — правильно определены все три структуры или выполнены все операции индивидуальной карточки, объяснены принципы LIFO и FIFO, состояние структуры показано по шагам, выбор структуры обоснован.
- «4» — допущена одна неточность в последовательности операций или формулировке, но основные различия стека, очереди и дека поняты и объяснены.
- «3» — правильно определена хотя бы одна структура и выполнена базовая часть задания, однако имеются ошибки в порядке удаления или отсутствует полное обоснование.
- Ниже отметки «3» — не различены правила доступа к данным и не прослежена последовательность операций; требуется повторная работа с моделью.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Что нового вы узнали о принципах LIFO и FIFO? | Проверка осознания ключевого предметного содержания. |
Какую структуру вы выберете для истории действий пользователя и почему? | Выявление умения переносить знание в практический контекст. |
На каком шаге моделирования операций возникло затруднение? | Выявление точек затруднения в алгоритме рассуждения. |
Насколько уверенно вы сможете объяснить различие стека, очереди и дека однокласснику? | Субъективная оценка уровня освоения темы и готовности к дальнейшей работе. |
Завершающее слово учителя
"Сегодня мы увидели, что структура данных — это не просто контейнер для значений, а правило работы с ними. Стек возвращает последний добавленный элемент, очередь сохраняет порядок поступления, а дек позволяет работать с обоими концами. Типичная ошибка — смотреть только на набор элементов и не учитывать последовательность операций. На следующем уроке мы проверим эти модели в алгоритмах и программах, где правильный выбор структуры влияет на эффективность решения."
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый (обязательный) | Составить сравнительную таблицу стека, очереди и дека: принцип доступа, операции добавления и удаления, один жизненный пример для каждой структуры. Выполнить 3 короткие последовательности операций и указать удалённые элементы. | Закрепляет определения и порядок выполнения операций; при проверке обратить внимание на точность терминов и отсутствие перестановки LIFO и FIFO. |
Средний (повышающий) | Написать и протестировать программу на Python: реализовать стек средствами списка и обработать последовательность из не менее чем шести команд добавления и удаления; вывести удалённые элементы и итоговое состояние. | Формирует умение переводить модель в код; при проверке смотреть на соответствие операций условию и наличие проверки результата. |
Продвинутый (дополнительный) | Разработать небольшое решение для одной ситуации на выбор: история переходов, очередь запросов или проверка палиндрома. Обосновать выбор структуры, привести два теста и описать один возможный ошибочный случай. | Развивает проектное и алгоритмическое мышление; при проверке оценивать обоснование выбора, полноту тестирования и анализ граничного случая. |
Контрольные вопросы перед выходом: «Какая структура работает по принципу LIFO?», «Какая структура сохраняет порядок поступления элементов?», «С какой стороны можно добавлять и удалять элементы дека?», «Какую структуру вы выберете для отмены последнего действия пользователя и почему?»