Главная » Java, Структуры данных и алгоритмы » Стеки

0

Стек представляет собой объект, работа с которым — добавление и удаление — осуществляется по принципу LIFO {last-in first-out — последним пришел — первым ушел). Добавление объектов в стек может осуществляться в любой момент, удаляется же лишь объект, добавленный последним. Название «стек» происходит от английского названия загруженной в специальный распределитель стопки тарелок, используемой в кафетериях. В данном случае основными операциями являются «вдавливание» и «выталкивание» тарелок из стопки. Когда нужна новая тарелка из распределителя, ее «выталкивают» из стопки, а при добавлении в стопку еще одной тарелки ее «вдавливают» в стопку, и она становится верхней в стопке. Кроме того, можно сравнить стеки с упаковкой конфет PEZ®, которая состоит из содержащего мятные леденцы контейнера с пружинкой. При открытии крыШки этого контейнера «выскакивает» верхний леденец (см. рис. 4.1). относятся к базовым структурам данных, используемым во многих приложениях.

Рис. 4.1. Схема устройства упаковки конфет PEZ®, которая является физической реализацией абстрактного типа данных «стек» (PEZ® — зарегистрированная торговая марка компании PEZ Candy, Inc.)

Пример 4.1. В интернет-браузерах адреса посещаемых сайтов хранятся в виде стеков. При открытии пользователем нового Web-сайта его адрес добавляется, «вдавливается» в стек адресов. После этого пользователь может вернуться к открытым ранее сайтам с помощью кнопки «Назад».

Пример 4.2. В большинстве текстовых редакторов существует механизм отмены действий «Undo», с помощью которого можно отменить последние операции редактирования и вернуться к предыдущему виду документа. Такой механизм отмены действий реализуется благодаря хранению проводимых изменений в виде стека.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии