NIST

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.

  1. new() returns a stack
  2. popoff(push(v, S)) = S
  3. 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.

  1. isEmpty(new()) = true
  2. 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

Maksim Goleta's Collections (C#) implementing singly- and doubly-linked lists, binary search trees, and AVL trees. Bro. David Carlson's tutorial and code (C++). (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 23 April 2007.
HTML page formatted Mon Apr 23 09:23:15 2007.

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 April 2007. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/stack.html

to NIST home page