Материал: 7 - Презентация - Дженерики, Абстрактные типы данных, Стек, Очередь
Центрдистанционногообучения
Что такое Стек?
11
online.mirea.ru
Центрдистанционногообучения
Структура данных Стек
Стеком ( в переводе с английского – stack – стопка; stack — стопка; читается как стэк) называется линейная динамическая структура данных, добавление и исключение элементов в которую и производится с одного конца, называемого вершиной стека.
Стек работает по принципу LIFO (Last-In, First-Out) -
"поступивший последним, обслуживается первым».
.
Магазин пистолета, очередь в кассу, лоток принтера с бумагой, игра
“Ханойские башни” — простые примеры стека.
online.mirea.ru
Центрдистанционногообучения
Примеры Стека
Примеры применения стека — любая рекурсивная задача (“так, старую итерацию пока отложу в стопку, а сейчас надо обрабатывать новую итерацию!“), например, перебор маршрутов исследовательского робота в пещере неизвестной конфигурации..
Самые первые калькуляторы были напрямую сделаны как стеки. Вместо “2+2” нужно было вводить “2 2 +”. Первые два элемента (“операнды”) клались в стек, пока не будет введён плюс (“оператор
online.mirea.ru
Центрдистанционногообучения
Операции над Стеком
Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.
Основными операциями над стеками являются:
•добавление элемента - push(
•удаление элемента - pop()
Центрдистанционногообучения
Абстрактные типы данных (АТД) или структуры данных
•Абстрактный тип данных (ADT) является абстракцией структуры данных
•АТД определяет:
•Хранение данных
•Операции выполняемые над данными
•Условия возникновения ошибок, связанных с выполнением операций
•Пример: AТД для моделирования фондовой биржи
•Данные это заказы на покупку / продажу
•Поддерживаются операции
•Заказ на покупку(акций)
•Заказ на продажу(акций)
•Отмена заказа(заказ)
•Условия возникновения ошибок:
•Купить / продать несуществующие акции
•Отменить несуществующий заказ
15 online.mirea.ru