LIFO¶

LIFO (от англ. Last In, First Out — «последним пришёл — первым ушёл») — это способ организации и обработки данных, при котором элемент, добавленный в структуру последним, извлекается из неё первым. LIFO является одним из фундаментальных принципов работы со структурами данных, в первую очередь со стеком. Данный метод противоположен принципу FIFO (First In, First Out — «первым пришёл — первым ушёл»), используемому в очередях.

¶История и происхождение

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

В бухгалтерском учёте (accounting) термин LIFO имеет самостоятельное значение, не связанное с информатикой: это метод оценки материально-производственных запасов, при котором в себестоимость реализованной продукции сперва списываются последние по времени приобретения партии товаров. Данный метод широко применялся в США и некоторых других странах для целей налогового учёта, однако в России метод LIFO был отменён с 1 января 2008 года.

¶Реализация в программировании

¶Основная структура данных — стек

Основной структурой данных, реализующей принцип LIFO, является стек (stack). Стек представляет собой линейный список, в котором все добавления (операция push) и удаления (операция pop) элементов производятся только с одного конца, называемого вершиной стека. Операция чтения элемента без его удаления (операция peek или top) также выполняется с вершины.

¶Операции со стеком

1. Push (добавление в стек): Элемент помещается на вершину стека. Все предыдущие элементы сдвигаются вниз относительно нового.
2. Pop (извлечение из стека): Элемент с вершины стека изымается. После этого вершиной становится следующий под ним элемент.
3. Peek / Top (чтение вершины): Позволяет получить значение элемента, находящегося на вершине, не изменяя содержимого стека.
4. IsEmpty (проверка пустоты): Определяет, содержит ли стек какие-либо элементы.
5. Size (получение размера): Возвращает количество элементов в стеке.

¶Пример работы

Предположим, в стек последовательно добавляются числа: 1, затем 2, затем 3.

• После push(1): стек [1]. Вершина — 1.
• После push(2): стек [1, 2]. Вершина — 2.
• После push(3): стек [1, 2, 3]. Вершина — 3.

При выполнении операций pop из стека будут извлекаться в обратном порядке:

• pop() — извлекается 3. Стек: [1, 2].
• pop() — извлекается 2. Стек: [1].
• pop() — извлекается 1. Стек: [].

¶Применение принципа LIFO

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

¶Системное программирование и архитектура ЭВМ

• Стек вызовов (call stack): При вызове функции (или подпрограммы) адрес возврата и локальные переменные сохраняются в стеке. При завершении функции данные извлекаются, и управление возвращается в вызвавшую программу. Это основа для реализации вложенных и рекурсивных вызовов.
• Аппаратный стек: Большинство процессоров (особенно архитектуры x86 и ARM) имеют встроенный аппаратный стек, используемый для хранения адресов возврата, флагов и параметров при обработке прерываний и исключений.

¶Теория алгоритмов и структуры данных

• Обратная польская запись: LIFO используется для преобразования математических выражений из инфиксной формы (стандартная запись) в постфиксную (обратная польская запись), а также для их вычисления.
• Обход деревьев и графов: Алгоритмы поиска в глубину (DFS) реализуются с использованием стека LIFO.
• Алгоритм «лабиринт» и рекурсия: Стек явно или неявно используется при решении задач с возвратом (backtracking), таких как поиск выхода из лабиринта или задача о восьми ферзях.

¶Прикладное программирование

• Синтаксический анализ: Компиляторы и интерпретаторы используют стек для проверки синтаксиса, обработки вложенных конструкций (скобок, блоков кода) и построения дерева разбора.
• Отмена операций (Undo/Redo): Во многих редакторах и графических программах история операций организована как стек. Последнее выполненное действие может быть отменено (извлечено из стека), а отменённое действие может быть повторено (помещено обратно в стек при использовании второго стека для Redo).
• Обработка событий в графических интерфейсах: Стек используется для управления модальными окнами и диалогами, где последнее вызванное окно должно быть закрыто первым.

¶Бухгалтерский учёт (отдельная область)

В бухгалтерии метод LIFO применяется для оценки себестоимости товарно-материальных запасов в условиях инфляции. При использовании LIFO стоимость последних по времени поступления товаров списывается на себестоимость, что позволяет снизить налогооблагаемую прибыль в период роста цен, но приводит к занижению оценки остатков запасов в балансе. В Российской Федерации метод LIFO официально не применяется с 2008 года.

¶Критика и ограничения

Применение LIFO вне сферы компьютерных наук часто сопряжено с прагматическими проблемами. В бухгалтерском учёте этот метод критикуется за то, что он не отражает реального физического движения товаров (принцип FIFO чаще соответствует реальной логистике) и может искажать финансовые показатели компании, особенно в долгосрочной перспективе. В логистике и управлении складом LIFO используется реже, так как для большинства товаров (продукты питания, медикаменты) соблюдение срока годности требует реализации в порядке FIFO. В информатике ограничения LIFO связаны с последовательным доступом к элементам — для доступа к элементу, помещённому в стек раньше других, необходимо извлечь все элементы, помещённые после него.

¶Источники

1. Кнут, Д. Э. Искусство программирования. Том 1. Основные алгоритмы. — 3-е изд. — М.: Вильямс, 2016.
2. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2022.
3. Таненбаум, Э., Остин, Т. Архитектура компьютера. — 6-е изд. — СПб.: Питер, 2023.
4. Хорн, Г. К. Введение в бухгалтерский учёт. — 10-е изд. — М.: Юнити-Дана, 2019.