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 Black.

Entry modified 22 August 2013.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "cactus stack", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 22 August 2013. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/cactusstack.html