Стек, очередь, дек | Что такое стек? (11 кл. 136 ч.)

Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, полный углублённый курс, по 4 часа в неделю)


Уроки 74 - 76
Стек, очередь, дек
(§42. Стек, очередь, дек)



Содержание урока

Что такое стек?

Использование динамического массива

Вычисление арифметических выражений

Скобочные выражения

Очереди, деки

Вопросы и задания

Задачи


Что такое стек?


Представьте себе стопку книг (подносов, кирпичей и т. п.). С точки зрения информатики, её можно воспринимать как список элементов, расположенных в определённом порядке. Этот список имеет одну особенность — удалять и добавлять элементы можно только с одной («верхней») стороны. Действительно, для того чтобы вытащить какую-то книгу из стопки, нужно сначала снять все те книги, которые находятся на ней. Положить книгу сразу в середину тоже нельзя.

Стек (англ. stack — стопка) — это линейный список, в котором элементы добавляются и удаляются только с одного конца (англ. LIFO: Last In - First Out — последний пришёл — первым ушёл).

На рисунке 6.6 показаны примеры стеков вокруг нас, в том числе автоматный магазин и детская пирамидка.

Рис. 6.6

Рис. 6.6

Как вы знаете из учебника для 10 класса, стек используется при выполнении программ: в нём хранятся адреса возврата из подпрограмм, параметры, передаваемые функциям и процедурам, а также локальные переменные.

Задача 1. В файле записаны целые числа. Нужно вывести их в другой файл в обратном порядке.

В этой задаче очень удобно использовать стек.

Для стека определены две операции:

• добавить элемент на вершину стека (англ. push — втолкнуть);
• получить элемент с вершины стека и удалить его из стека (англ. pop — вытолкнуть).

Запишем алгоритм решения на псевдокоде. Сначала читаем данные и добавляем их в стек:

нц пока файл не пуст 
прочитать х 
добавить х в стек
кц

Теперь верхний элемент стека — это последнее число, прочитанное из файла. Поэтому остаётся «вытолкнуть» все записанные в стек числа, они будут выходить в обратном порядке:

нц пока стек не пуст 
вытолкнуть число из стека в х 
записать х в файл
кц


Следующая страница Использование динамического массива



Cкачать материалы урока







Наверх