cactus stack

(data structure)

Definition: A variant of stack in which one other cactus stack may be attached to the top. An attached stack is called a "branch." When a branch becomes empty, it is removed. Pop is not allowed if there is a branch. A branch is only accessible through the original reference; it is not accessible through the stack.

Formal Definition: The operations new to this variant of stack, branch(S, T) and notch(v), may be defined with axiomatic semantics as follows.

1. top(branch(S, T)) = top(S)
2. notch(new()) = false
3. notch(push(v, S)) = false
4. notch(branch(S, T)) = true

Also known as saguaro stack.

Generalization (I am a kind of ...)
stack, tree.

Note: A saguaro is a kind of branching cactus.

Author: PEB

More information

Pictures and a description of saguaro cactus.

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

Entry modified 17 December 2004.
HTML page formatted Tue Dec 6 16:16:32 2011.

Cite this as:
Paul E. Black, "cactus stack", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/cactusstack.html