Уроки 74 - 76
Стек, очередь, дек
(§42. Стек, очередь, дек)
Содержание урока
Что такое стек?
Использование динамического массива
Вычисление арифметических выражений
Что такое стек?
Представьте себе стопку книг (подносов, кирпичей и т. п.). С точки зрения информатики, её можно воспринимать как список элементов, расположенных в определённом порядке. Этот список имеет одну особенность — удалять и добавлять элементы можно только с одной («верхней») стороны. Действительно, для того чтобы вытащить какую-то книгу из стопки, нужно сначала снять все те книги, которые находятся на ней. Положить книгу сразу в середину тоже нельзя.
Стек (англ. stack — стопка) — это линейный список, в котором элементы добавляются и удаляются только с одного конца (англ. LIFO: Last In - First Out — последний пришёл — первым ушёл).
На рисунке 6.6 показаны примеры стеков вокруг нас, в том числе автоматный магазин и детская пирамидка.
Рис. 6.6
Как вы знаете из учебника для 10 класса, стек используется при выполнении программ: в нём хранятся адреса возврата из подпрограмм, параметры, передаваемые функциям и процедурам, а также локальные переменные.
Задача 1. В файле записаны целые числа. Нужно вывести их в другой файл в обратном порядке.
В этой задаче очень удобно использовать стек.
Для стека определены две операции:
• добавить элемент на вершину стека (англ. push — втолкнуть);
• получить элемент с вершины стека и удалить его из стека (англ. pop — вытолкнуть).
Запишем алгоритм решения на псевдокоде. Сначала читаем данные и добавляем их в стек:
нц пока файл не пуст прочитать х добавить х в стек кц
Теперь верхний элемент стека — это последнее число, прочитанное из файла. Поэтому остаётся «вытолкнуть» все записанные в стек числа, они будут выходить в обратном порядке:
нц пока стек не пуст вытолкнуть число из стека в х записать х в файл кц
Следующая страница 
Использование динамического массива
Cкачать материалы урока
