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 Fri Dec 17 12:27:51 2004.
HTML page formatted Wed Oct 26 09:47:18 2005.

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