A spaghetti stack is in fact an N-ary tree data structure in which child nodes have pointers to the parent nodes. When a list of nodes is traversed from a leaf node to the root node by chasing these parent pointers, the structure looks like a linked list stack. You can just pretend that the one and only parent pointer is called "next" or "link", and ignore that the parents have other children, which are not accessible anyway since there are no downward pointers. In computer science, a tree is a widely-used computer data structure that emulates a tree structure with a set of linked nodes. ... A child node or descendant node is a node in a tree data structure that is linked to by a parent node. ... A parent node (or ancestor node) is a node in a tree data structure that links to one or more child nodes. ... A root node is a specially chosen node in a tree data structure at which all operations on the tree begin. ... In computer science, a pointer is a programming language datatype whose value is used to refer to (points to) another value stored elsewhere in the computer memory. ... In computer science, a linked list is one of the fundamental data structures used in computer programming. ... A stack is a data structure that works on the principle of Last In First Out (LIFO). ...

Spaghetti stack structures arise in situations when records are dynamically pushed and popped onto a stack as execution progresses, but references to the popped popped records remain in use.

For example, a compiler for a language such as C creates a spaghetti stack as it opens and closes symbol tables representing block scopes. When a new block scope is opened, a symbol table is pushed onto a stack. When the closing curling brace is encounterd, the scope is closed and the symbol table is popped. But that symbol table is remembered, rather than destroyed. And of course it remembers it higher level "parent" symbol table and so on. Thus when the compiler is later performing translations over the abstract syntax tree, for any given expression, it can fetch the symbol table representing that expression's environment and can resolve references to identifiers. If the expression refers to a variable X, it's first sought after in the leaf symbol table representing the inner-most lexical scope, then in the parent and so on. The C Programming Language, Brian Kernighan and Dennis Ritchie, the original edition that served for many years as an informal specification of the language The C programming language is a standardized programming language developed in the early 1970s by Ken Thompson and Dennis Ritchie for use on the UNIX operating...

The term spaghetti stack is closely associated with implementations of programming languages that support continuations. Spaghetti stacks are used to implement the actual run-time stack containing variable bindings and other environmental features. When continuations must be supported, a function's local variables cannot be destroyed when that function returns: a saved continuation may later re-enter into that function, and will expect not only the variables there to be intact, but it will also expect the entire stack to be there, so it can return again! Thus stack frames are dynamically allocated, and simply left behind to be garbage collected when no continuations refer to them any longer. This type of structure solves the upward and downward funarg problem, so first-class lexical closures are readily implemented in that substrate also. Funarg is an abbreviation for functional argument; in computer science, the funarg problem relates to the difficulty of implementing functions as first-class citizen objects in stack-based programming language implementations. ... In programming languages, a closure is an abstraction representing a function, plus the lexical environment (see static scoping) in which the function was created, and its application to arguments. ...