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.

In computer science and queueing theory, LIFO (last in, first out) 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.

In computing, LIFO as a term 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. 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 removed.[2] In computing, the abstract LIFO mechanism is used in real data structures implemented as stacks; sometimes, such data structures are called "push-down lists" and "piles".[3]

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, 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."[4]

The term FILO (first in, last out) can also be used for the same purpose, while LCFS (last come, first served) is sometimes used in queueing theory.

See also[edit]

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. ^ 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".