LIFO (computing)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
In a stack, the topmost item, which is added last, is taken out first. Hence a stack is a LIFO structure.

LIFO is an acronym that 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 be added or taken off from only one end, called the "top".[1] A LIFO structure can be illustrated with the example of a stack of trays. The last tray to be placed on top is also the first to be taken off the top.

Definition[edit]

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.[2] 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"[3] The term FILO ("first in, last out") can be used synonymously, as the term emphasizes that early additions to the list need to wait until they rise to the LIFO structure "top" to be accessed. The term LCFS ("last come, first served") is sometimes used in queueing theory. The difference between a generalized list, an array, queue, or stack, is defined by the rules enforced and used to access the mechanism.[2] In any event, an 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."[4]

Use[edit]

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.[3]

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 interdependent.[5]

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.[3] 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[edit]

Notes and references[edit]

  1. ^ Lipschutz, Seymour (1986). Schaum's Outline of 'Theory and Problems of Data Structures' (1st (pb) ed.). McGRAW-HILL BOOK Company. pp. 7, 164–165. ISBN 0-07-038001-5. "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'" 
  2. ^ a b Kruse, Robert L. (1987) [1984]. Data Structures & Program Design. Joan L. Stone, Kenny Beck, Ed O'Dougherty (production process staff workers) (second (hc) textbook ed.). New Jersey: Prentice-Hall, Inc. div. of Simon & Schuster. p. 150. ISBN 0-13-195884-4. "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." 
  3. ^ a b c Lipshutz, p. 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."
  4. ^ 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".
  5. ^ Both Kruse and Lipsutz, Implicit in context—both discuss at length with coverage of stacks.