stack

(data structure)

Definition: A collection of items in which only the most recently added item may be removed. The latest added item is at the top. Basic operations are push and pop. Often top and isEmpty are available, too. Also known as "last-in, first-out" or LIFO.

Formal Definition: The operations new(), push(v, S), top(S), and popoff(S) may be defined with axiomatic semantics as follows.

new() returns a stack
popoff(push(v, S)) = S
top(push(v, S)) = v

where S is a stack and v is a value. The pop operation is a combination of top, to return the top value, and popoff, to remove the top value.

The predicate isEmpty(S) may be defined with the following additional axioms.

isEmpty(new()) = true
isEmpty(push(v, S)) = false

Also known as LIFO.

Generalization (I am a kind of ...)
abstract data type.

Specialization (... is a kind of me.)
bounded stack, cactus stack.

See also queue.

Note: Other operations may include index(i, S), return the ith item in the stack, isFull(S), and rotate(i, S), move i items from top to bottom or vice versa.

Author: PEB

Implementation

(Scheme)

More information

examples and code. Demonstration with dynamic array and linked list implementations.

Origin is attributed to A. W. Burks, D. W. Warren, and J. B. Wright, An analysis of a logical machine using parenthesis-free notation, Mathematical Tables and Other Aids to Computation, 8(46):53-57, April 1954, and A. Newell and J. C. Shaw, Programming the logic theory machine, Proceedings of the 1957 Western Joint Computer Conference, pages 230-240, Institute of Radio Engineers, New York, February 1957.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified Fri Dec 30 15:14:45 2005.
HTML page formatted Fri Dec 30 15:36:26 2005.

Cite this as:
Paul E. Black, "stack", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.
http://www.nist.gov/dads/HTML/stack.html