LIFO
Encyclopedia
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and queueing theory
Queueing theory
Queueing theory is the mathematical study of waiting lines, or queues. The theory enables mathematical analysis of several related processes, including arriving at the queue, waiting in the queue , and being served at the front of the queue...
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". 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
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 dataData
The term data refers to qualitative or quantitative attributes of a variable or set of variables. Data are typically the results of measurements and can be the basis of graphs, images, or observations of a set of variables. Data are often viewed as the lowest level of abstraction from which...
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. The abstract LIFO mechanism, when applied to computing inevitably devolves to the real data structures implemented as stack
Stack (data structure)
In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the stack,...
s 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" 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. 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."
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 ENIACENIAC
ENIAC was the first general-purpose electronic computer. It was a Turing-complete digital computer capable of being reprogrammed to solve a full range of computing problems....
of World War II
World War II
World War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...
having limited abilities and scope of application.
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.
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. 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
- Depth-first searchDepth-first searchDepth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....
- FIFO (computing) (First in, first out)
- Stack data structureStack (data structure)In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the stack,...