En informática , una pila es un tipo de datos abstracto que sirve como una colección de elementos con dos operaciones principales:
Además, una operación de vistazo puede, sin modificar la pila, devolver el valor del último elemento agregado. La pila de nombres es una analogía con un conjunto de elementos físicos apilados uno encima del 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 con el acrónimo LIFO . [nb 1] Al igual que con una pila de objetos físicos, esta estructura facilita sacar un elemento de la parte superior de la pila, pero acceder a un dato más profundo en la pila puede requerir eliminar varios otros elementos primero. [1]
Considerada una estructura de datos lineal , o más abstractamente una colección secuencial, una pila tiene un extremo que es la única posición en la que pueden ocurrir las operaciones de empujar y sacar, la parte superior de la pila, y está fijo en el otro extremo, la parte inferior . Esta estructura de datos permite implementar una pila como una lista enlazada individualmente y como 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, la pila se encuentra en un estado de desbordamiento de pila .
Se necesita una pila para implementar la búsqueda en profundidad .
Stacks entró en la literatura 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 Munich propusieron la idea de una pila llamada Operationskeller ("bodega operativa") 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ó de forma independiente conceptos similares en la primera mitad de 1954 [13] [7] y Wilhelm Kämmerer con su automatisches Gedächtnis ("memoria automática") en 1958. [14] [15] [7]
Las pilas a menudo se describen utilizando la analogía de una pila de platos accionada por un resorte en una cafetería. [16] [1] [17] Los platos limpios se colocan encima de la pila, empujando hacia abajo los platos que ya estén allí. Cuando se retira la placa superior de la pila, la que está debajo se eleva para convertirse en la nueva placa superior.
En muchas implementaciones, una pila tiene más operaciones que las operaciones esenciales "push" y "pop". Un ejemplo de operación no esencial es "parte superior de la pila" o "mirar", que observa el elemento superior sin sacarlo 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 insuficiente al ejecutar las operaciones "superior de la pila" 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 vinculada , ya que es simplemente un caso especial de una lista. En cualquier caso, lo que identifica la estructura de datos como una pila no es la implementación sino la interfaz: al usuario sólo se le permite colocar o insertar elementos en 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 el primer elemento se inserte en la pila y el último elemento se desprenda. El programa debe realizar un seguimiento del tamaño (longitud) de la pila, utilizando una variable top que registra el número de elementos empujados hasta el momento y, por lo tanto, apunta al lugar de la matriz donde se insertará el siguiente elemento (asumiendo un valor cero). convención de índice basada). Por lo tanto, la pila en sí se puede implementar efectivamente como una estructura de tres elementos:
pila de estructura : tamaño máximo: entero arriba: número entero elementos: conjunto de elementos
inicialización del procedimiento (stk: pila, tamaño: entero): stk.items ← nueva matriz de elementos de tamaño , inicialmente vacía stk.maxsize ← tamaño stk.arriba ← 0
La operación de inserción agrega un elemento e incrementa el índice superior , después de verificar si hay desbordamiento:
inserción de procedimiento (stk: pila, x: elemento): si stk.top = stk.maxsize: informar error de desbordamiento demás : stk.elementos[stk.top] ← x stk.top ← stk.top + 1
De manera similar, pop disminuye el índice superior después de verificar si hay un desbordamiento insuficiente y devuelve el elemento que anteriormente era el superior:
procedimiento pop(stk: pila): si stk.top = 0: informar error de desbordamiento insuficiente demás : stk.arriba ← stk.arriba − 1 r ← stk.elementos[stk.top] volver r
Usando una matriz dinámica , es posible implementar una pila que puede crecer o reducirse tanto como sea necesario. El tamaño de la pila es simplemente el tamaño de la matriz dinámica, lo cual es una implementación muy eficiente de una pila, ya que agregar o eliminar elementos del final de una matriz dinámica requiere un tiempo O(1) amortizado.
Otra opción para implementar pilas es utilizar una lista enlazada individualmente . Una pila es entonces un puntero al "encabezado" de la lista, quizás con un contador para realizar un seguimiento del tamaño de la lista:
marco de estructura : datos: elemento siguiente : marco o nulo
pila de estructura : cabeza: marco o nulo tamaño: entero
inicialización del procedimiento (stk: pila): stk.cabeza ← nulo stk.tamaño ← 0
Empujar y hacer estallar elementos ocurre al principio de la lista; El desbordamiento no es posible en esta implementación (a menos que la memoria esté agotada):
inserción de procedimiento (stk: pila, x: artículo): newhead ← nuevo marco nuevohead.data ← x nuevohead.siguiente ← stk.head stk.cabeza ← nuevo jefe tamaño.stk ← tamaño.stk + 1
procedimiento pop(stk: pila): si stk.head = nil: informar error de desbordamiento insuficiente r ← stk.cabeza.datos stk.cabeza ← stk.cabeza.siguiente tamaño.stk ← tamaño.stk - 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/matriz estándar. Algunos lenguajes, en particular los de la familia Forth (incluido PostScript ), están diseñados en torno a pilas definidas por lenguajes que el programador puede ver y manipular directamente.
El siguiente es un ejemplo de manipulación de una pila en Common Lisp (" > " es el mensaje del intérprete Lisp; las líneas que no comienzan con " > " son las respuestas del intérprete a las expresiones):
> ( setf pila ( lista ' a'b 'c )) ;; establezca la variable "pila" ( A B C ) > ( pila emergente ) ;; obtener el elemento superior (más a la izquierda), debe modificar la pila A > pila ;; verifique el valor de la pila ( B C ) > ( empuje 'nueva pila ) ;; Empuje una nueva tapa en la pila ( NUEVO 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 ; class StackDemo { public static void main ( String [] args ) { Stack < String > stack = new Stack < String > (); pila . empujar ( "A" ); // Inserta "A" en la pila de la pila . empujar ( "B" ); // Inserta "B" en la pila de la pila . empujar ( "C" ); // Inserta "C" en la pila de la pila . empujar ( "D" ); // Inserta "D" en la pila System . afuera . println ( pila.peek ( ) ) ; // Imprime la parte superior de la pila ("D") . estallido (); // eliminando la pila superior ("D") . estallido (); // eliminando el siguiente superior ("C") } } Un uso común de las pilas a nivel de arquitectura es como medio para asignar y acceder a memoria.
Una pila típica es un área de la memoria de una 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 hace referencia más recientemente; cuando la pila tiene un tamaño de cero, el puntero de la pila apunta al origen de la pila.
Las dos operaciones aplicables a todas las pilas son:
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 desde el 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 la 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 la pila nunca debe incrementarse más allá de 1000 (hasta 1001 o más). Si una operación emergente en la pila hace que el puntero de la pila se mueva más allá del origen de la pila, se produce un desbordamiento de la pila . Si una operación de inserción hace que el puntero de la pila aumente o disminuya más allá de la extensión máxima de la pila, se produce un desbordamiento de la pila .
Algunos entornos que dependen en gran medida de pilas pueden proporcionar operaciones adicionales, por ejemplo:
Las pilas a menudo se visualizan 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 a 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 a abajo: la parte superior (28) es la pila "inferior", ya que la pila "superior" (9) es desde donde se empujan o sacan 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. Aquí hay dos visualizaciones equivalentes de este proceso:
manzana platanoplátano ===girar a la derecha==> pepinomanzana pepino
manzana pepinoplátano ===girar a la izquierda==> pepinomanzana platano
Una pila generalmente está representada en las computadoras por un bloque de celdas de memoria, con la "parte inferior" en una ubicación fija y el puntero de la pila contiene la dirección de la celda "superior" actual de la pila. La nomenclatura "superior" e "inferior" se utiliza independientemente de si la pila realmente crece hacia direcciones de memoria más altas.
Al empujar un elemento a la pila, se ajusta el puntero de la pila según el tamaño del elemento (ya sea disminuyendo o incrementándose, dependiendo de la dirección en la que crece la pila en la memoria), apuntándolo a la siguiente celda y copiando el nuevo elemento superior a 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 de 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 el nuevo elemento se inserte en la pila.
Hacer estallar la pila es simplemente lo contrario de empujar. Se elimina 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 inserción.
Muchos diseños de CPU de tipo CISC , incluidos x86 , Z80 y 6502 , tienen un registro dedicado para usar como puntero de pila de llamadas con instrucciones dedicadas de llamada, retorno, inserción y extracción que actualizan implícitamente 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 el 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, si no todos, los registros pueden usarse como punteros de pila según sea necesario.
Algunas máquinas utilizan una pila para 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 superiores de la pila, sacándolos de la pila y empujando el resultado a la pila. Las máquinas que funcionan de esta manera se denominan máquinas apilables .
Varias mainframes y minicomputadoras eran máquinas apilables, 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 coma 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 las cachés de código , pero también evita algunos tipos de optimizaciones posibles en los procesadores que permiten el acceso aleatorio al archivo de registro 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 todavía 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. Se utilizaron muchos microprocesadores basados en pilas para implementar el lenguaje de programación Forth a nivel de microcódigo .
Las calculadoras que emplean notación polaca inversa utilizan una estructura de pila para contener valores. Las expresiones se pueden representar en notaciones de prefijo, postfijo 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 . Una ilustración de esto es el ejemplo simple 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, entonces después de seguir un camino incorrecto, debe haber un método mediante el cual regresar al comienzo de ese camino. Esto se puede lograr mediante el uso de pilas, ya que se puede empujar un último punto correcto hacia la pila y sacarlo de la pila en caso de una ruta incorrecta.
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 específico. Otras aplicaciones del retroceso implican la búsqueda de espacios que representan soluciones potenciales a un problema de optimización. Branch andbound 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 las operaciones más básicas (sumar dos números, imprimir un carácter) tomando sus argumentos de la pila y colocando los valores devueltos 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 diccionario. Muchas máquinas virtuales también están orientadas a pilas, incluidas la máquina de código p y la máquina virtual Java .
Casi todas las convenciones de llamadas —las formas en que las subrutinas reciben sus parámetros y devuelven resultados—utilizan una pila especial (la " pila de llamadas ") para contener información sobre la llamada y el anidamiento de procedimientos/funciones para cambiar al contexto de la función llamada y restaurar a la función de llamada cuando finalice la llamada. Las funciones siguen un protocolo de ejecución entre la persona que llama y la persona que llama para guardar argumentos y devolver valor en la pila. Las pilas son una forma importante de admitir llamadas a funciones anidadas o recursivas . El compilador utiliza implícitamente este tipo de pila para admitir declaraciones CALL y RETURN (o sus equivalentes) y el programador no lo manipula directamente.
Algunos lenguajes de programación utilizan la pila para almacenar datos locales de un procedimiento. El espacio para elementos de datos locales se asigna desde la pila cuando se ingresa al procedimiento y se desasigna cuando el procedimiento sale. El lenguaje de programación C normalmente se implementa de esta manera. El uso de la misma pila para llamadas de datos y procedimientos tiene importantes implicaciones de seguridad (ver más abajo) que un programador debe tener en cuenta para evitar introducir errores de seguridad graves en un programa.
Varios algoritmos utilizan una pila (separada de la pila de llamadas a funciones habitual de la mayoría de los lenguajes de programación) como estructura de datos principal con la que organizan su información. Éstas incluyen:
Algunos entornos informáticos utilizan pilas de manera que pueden hacerlos vulnerables a ataques y violaciones de seguridad . Los programadores que trabajan en dichos entornos deben tener especial cuidado para evitar tales errores en estas implementaciones.
Como 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 a procedimientos. Si los datos se mueven a una ubicación incorrecta en la pila, o un elemento de datos de gran tamaño se mueve a una ubicación de la pila que no es lo suficientemente grande para contenerlo, la información devuelta para las llamadas a procedimientos puede estar dañada, provocando que el programa falle.
Las partes malintencionadas pueden intentar un ataque de destrucción de pila que aproveche 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 de la pila y, al hacerlo, puede cambiar las direcciones de retorno de los procedimientos que los han llamado. Un atacante puede experimentar para encontrar un tipo específico de datos que se puedan proporcionar a dicho programa, de modo que la dirección de retorno del procedimiento actual se restablezca para que apunte a un área dentro de la pila misma (y dentro de los datos proporcionados por el atacante). que a su vez contiene instrucciones que realizan 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 violaciones de seguridad en el software, principalmente porque algunos de los compiladores más populares utilizan una pila compartida tanto para datos como para llamadas a procedimientos, y no verifican la longitud de elementos de datos. Con frecuencia, los programadores tampoco escriben código para verificar el tamaño de los elementos de datos, y cuando se copia en la pila un elemento de datos de tamaño demasiado grande o insuficiente, puede ocurrir una violación de seguridad.
Die Bezeichnung 'Keller' hierfür wurde von Bauer und Samelson in einer deutschen Patentanmeldung vom 30. März 1957 eingeführt.
Este artículo incorpora material de dominio público de Paul E. Black. "Pila limitada". Diccionario de Algoritmos y Estructuras de Datos . NIST .
