Pila (tipo de datos abstracto)

En informática , una pila es un tipo de datos abstracto que sirve como una colección de elementos con dos operaciones principales:

• Push , que agrega un elemento a la colección, y
• Pop , que elimina el elemento añadido más recientemente.

Además, una operación de peek puede, sin modificar la pila, devolver el valor del último elemento añadido. El nombre pila es una analogía de un conjunto de elementos físicos apilados uno sobre otro, como una pila de platos.

El orden en el que se agrega o elimina un elemento de una pila se describe como último en entrar, primero en salir , al que se hace referencia mediante el acrónimo LIFO . ^{[nb 1]} Al igual que con una pila de objetos físicos, esta estructura facilita la extracción de un elemento de la parte superior de la pila, pero acceder a un dato más profundo en la pila puede requerir la eliminación de varios otros elementos primero. ^[1]

Considerada como una colección secuencial, una pila tiene un extremo que es la única posición en la que pueden ocurrir las operaciones de inserción y extracción, la parte superior de la pila, y está fija en el otro extremo, la parte inferior . Una pila puede implementarse, por ejemplo, como una lista enlazada simple con un puntero al elemento superior.

Se puede implementar una pila para que tenga una capacidad limitada. Si la pila está llena y no contiene suficiente espacio para aceptar otro elemento, se encuentra en un estado de desbordamiento de pila .

Se necesita una pila para implementar la búsqueda en profundidad .

Las pilas entraron en la literatura de la ciencia informática en 1946, cuando Alan Turing utilizó los términos "enterrar" y "desenterrar" como un medio para llamar y regresar de subrutinas. ^{[2] [3]} Las subrutinas y una pila de dos niveles ya se habían implementado en el Z4 de Konrad Zuse en 1945. ^{[4] [5]}

Klaus Samelson y Friedrich L. Bauer de la Universidad Técnica de Múnich propusieron la idea de una pila llamada Operationskeller ("sótano operativo") en 1955 ^{[6] [7]} y presentaron una patente en 1957. ^{[8] [9] [10] [11]} En marzo de 1988, cuando Samelson ya había fallecido, Bauer recibió el premio IEEE Computer Pioneer Award por la invención del principio de pila. ^{[12] [7]} Charles Leonard Hamblin desarrolló conceptos similares de forma independiente en la primera mitad de 1954 ^{[13] [7]} y Wilhelm Kämmerer  [de] con su automatisches Gedächtnis ("memoria automática") en 1958. ^{[14] [15] [7]}

Las pilas se describen a menudo utilizando la analogía de una pila de platos accionada por resorte en una cafetería. ^{[16] [1] [17]} Los platos limpios se colocan en la parte superior de la pila, empujando hacia abajo los platos que ya están allí. Cuando se retira el plato superior de la pila, el que está debajo se eleva para convertirse en el nuevo plato superior.

En muchas implementaciones, una pila tiene más operaciones que las operaciones esenciales "push" y "pop". Un ejemplo de una operación no esencial es "top of stack" o "peek", que observa el elemento superior sin quitarlo de la pila. ^[18] Dado que esto se puede dividir en un "pop" seguido de un "push" para devolver los mismos datos a la pila, no se considera una operación esencial. Si la pila está vacía, se producirá una condición de desbordamiento al ejecutar las operaciones "stack top" o "pop". Además, muchas implementaciones proporcionan una verificación si la pila está vacía y una operación que devuelve su tamaño.

Una pila se puede implementar fácilmente a través de una matriz o una lista enlazada , ya que es simplemente un caso especial de una lista. ^[19] En cualquier caso, lo que identifica la estructura de datos como una pila no es la implementación sino la interfaz: al usuario solo se le permite insertar o sacar elementos de la matriz o lista enlazada, con algunas otras operaciones auxiliares. A continuación se demostrarán ambas implementaciones utilizando pseudocódigo .

Se puede utilizar una matriz para implementar una pila (limitada), de la siguiente manera. El primer elemento, generalmente en el desplazamiento cero , es la parte inferior, lo que resulta en array[0]que sea el primer elemento que se inserta en la pila y el último que se extrae. El programa debe realizar un seguimiento del tamaño (longitud) de la pila, utilizando una variable top que registra la cantidad de elementos insertados hasta el momento, por lo tanto, apunta al lugar en la matriz donde se insertará el siguiente elemento (asumiendo una convención de índice basada en cero). Por lo tanto, la pila en sí se puede implementar de manera efectiva como una estructura de tres elementos:

pila de estructura : tamaño máximo: entero arriba: entero artículos: matriz de artículos

procedimiento initialize(stk: pila, tamaño: entero): stk.items ← nueva matriz de elementos de tamaño , inicialmente vacía stk.maxsize ← tamaño punto superior ← 0

La operación push agrega un elemento e incrementa el índice superior , después de verificar si hay desbordamiento:

procedimiento push(stk : pila, x : elemento): si stk.top = stk.maxsize: Informar de un error de desbordamiento demás : stk.items[stk.top] ← x stk.top ← stk.top + 1

De manera similar, pop disminuye el índice superior después de verificar si hay desbordamiento y devuelve el elemento que anteriormente era el superior:

procedimiento pop(stk : pila): si stk.top = 0: Informar de un error de desbordamiento demás : punto.arriba ← punto.arriba − 1 r ← stk.items[stk.top] volver r

Al utilizar una matriz dinámica , es posible implementar una pila que puede crecer o contraerse tanto como sea necesario. El tamaño de la pila es simplemente el tamaño de la matriz dinámica, lo que constituye una implementación muy eficiente de una pila, ya que agregar elementos o quitarlos del final de una matriz dinámica requiere tiempo O(1) amortizado.

Otra opción para implementar pilas es utilizar una lista enlazada simple . Una pila es entonces un puntero a la "cabeza" de la lista, con quizás un contador para llevar un registro del tamaño de la lista:

Marco de estructura : datos : artículo siguiente: marco o nulo

pila de estructura : cabeza: marco o nulo tamaño: entero

procedimiento initialize(stk : pila): stk.cabeza ← nulo tamaño de pieza ← 0

La inserción y extracción de elementos se realiza al principio de la lista; el desbordamiento no es posible en esta implementación (a menos que se agote la memoria):

procedimiento push(stk : pila, x : elemento): newhead ← nuevo marco nuevo encabezado.datos ← x newhead.next ← stk.cabeza stk.head ← nuevohead tamaño de pieza ← tamaño de pieza + 1

procedimiento pop(stk : pila): si stk.head = nil: Informar de un error de desbordamiento r ← stk.cabeza.datos stk.cabeza ← stk.cabeza.siguiente tamaño de pieza ← tamaño de pieza - 1 volver r

Algunos lenguajes, como Perl , LISP , JavaScript y Python , hacen que las operaciones de pila push y pop estén disponibles en sus tipos de lista/array estándar. Algunos lenguajes, en particular los de la familia Forth (incluido PostScript ), están diseñados en torno a pilas definidas por el lenguaje que son directamente visibles y manipuladas por el programador.

El siguiente es un ejemplo de manipulación de una pila en Common Lisp (" > " es el indicador del intérprete de Lisp; las líneas que no comienzan con " > " son las respuestas del intérprete a las expresiones):

> ( setf stack ( list 'a 'b 'c )) ;; establece la variable "stack" ( A B C ) > ( pop stack ) ;; obtiene el elemento superior (más a la izquierda), debe modificar la pila A > stack ;; verifica el valor de stack ( B C ) > ( push 'new stack ) ;; inserta un nuevo elemento superior en la pila ( NEW B C )                     

Varios de los tipos de contenedores de la biblioteca estándar de C++ tienen operaciones push_back y pop_back con semántica LIFO; además, la clase de plantilla de pila adapta los contenedores existentes para proporcionar una API restringida con solo operaciones push/pop. PHP tiene una clase SplStack. La biblioteca de Java contiene una clase que es una especialización de . A continuación se muestra un programa de ejemplo en lenguaje Java que utiliza esa clase.StackVector

importar java.util.Stack ; clase  StackDemo { public static void main ( String [] args ) { Stack < String > stack = new Stack < String > (); stack . push ( "A" ); // Insertar "A" en la pila stack . push ( "B" ); // Insertar "B" en la pila stack . push ( "C" ); // Insertar "C" en la pila stack . push ( "D" ); // Insertar "D" en la pila System . out . println ( stack . peek ()); // Imprime la parte superior de la pila ("D") stack . pop (); // Eliminando la parte superior ("D") stack . pop (); // Eliminando la siguiente parte superior ("C") } }                          

Un uso común de las pilas a nivel de arquitectura es como medio para asignar y acceder a la memoria.

Una pila típica es un área de la memoria de la computadora con un origen fijo y un tamaño variable. Inicialmente, el tamaño de la pila es cero. Un puntero de pila (generalmente en forma de registro de procesador ) apunta a la ubicación de la pila a la que se hizo referencia más recientemente; cuando la pila tiene un tamaño de cero, el puntero de pila apunta al origen de la pila.

Las dos operaciones aplicables a todas las pilas son:

• Una operación de inserción : la dirección en el puntero de la pila se ajusta según el tamaño del elemento de datos y se escribe un elemento de datos en la ubicación a la que apunta el puntero de la pila.
• Una operación pop o pull : se lee un elemento de datos en la ubicación actual a la que apunta el puntero de la pila, y el puntero de la pila se mueve una distancia correspondiente al tamaño de ese elemento de datos.

Existen muchas variaciones del principio básico de las operaciones de pila. Cada pila tiene una ubicación fija en la memoria en la que comienza. A medida que se agregan elementos de datos a la pila, el puntero de la pila se desplaza para indicar la extensión actual de la pila, que se expande a partir del origen.

Los punteros de pila pueden apuntar al origen de una pila o a un rango limitado de direcciones por encima o por debajo del origen (dependiendo de la dirección en la que crece la pila); sin embargo, el puntero de pila no puede cruzar el origen de la pila. En otras palabras, si el origen de la pila está en la dirección 1000 y la pila crece hacia abajo (hacia las direcciones 999, 998, etc.), el puntero de pila nunca debe incrementarse más allá de 1000 (hasta 1001 o más allá). Si una operación de extracción en la pila hace que el puntero de pila se mueva más allá del origen de la pila, se produce un desbordamiento de pila . Si una operación de inserción hace que el puntero de pila aumente o disminuya más allá de la extensión máxima de la pila, se produce un desbordamiento de pila .

Algunos entornos que dependen en gran medida de pilas pueden proporcionar operaciones adicionales, por ejemplo:

• Duplicado : el elemento superior se extrae y luego se empuja dos veces, de modo que dos copias del elemento superior anterior ahora se encuentran en la parte superior.
• Peek : se inspecciona (o devuelve) el elemento superior, pero el puntero de la pila y el tamaño de la pila no cambian (lo que significa que el elemento permanece en la pila). Esto también se puede llamar operación superior .
• Intercambio o trueque : los dos elementos superiores en la pila se intercambian.
• Rotar (o rodar) : los n elementos superiores se mueven en la pila de forma rotatoria. Por ejemplo, si n = 3 , los elementos 1, 2 y 3 de la pila se mueven a las posiciones 2, 3 y 1 de la pila, respectivamente. Existen muchas variantes posibles de esta operación, siendo las más comunes las llamadas rotación a la izquierda y rotación a la derecha.

Las pilas se visualizan a menudo creciendo de abajo hacia arriba (como las pilas del mundo real). También se pueden visualizar creciendo de izquierda a derecha, donde la parte superior está en el extremo derecho, o incluso creciendo de arriba hacia abajo. La característica importante es que la parte inferior de la pila esté en una posición fija. La ilustración de esta sección es un ejemplo de una visualización de crecimiento de arriba hacia abajo: la parte superior (28) es la parte "inferior" de la pila, ya que la parte "superior" de la pila (9) es desde donde se empujan o extraen los elementos.

Una rotación hacia la derecha moverá el primer elemento a la tercera posición, el segundo a la primera y el tercero a la segunda. A continuación se muestran dos visualizaciones equivalentes de este proceso:

manzana plátanoplátano ===rotación derecha==> pepinopepino manzana

pepino manzanaplátano ===rotación a la izquierda==> pepinomanzana plátano

En las computadoras, una pila suele representarse mediante un bloque de celdas de memoria, con la "base" en una ubicación fija y el puntero de pila que contiene la dirección de la celda "superior" actual en la pila. La nomenclatura "superior" e "inferior" se utiliza independientemente de si la pila realmente crece hacia direcciones de memoria superiores.

Al insertar un elemento en la pila, el puntero de la pila se ajusta según el tamaño del elemento (ya sea decrementándolo o incrementándolo, según la dirección en la que crece la pila en la memoria), apuntándolo a la siguiente celda y copiando el nuevo elemento superior en el área de la pila. Dependiendo nuevamente de la implementación exacta, al final de una operación de inserción, el puntero de la pila puede apuntar a la siguiente ubicación no utilizada en la pila, o puede apuntar al elemento superior en la pila. Si la pila apunta al elemento superior actual, el puntero de la pila se actualizará antes de que se inserte un nuevo elemento en la pila; si apunta a la siguiente ubicación disponible en la pila, se actualizará después de que se inserte el nuevo elemento en la pila.

Sacar la pila es simplemente lo inverso de empujarla. Se quita el elemento superior de la pila y se actualiza el puntero de la pila, en el orden opuesto al utilizado en la operación de empujar.

Muchos diseños de CPU de tipo CISC , incluidos los x86 , Z80 y 6502 , tienen un registro dedicado para su uso como puntero de pila de llamadas con instrucciones dedicadas de llamada, retorno, inserción y extracción que implícitamente actualizan el registro dedicado, aumentando así la densidad del código . Algunos procesadores CISC, como el PDP-11 y el 68000 , también tienen modos de direccionamiento especiales para la implementación de pilas , normalmente también con un puntero de pila semidedicado (como A7 en el 68000). Por el contrario, la mayoría de los diseños de CPU RISC no tienen instrucciones de pila dedicadas y, por lo tanto, la mayoría de los registros, si no todos, se pueden usar como punteros de pila según sea necesario.

Algunas máquinas utilizan una pila para realizar operaciones aritméticas y lógicas; los operandos se colocan en la pila y las operaciones aritméticas y lógicas actúan sobre uno o más elementos de la parte superior de la pila, sacándolos de la pila y colocando el resultado en la pila. Las máquinas que funcionan de esta manera se denominan máquinas de pila .

Varias computadoras centrales y minicomputadoras eran máquinas apiladas, siendo las más famosas los grandes sistemas de Burroughs . Otros ejemplos incluyen las máquinas CISC HP 3000 y las máquinas CISC de Tandem Computers .

La arquitectura de punto flotante x87 es un ejemplo de un conjunto de registros organizados como una pila donde también es posible el acceso directo a registros individuales (en relación con la parte superior actual).

Tener la parte superior de la pila como argumento implícito permite una pequeña huella de código de máquina con un buen uso del ancho de banda del bus y de los cachés de código , pero también impide algunos tipos de optimizaciones posibles en procesadores que permiten el acceso aleatorio al archivo de registros para todos (dos o tres) operandos. Una estructura de pila también hace que las implementaciones superescalares con cambio de nombre de registros (para ejecución especulativa ) sean algo más complejas de implementar, aunque aún es factible, como lo ejemplifican las implementaciones x87 modernas .

Sun SPARC , AMD Am29000 e Intel i960 son ejemplos de arquitecturas que utilizan ventanas de registro dentro de una pila de registros como otra estrategia para evitar el uso de memoria principal lenta para argumentos de funciones y valores de retorno.

También hay una serie de microprocesadores pequeños que implementan una pila directamente en el hardware, y algunos microcontroladores tienen una pila de profundidad fija a la que no se puede acceder directamente. Algunos ejemplos son los microcontroladores PIC , el Computer Cowboys MuP21, la línea Harris RTX y el Novix NC4016. Al menos una familia de microcontroladores, la COP400 , implementa una pila ya sea directamente en el hardware o en la RAM a través de un puntero de pila, según el dispositivo. Muchos microprocesadores basados ​​en pila se utilizaron para implementar el lenguaje de programación Forth a nivel de microcódigo .

Las calculadoras que emplean la notación polaca inversa utilizan una estructura de pila para almacenar valores. Las expresiones se pueden representar en notaciones de prefijo, posfijo o infijo y la conversión de una forma a otra se puede lograr utilizando una pila. Muchos compiladores utilizan una pila para analizar la sintaxis antes de traducirla a código de bajo nivel. La mayoría de los lenguajes de programación son lenguajes libres de contexto , lo que permite analizarlos con máquinas basadas en pilas.

Otra aplicación importante de las pilas es el retroceso . Un ejemplo de esto es el simple ejemplo de encontrar el camino correcto en un laberinto que contiene una serie de puntos, un punto de partida, varios caminos y un destino. Si se deben elegir caminos aleatorios, luego de seguir un camino incorrecto, debe haber un método para regresar al comienzo de ese camino. Esto se puede lograr mediante el uso de pilas, ya que se puede insertar un último punto correcto en la pila y sacarlo de la pila en caso de un camino incorrecto.

El ejemplo prototípico de un algoritmo de retroceso es la búsqueda en profundidad , que encuentra todos los vértices de un gráfico a los que se puede llegar desde un vértice inicial especificado. Otras aplicaciones del retroceso implican la búsqueda en espacios que representan soluciones potenciales a un problema de optimización. La técnica de ramificación y acotación es una técnica para realizar este tipo de búsquedas de retroceso sin buscar exhaustivamente todas las soluciones potenciales en dicho espacio.

Varios lenguajes de programación están orientados a la pila , lo que significa que definen la mayoría de las operaciones básicas (sumar dos números, imprimir un carácter) como tomar sus argumentos de la pila y colocar los valores de retorno nuevamente en la pila. Por ejemplo, PostScript tiene una pila de retorno y una pila de operandos, y también tiene una pila de estado de gráficos y una pila de diccionarios. Muchas máquinas virtuales también están orientadas a la pila, incluida la máquina de código p y la máquina virtual Java .

Casi todas las convenciones de llamada (las formas en que las subrutinas reciben sus parámetros y devuelven resultados) utilizan una pila especial (la " pila de llamadas ") para almacenar información sobre la llamada y anidación de procedimientos/funciones con el fin de cambiar al contexto de la función llamada y restaurar a la función que llama cuando finaliza la llamada. Las funciones siguen un protocolo de tiempo de ejecución entre el llamador y el llamado para guardar los argumentos y el valor de retorno en la pila. Las pilas son una forma importante de admitir llamadas a funciones anidadas o recursivas . Este tipo de pila es utilizada implícitamente por el compilador para admitir las declaraciones CALL y RETURN (o sus equivalentes) y no es manipulada directamente por el programador.

Algunos lenguajes de programación utilizan la pila para almacenar datos locales de un procedimiento. El espacio para los elementos de datos locales se asigna desde la pila cuando se ingresa al procedimiento y se libera cuando éste sale. El lenguaje de programación C se implementa típicamente de esta manera. El uso de la misma pila para llamadas de datos y de procedimientos tiene importantes implicaciones de seguridad (ver a continuación) de las cuales un programador debe estar consciente para evitar introducir errores de seguridad graves en un programa.

Varios algoritmos utilizan una pila (separada de la pila de llamadas de función habitual de la mayoría de los lenguajes de programación) como la estructura de datos principal con la que organizan su información. Entre ellos se incluyen:

• Exploración de Graham , un algoritmo para la envoltura convexa de un sistema de puntos bidimensional. Una envoltura convexa de un subconjunto de la entrada se mantiene en una pila, que se utiliza para encontrar y eliminar concavidades en el límite cuando se agrega un nuevo punto a la envoltura. ^[20]
• Parte del algoritmo SMAWK para encontrar los mínimos de fila de una matriz monótona utiliza pilas de manera similar al escaneo de Graham. ^[21]
• Todos los valores más pequeños más cercanos , el problema de encontrar, para cada número en una matriz, el número precedente más cercano que sea menor que él. Un algoritmo para este problema utiliza una pila para mantener una colección de candidatos para el valor más pequeño más cercano. Para cada posición en la matriz, la pila se vacía hasta que se encuentra un valor más pequeño en su parte superior, y luego el valor en la nueva posición se coloca en la pila. ^[22]
• El algoritmo de cadena de vecinos más cercanos , un método de agrupamiento jerárquico aglomerativo basado en el mantenimiento de una pila de clústeres, cada uno de los cuales es el vecino más cercano de su predecesor en la pila. Cuando este método encuentra un par de clústeres que son vecinos más cercanos entre sí, se extraen y se fusionan. ^[23]

Algunos entornos informáticos utilizan pilas de forma que pueden hacerlos vulnerables a ataques y violaciones de seguridad . Los programadores que trabajan en dichos entornos deben tener especial cuidado para evitar este tipo de problemas en estas implementaciones.

Por ejemplo, algunos lenguajes de programación utilizan una pila común para almacenar tanto los datos locales de un procedimiento llamado como la información de enlace que permite que el procedimiento regrese a su llamador. Esto significa que el programa mueve datos dentro y fuera de la misma pila que contiene direcciones de retorno críticas para las llamadas de procedimiento. Si los datos se mueven a la ubicación incorrecta en la pila, o un elemento de datos de gran tamaño se mueve a una ubicación de pila que no es lo suficientemente grande para contenerlo, la información de retorno para las llamadas de procedimiento puede estar dañada, lo que provoca que el programa falle.

Los grupos malintencionados pueden intentar un ataque de destrucción de pila que se aproveche de este tipo de implementación al proporcionar una entrada de datos de gran tamaño a un programa que no verifica la longitud de la entrada. Un programa de este tipo puede copiar los datos en su totalidad a una ubicación en la pila y, al hacerlo, puede cambiar las direcciones de retorno de los procedimientos que lo han llamado. Un atacante puede experimentar para encontrar un tipo específico de datos que se puedan proporcionar a un programa de este tipo de modo que la dirección de retorno del procedimiento actual se restablezca para apuntar a un área dentro de la propia pila (y dentro de los datos proporcionados por el atacante), que a su vez contiene instrucciones que llevan a cabo operaciones no autorizadas.

Este tipo de ataque es una variación del ataque de desbordamiento de búfer y es una fuente extremadamente frecuente de brechas de seguridad en el software, principalmente porque algunos de los compiladores más populares utilizan una pila compartida tanto para llamadas de datos como de procedimientos, y no verifican la longitud de los elementos de datos. Con frecuencia, los programadores tampoco escriben código para verificar el tamaño de los elementos de datos, y cuando un elemento de datos de tamaño demasiado grande o demasiado pequeño se copia a la pila, puede ocurrir una brecha de seguridad.

•  Este artículo incorpora material de dominio público de Paul E. Black. "Pila limitada". Diccionario de algoritmos y estructuras de datos . NIST .

• Donald Knuth . El arte de la programación informática , volumen 1: Algoritmos fundamentales , tercera edición. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Sección 2.2.1: Pilas, colas y deques, págs. 238–243. 
• Langmaack, Hans [en alemán] (2015) [14 de noviembre de 2014]. Escrito en Kiel, Alemania. Friedrich L. Bauers und Klaus Samelsons Arbeiten in den 1950er-Jahren zur Einführung der Begriffe Kellerprinzip und Kellerautomat [ Trabajos de Friedrich L. Bauer y Klaus Samelson en la década de 1950 sobre la introducción de los términos principio de bodega y autómata de bodega ] (PDF) (en alemán ). Jena, Alemania: Institut für Informatik, Christian-Albrechts-Universität zu Kiel. págs. 19-29. Archivado (PDF) desde el original el 14 de noviembre de 2022 . Consultado el 14 de noviembre de 2022 .(11 páginas) (NB. Publicado en Fothe & Wilke.)
• Goos, Gerhard [en alemán] (7 de agosto de 2017). Geschichte der deutschsprachigen Informatik - Programmiersprachen und Übersetzerbau [ Historia de la informática en los países de habla alemana - Lenguajes de programación y diseño de compiladores ] (PDF) (en alemán). Karlsruhe, Alemania: Fakultät für Informatik, Instituto Tecnológico de Karlsruhe (KIT). Archivado (PDF) desde el original el 19 de mayo de 2022 . Consultado el 14 de noviembre de 2022 .(11 páginas)

Wikimedia Commons tiene medios relacionados con Estructuras de datos de pila .

Wikilibros tiene un libro sobre el tema: Estructuras de datos/Pilas y colas

• Máquinas apiladoras: la nueva ola
• Profundidad de la pila delimitadora
• Análisis del tamaño de pila para programas controlados por interrupciones