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

Стек и очередь: две модели порядка

Когда в задаче нужно понять, какой элемент обработают первым, многие школьники начинают перебирать варианты и быстро запутываются. Стек и очередь помогают заменить длинные рассуждения понятным правилом: один элемент добавился, другой вышел. Разберём эти структуры так, чтобы ты мог узнавать их в условии, выполнять операции вручную и уверенно решать задания по алгоритмам на уроке и экзамене.

Стек работает по принципу LIFO: последним положили — первым достали. Представь стопку тарелок: снять можно только верхнюю. Основные операции называются так:

push(x) — положить элемент x на вершину
pop() — снять верхний элемент
top() — посмотреть верхний элемент, не снимая его

Очередь работает по принципу FIFO: первым пришёл — первым обслужен. Это похоже на очередь в магазине. Новый участник встаёт в конец, а выходит тот, кто стоит впереди.

Как работает стек

У стека есть только одна рабочая сторона — вершина. Если записать элементы слева направо как 4, 7, 2, то вершиной будет 2. После операции push(9) получится 4, 7, 2, 9, а после pop() удалится именно 9. Элементы 2, 7 и 4 пока не изменят порядок.

Стек удобно использовать там, где нужно вернуться к последнему незавершённому действию. Например, браузер хранит историю переходов, а редактор может отменять последние изменения. В математике стек встречается при проверке правильности скобок: открывающую скобку кладут внутрь, а при закрывающей сравнивают её с верхней.

Начало: [ ]
push(3) → [3]
push(8) → [3, 8]
pop() → удалён 8, осталось [3]
top() → 3

Если попытаться выполнить pop() у пустого стека, возникнет ошибка: извлекать нечего. В некоторых задачах отдельно проверяют переполнение, если стек имеет ограниченный размер. В обычном школьном примере важно следить за тем, где находится вершина и какая операция выполняется последней.

Для закрепления можно потренироваться в личном кабинете с бесплатными заданиями: после каждого шага проговаривай, почему элемент оказался сверху.

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

В очереди элементы движутся в одном направлении. Добавление происходит в конец, или хвост, а удаление — из начала, или головы. Если в очереди стоят 5, 6 и 9, то добавление 4 даст последовательность 5, 6, 9, 4. Операция удаления уберёт 5, а не последний элемент.

Названия операций могут различаться в учебниках и языках программирования, но смысл остаётся тем же:

enqueue(x) — добавить x в конец
dequeue() — удалить элемент из начала
front() — посмотреть первый элемент

Структура	Кто выходит первым	Пример
Стек	Последний добавленный	Стопка книг
Очередь	Первый добавленный	Люди у кассы

Очередь применяют для обработки заявок, печати документов и обхода вершин графа по уровням. Если условие говорит «обслужить в порядке поступления», почти наверняка нужна очередь. Если сказано «вернуться к последнему выбору», ищи стек.

Попробуй решить несколько похожих ситуаций в бесплатной практике школы: определяй структуру до того, как начнёшь считать.

Разобранный пример

Рассмотрим последовательность операций над пустым стеком. Нужно определить, что напечатает алгоритм:

push(4)
push(7)
pop() → напечатать удалённое значение
push(2)
push(9)
pop() → напечатать удалённое значение
pop() → напечатать удалённое значение

Начинаем с пустого стека. После push(4) внутри находится 4. Затем добавляется 7, поэтому вершина меняется на 7. Первая операция pop() снимает верхний элемент, значит, печатается 7, а в стеке остаётся 4.

Теперь push(2) кладёт 2 поверх 4, а push(9) — 9 поверх 2. Следующий pop() удаляет 9 и печатает его. После этого верхним становится 2. Последний pop() удаляет и печатает 2.

Стек по шагам: [ ] → [4] → [4, 7] → [4]
После push(2), push(9): [4] → [4, 2] → [4, 2, 9]
Ответ: 7, 9, 2

Обрати внимание: 4 не вывелась, потому что операций удаления было только три. В задачах с очередью тот же список действий дал бы другой результат: удалялись бы элементы с начала, то есть 4, затем 7 и 2.

Ошибки и связь с экзаменом

Первая типичная ошибка — считать стек очередью и удалять первый записанный элемент. Проверяй ключевое правило LIFO. Вторая — путать просмотр и удаление: top() показывает вершину, но оставляет её внутри, а pop() меняет структуру. Третья — забывать, что после pop() вершиной становится предыдущий элемент.

Четвёртая ошибка появляется в таблицах: ученик смотрит только на начальные данные и не учитывает промежуточные операции. Записывай состояние после каждого push, pop, enqueue или dequeue. Если элементов много, обозначай начало и конец очереди стрелками.

На экзамене такие задания проверяют не скорость запоминания терминов, а аккуратность моделирования алгоритма. Для подготовки полезны варианты ЕГЭ по математике и ОГЭ с заданиями по алгоритмам. Решай сначала короткие цепочки, затем увеличивай количество операций.

Что запомнить

Стек подчиняется правилу LIFO: последним добавили — первым извлекли. Его рабочая точка — вершина. Очередь подчиняется правилу FIFO: первым добавили — первым извлекли. В неё добавляют в конец, а удаляют из начала.

Перед решением задачи определи три вещи: какая структура используется, где происходит добавление и откуда происходит удаление. После каждой операции фиксируй состояние. Не смешивай pop() с просмотром вершины и не удаляй из очереди последний элемент, если условие этого не говорит.

Следующий шаг простой: зарегистрируйся и реши 5 заданий бесплатно в личном кабинете. После каждого ответа объясни себе порядок выхода элементов одной фразой. Если объяснение получается без подсказки, тема действительно закрепляется.