En informática , un árbol de punteros padre o in-tree es una estructura de datos de árbol N -ario en la que cada nodo tiene un puntero a su nodo padre , pero no punteros a nodos secundarios . Cuando se utiliza para implementar un conjunto de pilas , la estructura se denomina pila de espagueti , pila de cactus o pila de saguaro (en honor al saguaro , una especie de cactus). [1] Los árboles de punteros padre también se utilizan como estructuras de datos de conjuntos disjuntos .
La estructura puede considerarse como un conjunto de listas enlazadas simples que comparten parte de su estructura, en particular, sus colas. Desde cualquier nodo, se puede llegar a los ancestros del nodo, pero no a ningún otro nodo.
Un compilador para un lenguaje como C crea una pila de espaguetis a medida que abre y cierra tablas de símbolos que representan ámbitos de bloque . Cuando se abre un nuevo ámbito de bloque, se coloca una tabla de símbolos en una pila. Cuando se encuentra la llave de cierre, el ámbito se cierra y se extrae la tabla de símbolos. Pero esa tabla de símbolos se recuerda, en lugar de destruirse, y recuerda su tabla de símbolos "principal" de nivel superior, y así sucesivamente. Por lo tanto, cuando el compilador realiza posteriormente traducciones sobre el árbol de sintaxis abstracta , para cualquier expresión dada, puede obtener la tabla de símbolos que representa el entorno de esa expresión y puede resolver referencias a identificadores. Si la expresión hace referencia a una variable X, primero se busca en la tabla de símbolos de hoja que representa el ámbito léxico más interno, luego en el principal, y así sucesivamente.
El término pila de espagueti está estrechamente asociado con las implementaciones de lenguajes de programación que admiten continuaciones . Las pilas de espagueti se utilizan para implementar la pila de tiempo de ejecución real que contiene enlaces de variables y otras características del entorno. Cuando se deben admitir continuaciones, las variables locales de una función no se pueden destruir cuando esa función regresa: una continuación guardada puede volver a ingresar más tarde en esa función y esperará no solo que las variables allí estén intactas, sino que también esperará que la pila completa esté presente para que la función pueda regresar nuevamente. Para resolver este problema, los marcos de pila se pueden asignar dinámicamente en una estructura de pila de espagueti y simplemente dejarlos atrás para que se recolecten los elementos no utilizados cuando ya no haya continuaciones que hagan referencia a ellos. Este tipo de estructura también resuelve los problemas de funarg ascendente y descendente , como resultado, los cierres léxicos de primera clase se implementan fácilmente en ese sustrato.
Algunos ejemplos de lenguajes que utilizan pilas de espaguetis son:
Los ordenadores mainframe que utilizan la arquitectura Burroughs Large Systems y ejecutan el sistema operativo MCP pueden generar múltiples tareas dentro del mismo programa. Como originalmente eran sistemas basados en ALGOL, deben admitir funciones anidadas y el resultado es que la creación de tareas genera una bifurcación en la pila, que Burroughs describió informalmente como una "pila saguaro".