LIFO

LIFO is an acronym which stands for last in, first out. In computer science and queueing theory this refers to the way items stored in some types of data structures are processed. By definition, in a LIFO structured linear list, elements can only be added or taken off from only one end, called the "top". [cite book
title=Schaum's Outline of 'Theory and Problems of Data Structures'
quote=A stack, also called a last-in, first-out (LIFO) system, is a linear list in which insertions and deletions can take place at only one end, called the 'top'|pages= p.7, 164-165 (of 344)|authorlink= |last=Seymour, Ph.D.|first=Seymour, Professor of Mathematics, Temple University
date=1986|edition=1st (pb)|isbn= ISBN 0-07-038001-5
publisher= McGRAW-HILL BOOK Company|location=various, New York, St. Louis, Sanfrancisco, ..., Tokyo, Toronto et al.|] A LIFO structure can be illustrated with the example of a narrow, crowded elevator with a small door. When the elevator reaches its destination, the last people to get on "have to be" the first to get off.

Definition

The term in computing generally refers to the abstract principles of list processing and temporary storage, particularly when there is a need to access the data in limited amounts, and in a certain order. LIFO is most used in cases where the last data added to the structure must be the first data to be removed or evaluated. A useful analogy is of the office worker: a person can only handle one page at a time, so the top piece of paper added to a pile is the first off; parallel to limitations such as data bus width and the fact that one can only manipulate a single binary data address in a computer at a time.cite book
last=Kruse|First=Robert L.|title=Data Structures & Program Design (second edition)|edition=second (hc) textbook
origdate=1984|date=1987|others=Joan L. Stone, Kenny Beck, Ed O'Dougherty (production process staff workers)
publisher=Prentice-Hall, Inc. div. of Simon & Schuster|location=Englewood Cliffs, New Jersey 07632
isbn= ISBN 0-13-195884-4|quote="The definition of a finite sequence immediately makes it possible for us to attempt a definition of a list: A 'list' of terms of type T is simply a finite sequence of elements of the set T. ... The only difference among stacks and queues and more general lists is the operations by which changes or accesses can be made to the list."|pages= p. 150|] The abstract LIFO mechanism, when applied to computing inevitably devolves to the real data structures implemented as stacks whose eponymous relation to the "stack of paper", "stack of plates" should be obvious. Other names for the device are "Push down list" and "piles"Lipshutz, pp. 164, "Other names for stacks are "piles" and "push-down lists." Although the stack may seem to be a very restricted type of data structure, it has many important applications in computer science."] The term FILO ("first in, last out") can be used synonymously, as the term emphasizes that early additions list need to wait until they rise to the LIFO structure "top" to be accessed. The difference between a generalized list, an array, queue, or stack, is defined by the rules enforced and used to access the mechanism.Ibid] In any event, a LIFO structure is accessed in opposite order to a queue: "There are certain frequent situations in computer science when one wants to restrict insertions and deletions so that they can only take place at the beginning or end of the list, not in the middle. Two of the data structures useful in such situations are "stacks" and "queues"." Lipshutz, pp. 164-165, "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".]

Use

Stack structures in computing are extremely fundamental and important. It is fair to say that without the ability to organize data by order rearrangement, including links to executable code, computers would not be the flexible tools they are today, and exist solely as expensive special purpose calculators like the ENIAC of World War II having limited abilities and scope of application.Lipshutz, pp. 164, Essence of the matter, illustration of his meaning.]

In such data orderings, the stack is used as a dynamic memory element wherein an abstract concept—a machine dependent Stack frame is used to contain copies of data records or parts thereof—be they actual memory addresses of a data element (See parameters pass-by-reference), or a copy of the data (pass-by-value). In list processing, the most common need is sorting (alphabetically, greatest to smallest, etcetera.) where the machine is limited to comparing only two elements at a time, out of a list that likely holds millions of members. Various strategies (computer algorithms) exist which optimize particular types of data sorting, but in implementation all will resort to a sub-program and or sub-routines that generally call themselves or a part of their code recursively in each call adding to the list temporarily reordered in stack frames. It is for this reason, stacks and recursion are usually introduced in parallel in data structures courses—they are mutually interdependent. [Both Kruse and Lipsutz, Implicit in context—both discuss at length with coverage of stacks.]

It is through the flexibility of this access to data by stack-frames with their data re-groupings (in abstract a LIFO organized block of data which seems only to allow data some improvement on ordering flexibility) that sub-programs and sub-routines receive their input, do the task they are optimized to perform, and pass information back to the program segment currently in charge.Lipshutz, pp. 164, Ibid— by extension] The stack frame in actual cases includes the address of the next instruction of the calling program segment, which ordinarily then does something with the data "answer" processed by the subroutines or subprogram. In a recursive call, this is generally an instruction to check the next list element versus the returned "answer" (e.g. largest of the last two compared), until the list is exhausted.

Consequently, in real world implementations of the LIFO abstraction, the number of stack frames varies extremely often, each sized by the needs of the data elements that need manipulated. This can be likened to a LIFO pile of booklets or brochures, rather than a thin sheet of paper.

See also

* LIFO is also a term used in accounting, for example in determining the cost basis for inventory, and cost of goods sold. See FIFO and LIFO accounting.
* Depth-first search
* FIFO (First in, first out)
* Stack data structure

Notes and references