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.
The predicate isEmpty(S) may be defined with the following additional axioms.
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.
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.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 23 May 2011.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "stack", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 23 May 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/stack.html