<programming> (See below for synonyms) A data structure for storing items
which are to be accessed in last-in first-out order.
The operations on a stack are to create a new stack, to "push" a new item onto
the top of a stack and to "pop" the top item off. Error conditions are raised by
attempts to pop an empty stack or to push an item onto a stack which has no room
for further items (because of its implementation).
Most processors include support for stacks in their instruction set
architectures. Perhaps the most common use of stacks is to store subroutine
arguments and return addresses. This is usually supported at the machine code
level either directly by "jump to subroutine" and "return from subroutine"
instructions or by auto-increment and auto-decrement addressing modes, or both.
These allow a contiguous area of memory to be set aside for use as a stack and
use either a special-purpose register or a general purpose register, chosen by
the user, as a stack pointer.
The use of a stack allows subroutines to be recursive since each call can have
its own calling context, represented by a stack frame or activation record.
There are many other uses. The programming language Forth uses a data stack in
place of variables when possible.
Although a stack may be considered an object by users, implementations of the
object and its access details differ. For example, a stack may be either
ascending (top of stack is at highest address) or descending. It may also be
"full" (the stack pointer points at the top of stack) or "empty" (the stack
pointer points just past the top of stack, where the next element would be
pushed). The full/empty terminology is used in the Acorn Risc Machine and
In a list-based or functional language, a stack might be implemented as a linked
list where a new stack is an empty list, push adds a new element to the head of
the list and pop splits the list into its head (the popped element) and tail
(the stack in its modified form).
At MIT, pdl used to be a more common synonym for stack, and this may still be
true. Knuth ("The Art of Computer Programming", second edition, vol. 1, p. 236)
Many people who realised the importance of stacks and queues
independently have given other names to these structures:
stacks have been called push-down lists, reversion storages,
cellars, dumps, nesting stores, piles, last-in first-out
("LIFO") lists, and even yo-yo lists!
STAB-11 « STAC « stac compression « stack »
Stack Environment Control Dump machine » stack frame
» stacking order