Просмотр кода страницы LIFO

{{другие значения|FIFO и LIFO|FIFO и LIFO}}
[[Файл:Stack.png|thumb|230px|Самый верхний элемент [[стек]]а, который добавлен последним, извлекается самым первым. Поэтому такой стек является структурой типа LIFO]]
'''LIFO''' ({{Lang-en|last in, first out}}, «последним пришёл — первым ушёл») — способ организации и манипулирования данными относительно времени и приоритетов. В структурированном линейном списке, организованном по принципу LIFO, элементы могут добавляться и выбираться только с одного конца, называемого «вершиной списка».<ref>{{книга|заглавие=Schaum’s Outline of 'Theory and Problems of Data Structures|автор=Seymour Lipschutz.|год=1986|издание=1st (pb)|isbn=0-07-038001-5|издательство=McGRAW-HILL BOOK Company}}</ref> Структура LIFO может быть проиллюстрирована на примере стопки тарелок: чтобы взять вторую сверху, нужно снять верхнюю, а чтобы снять последнюю, нужно снять все лежащие выше.

== Определение ==
Термин относится к абстрактным принципам обработки списков и временного хранения данных, в частности, когда нужно иметь доступ к ограниченному набору данных в определённом порядке. Принцип LIFO применяется в тех случаях, когда последние данные, добавленные в структуру, должны быть первыми удалены или обработаны. Полезная [[аналогия]] с офисным работником: человек может работать только с одной страницей в каждый момент времени, поэтому очередной документ добавляется в папку сверху к стопке предыдущих. По аналогии с этим в компьютере тоже есть ограничения, такие как ширина шины данных и тот факт, что в каждый момент времени система может манипулировать только с одной ячейкой памяти.<ref name="Kruse">{{книга|автор=Robert L. Kruse|заглавие=Data Structures & Program Design|ссылка=https://archive.org/details/datastructurespr0000krus_n1p0|издание=2nd (hc) textbook|год=1987|издательство=Prentice-Hall|место=New Jersey|isbn=0-13-195884-4|page=[https://archive.org/details/datastructurespr0000krus_n1p0/page/150 150]}}</ref> Абстрактный механизм LIFO, применяемый в вычислениях, реализуется в реальных [[Структура данных|структурах данных]] в виде [[стек]]а, название которого совершенно очевидно имеет отношение к «пачке бумаги», «стопке тарелок» и т. п. ({{lang-en|stack}} переводится как «штабель, кипа, стопка»). В качестве синонима иногда используется термин FILO ({{Lang-en|first in, last out}} — «первым пришёл, последним ушёл»), в котором акцентируется, что более ранние дополнения к списку должны ожидать, пока они не поднимутся в структуре на самый верх, после чего к ним будет получен доступ. В [[Теория массового обслуживания|теории массового обслуживания]] иногда используется термин LCFS (last come, first served — «последним пришёл, первым обслужен»). Различие между обобщённым списком, массивом, очередью и стеком определяется правилами, используемыми в механизме доступа к данным.<ref name="Kruse"/> В любом случае в структуре LIFO организован доступ в обратном порядке по сравнению с [[Очередь (программирование)|очередью]]. «Имеются определённые, часто встречающиеся ситуации в области компьютерных наук, когда нужно ограничить вставки и удаления в списки так, чтобы эти изменения могли происходить только в начале или в конце списка, но не в его середине. В таких случаях полезны две структуры данных: ''стеки'' (магазины) и ''очереди''».<ref>«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</ref>

В качестве синонима LIFO также используется термин «магазинный принцип» в котором проводится аналогия с оружейным магазином и патронами.<ref>Методические указания для самостоятельной работы студентов по дисциплине «Теория вычислительных процессов и структур». Ч.1/ Ижевск, мех. ин-т; Сост. М. А. Сенилов. Ижевск, 1992. 13 с. // http://diplomforum.ru/f122/t43269.html {{Wayback|url=http://diplomforum.ru/f122/t43269.html |date=20150610232029 }}</ref>

== Применение ==
Стековые структуры в вычислительных системах относятся к числу фундаментальных и потому чрезвычайно важных. Можно сказать, что без способности к перестраиваемой организации данных, в том числе со ссылкой на [[Машинный код|исполняемый код]], компьютеры не были бы таким гибким инструментом, каким они являются сегодня, а были бы просто дорогим калькулятором для специальных целей, подобно [[ЭНИАК]]у времён [[Вторая мировая война|Второй мировой войны]], имеющим ограниченные возможности и неширокую сферу применения.<ref>Lipschutz, pp. 164, Essence of the matter, illustration of his meaning.</ref>

В упорядоченных структурах данных стек используется в качестве динамического элемента памяти, в котором абстрактное понятие — аппаратно зависимый [[стек вызовов]] — используется для хранения копии данных или их части, будь то адреса памяти элементов данных (см.: [[Параметр (программирование)#Передача параметра по ссылке]]) или копии данных (передача параметра по значению). Самой распространенной задачей обработки списков является сортировка (в [[Лексикографический порядок|лексикографическом порядке]], по возрастанию значения, и т. д.), в которой действия машины ограничиваются сравнением всего двух элементов, тогда как список чаще всего содержит миллионы членов. Существуют различные стратегии (компьютерные [[алгоритм]]ы), оптимальные для разных типов сортируемых данных, но при реализации все они прибегают к применению программ или [[Подпрограмма|подпрограмм]], которые обычно вызывают сами себя или часть своего кода [[Рекурсия|рекурсивно]], и при каждом вызове добавляют в стек вызовов частично упорядоченный список элементов. Именно по этой причине в курсах структур данных стеки и рекурсии обычно вводятся параллельно, потому что они тесно взаимосвязаны.<ref>Both Kruse and Lipsutz, Implicit in context—both discuss at length with coverage of stacks.</ref>

Именно благодаря гибкости доступа к стеку вызовов с возможностью перегруппировки данных (организованный по абстрактному методу LIFO блок данных как будто специально придуман только для того, чтобы данные можно было легко переупорядочить) подпрограммы и стандартные функции получают требуемые данные, выполняют те свои задачи, для решения которых они оптимизированы, и передают информацию обратно в вызывающий сегмент программы.<ref>Lipschutz, pp. 164</ref> Стек вызовов в конкретных случаях включает в себя адрес следующей инструкции вызывающей программы, которая обычно выполняет какие-то действия с «откликами», полученными от подпрограмм и стандартных функций. В рекурсивных вызовах эти действия обычно включают сравнение следующего элемента списка с возвратившимся «откликом» (например, выбор из двух значений наибольшей величины), пока список не будет исчерпан.

Следовательно, в реальном мире реализаций абстрактного принципа LIFO количество стеков вызовов меняется чрезвычайно часто, размер каждого зависит от числа требуемых элементов данных, которыми необходимо манипулировать. Поэтому уместно сравнить LIFO с кипой буклетов и брошюр, а не со стопкой тонких листов бумаги.

== См. также ==
* [[Поиск в глубину]]
* [[FIFO]]

== Примечания ==
{{примечания}}

[[Категория:Кибернетика]]
[[Категория:Межпроцессное взаимодействие]]