Интернет магазин китайских планшетных компьютеров



Компьютеры - LIFO (информатика)

24 февраля 2011


Оглавление:
1. LIFO (информатика)
2. Применение



Самый верхний элемент стека, который добавлен последним, извлекается самым первым. Поэтому такой стек является структурой типа LIFO.

LIFO — акроним Last In, First Out, абстрактное понятие в способах организации и манипулирования данными относительно времени и приоритетов. В структурированном линейном списке, организованном по принципу LIFO, элементы могут добавляться и выбираться только с одного конца, называемого «вершиной списка». Структура LIFO может быть проиллюстрирована на примере стопки тарелок: чтобы взять вторую сверху, нужно снять верхнюю, а чтобы снять последнюю, нужно снять все лежащие выше.

Определение

Термин относится к абстрактным принципам обработки списков и временного хранения данных, в частности, когда нужно иметь доступ к ограниченному набору данных в определённом порядке. Принцип LIFO применяется в тех случаях, когда последние данные, добавленные в структуру, должны быть первыми удалены или обработаны. Полезная аналогия с офисным работником: человек может работать только с одной страницей в каждый момент времени, поэтому очередной документ добавляется в папку сверху к стопке предыдущих. По аналогии с этим в компьютере тоже есть ограничения, такие как ширина шины данных и тот факт, что в каждый момент времени система может манипулировать только с одной ячейкой памяти. Абстрактный механизм LIFO, применяемый в вычислениях, реализуется в реальных структурах данных в виде стека, название кототого совершенно очевидно имеет отношение к «пачке бумаги», «стопке тарелок» и т. п.. В качестве синонима иногда используется термин FILO, в котором акцентируется, что более ранние дополнения к списку должны ожидать, пока они не поднимутся в структуре на самый верх, после чего к ним будет получен доступ. В теории массового обслуживания иногда используется термин LCFS. Различие между обобщённым списком, массивом, очередью и стеком определяется правилами, используемыми в механизме доступа к данным. В любом случае в структуре LIFO организован доступ в обратном порядке по сравнению с очередью. «Имеются определённые, часто встречающиеся ситуации в области компьютерных наук, когда нужно ограничить вставки и удаления в списки так, чтобы эти изменения могли происходить только в начале или в конце списка, но не в его середине. В таких случаях полезны две структуры данных: стеки и очереди».



Просмотров: 1349


<<< FIFO (информатика)
Mmap >>>