LIFO (англ. last in, first out, «последним пришёл — первым ушёл») — способ организации и манипулирования данными относительно времени и приоритетов. В структурированном линейном списке, организованном по принципу LIFO, элементы могут добавляться и выбираться только с одного конца, называемого «вершиной списка».[1] Структура LIFO может быть проиллюстрирована на примере стопки тарелок: чтобы взять вторую сверху, нужно снять верхнюю, а чтобы снять последнюю, нужно снять все лежащие выше.
Определение
правитьТермин относится к абстрактным принципам обработки списков и временного хранения данных, в частности, когда нужно иметь доступ к ограниченному набору данных в определённом порядке. Принцип LIFO применяется в тех случаях, когда последние данные, добавленные в структуру, должны быть первыми удалены или обработаны. Полезная аналогия с офисным работником: человек может работать только с одной страницей в каждый момент времени, поэтому очередной документ добавляется в папку сверху к стопке предыдущих. По аналогии с этим в компьютере тоже есть ограничения, такие как ширина шины данных и тот факт, что в каждый момент времени система может манипулировать только с одной ячейкой памяти.[2] Абстрактный механизм LIFO, применяемый в вычислениях, реализуется в реальных структурах данных в виде стека, название которого совершенно очевидно имеет отношение к «пачке бумаги», «стопке тарелок» и т. п. (англ. stack переводится как «штабель, кипа, стопка»). В качестве синонима иногда используется термин FILO (англ. first in, last out — «первым пришёл, последним ушёл»), в котором акцентируется, что более ранние дополнения к списку должны ожидать, пока они не поднимутся в структуре на самый верх, после чего к ним будет получен доступ. В теории массового обслуживания иногда используется термин LCFS (last come, first served — «последним пришёл, первым обслужен»). Различие между обобщённым списком, массивом, очередью и стеком определяется правилами, используемыми в механизме доступа к данным.[2] В любом случае в структуре LIFO организован доступ в обратном порядке по сравнению с очередью. «Имеются определённые, часто встречающиеся ситуации в области компьютерных наук, когда нужно ограничить вставки и удаления в списки так, чтобы эти изменения могли происходить только в начале или в конце списка, но не в его середине. В таких случаях полезны две структуры данных: стеки (магазины) и очереди».[3]
В качестве синонима LIFO также используется термин «магазинный принцип» в котором проводится аналогия с оружейным магазином и патронами.[4]
Применение
правитьСтековые структуры в вычислительных системах относятся к числу фундаментальных и потому чрезвычайно важных. Можно сказать, что без способности к перестраиваемой организации данных, в том числе со ссылкой на исполняемый код, компьютеры не были бы таким гибким инструментом, каким они являются сегодня, а были бы просто дорогим калькулятором для специальных целей, подобно ЭНИАКу времён Второй мировой войны, имеющим ограниченные возможности и неширокую сферу применения.[5]
В упорядоченных структурах данных стек используется в качестве динамического элемента памяти, в котором абстрактное понятие — аппаратно зависимый стек вызовов — используется для хранения копии данных или их части, будь то адреса памяти элементов данных (см.: Параметр (программирование)#Передача параметра по ссылке) или копии данных (передача параметра по значению). Самой распространенной задачей обработки списков является сортировка (в лексикографическом порядке, по возрастанию значения, и т. д.), в которой действия машины ограничиваются сравнением всего двух элементов, тогда как список чаще всего содержит миллионы членов. Существуют различные стратегии (компьютерные алгоритмы), оптимальные для разных типов сортируемых данных, но при реализации все они прибегают к применению программ или подпрограмм, которые обычно вызывают сами себя или часть своего кода рекурсивно, и при каждом вызове добавляют в стек вызовов частично упорядоченный список элементов. Именно по этой причине в курсах структур данных стеки и рекурсии обычно вводятся параллельно, потому что они тесно взаимосвязаны.[6]
Именно благодаря гибкости доступа к стеку вызовов с возможностью перегруппировки данных (организованный по абстрактному методу LIFO блок данных как будто специально придуман только для того, чтобы данные можно было легко переупорядочить) подпрограммы и стандартные функции получают требуемые данные, выполняют те свои задачи, для решения которых они оптимизированы, и передают информацию обратно в вызывающий сегмент программы.[7] Стек вызовов в конкретных случаях включает в себя адрес следующей инструкции вызывающей программы, которая обычно выполняет какие-то действия с «откликами», полученными от подпрограмм и стандартных функций. В рекурсивных вызовах эти действия обычно включают сравнение следующего элемента списка с возвратившимся «откликом» (например, выбор из двух значений наибольшей величины), пока список не будет исчерпан.
Следовательно, в реальном мире реализаций абстрактного принципа LIFO количество стеков вызовов меняется чрезвычайно часто, размер каждого зависит от числа требуемых элементов данных, которыми необходимо манипулировать. Поэтому уместно сравнить LIFO с кипой буклетов и брошюр, а не со стопкой тонких листов бумаги.
См. также
правитьПримечания
править- ↑ Seymour Lipschutz. Schaum’s Outline of 'Theory and Problems of Data Structures. — 1st (pb). — McGRAW-HILL BOOK Company, 1986. — ISBN 0-07-038001-5.
- ↑ 1 2 Robert L. Kruse. Data Structures & Program Design. — 2nd (hc) textbook. — New Jersey: Prentice-Hall, 1987. — ISBN 0-13-195884-4.
- ↑ «A queue is a linear list in which items may be added only at one end and items may be removed only at the other end» // Lipschutz, pp. 164—165
- ↑ Методические указания для самостоятельной работы студентов по дисциплине «Теория вычислительных процессов и структур». Ч.1/ Ижевск, мех. ин-т; Сост. М. А. Сенилов. Ижевск, 1992. 13 с. // http://diplomforum.ru/f122/t43269.html Архивная копия от 10 июня 2015 на Wayback Machine
- ↑ Lipschutz, pp. 164, Essence of the matter, illustration of his meaning.
- ↑ Both Kruse and Lipsutz, Implicit in context—both discuss at length with coverage of stacks.
- ↑ Lipschutz, pp. 164