Una pila (stack en inglés) es una lista ordenada o estructura de datos que permite almacenar y recuperar datos, siendo el modo de acceso a sus elementos de tipo LIFO (del inglés Last In, First Out, «último en entrar, primero en salir»). Esta estructura se aplica en multitud de supuestos en el área de la informática debido a su simplicidad y capacidad de dar respuesta a numerosos procesos.

Para el manejo de los datos cuenta con dos operaciones básicas: apilar (push), que coloca un objeto en la pila, y su operación inversa, retirar (o desapilar, pop), que retira el último elemento apilado.

En cada momento solamente se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, Top of Stack en inglés). La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al anterior (apilado con anterioridad), que pasa a ser el último, el nuevo TOS.

Las pilas suelen emplearse en los siguientes contextos: Evaluación de expresiones en notación postfija (notación polaca inversa). Reconocedores sintácticos de lenguajes independientes del contexto. Implementación de recursividad.

En un sistema operativo cada proceso tiene un espacio de memoria (pila) para almacenar valores y llamadas a funciones.

Una pila acotada es una pila limitada a un tamaño máximo impuesto en su especificación.

Por analogía con objetos cotidianos, una operación apilar equivaldría a colocar un plato sobre una pila de platos, y una operación retirar equivaldría a retirarlo.

Historia El método de pila para la evaluación de expresiones fue propuesto en 1955 y dos años después patentado por Friedrich L. Bauer, quién recibió en 1988 el premio "IEEE Computer Society Pioneer Award" por su trabajo en el desarrollo de dicha estructura de datos.

Pila como tipo abstracto de datos

A modo de resumen, la pila es un contenedor de nodos y tiene dos operaciones básicas: push (o apilar) y pop (o desapilar). «Push» añade un nodo a la parte superior de la pila, dejando por debajo el resto de los nodos ya presentes en la pila. «Pop» devuelve y elimina el actual nodo superior de la pila. Una metáfora que se utiliza con frecuencia es la idea de una pila de platos dispuesta en una cafetería en un contenedor con un muelle que mantiene la pila a nivel. En esa serie, solo el primer plato es visible y accesible para el usuario, todos las demás permanecen ocultos. Como se añaden nuevos platos, cada nuevo plato se convierte en la parte superior de la pila, permaneciendo escondidos debajo los demás. A medida que el plato superior se extrae de la pila, el inmediatamente inferior pasa a ocupar la parte superior de la pila. Dos principios importantes son ilustrados por esta metáfora: únicamente se accede al plato que se encuentra en la parte superior (el último en depositarse), y el resto de platos de la pila permanecen ocultos. Para extraer un plato distinto al superior habrá que extraer antes los que se encuentran sobre él.

Operaciones

Habitualmente, junto a las dos operaciones básicas de apilar y desapilar (push, pop), las pilas puede implementar otra serie de funciones:

Crear (constructor): crea la pila vacía. Tamaño (size): regresa el número de elementos de la pila. Apilar (push): añade un elemento a la pila. Desapilar (pop): lee y retira el elemento superior de la pila. Leer último (top o peek): lee el elemento superior de la pila sin retirarlo. Vacía (empty): devuelve cierto si la pila está sin elementos o falso en caso de que contenga alguno.

Una pila puede implementarse fácilmente, ya sea mediante una matriz o una lista enlazada. Lo que identifica a una estructura de datos como una pila en cualquier caso no es su estructura sino su interfaz: al usuario solamente se le permite colocar y extraer datos en el modo que se espera de una pila y algunas otras operaciones auxiliares.

Otro tipo de estructura de datos es la cola (FIFO, del inglés First In First Out), «primero en entrar, primero en salir».

Pilas Hardware

Un uso muy común de las pilas a nivel de arquitectura hardware es la asignación de memoria.

Arquitectura básica de una pila

Una pila típica es un área de la memoria de los computadores con un origen fijo, un espacio para almacenar datos y un puntero. Al principio, su número de elementos es cero y la dirección del puntero coincide con la dirección de origen. Conforme van incorporándose datos, los elementos contenidos en la pila van incrementándose y el puntero va actualizando su dirección para hacerla coincidir con el último en incorporase.

Las dos operaciones aplicables a todas las pilas son:

Apilar: colocar un nuevo dato en la pila. Se lee el puntero para localizar el último elemento, se incorpora a continuación de este y se redirecciona el puntero para que apunte al nuevo dato incorporado. Desapilar: extraer un dato de la pila. Se localiza el último dato mediante el puntero, se lee el dato y se redirecciona el puntero al elemento inmediato anterior para que vuelva a apuntar al último dato de la pila.

Una pila queda definida por su origen (una dirección de memoria), y su capacidad para almacenar datos. Cuando se intenta leer más allá de su origen (esto es, se intenta leer un elemento cuando está vacía) o cuando se intenta sobrepasar su capacidad de almacenar elementos, se produce un error: error por desbordamiento.

Se puede visualizar una pila de datos (independientemente de cómo se almacene en la memoria) como una serie de datos colocados unos sobre otros (representación que se corresponde con el mundo real) o como una sucesión de datos colocados de izquierda a derecha, unos tras otros.

Una pila ocuparía un bloque de celdas de memoria, con una dirección de origen, un espacio reservado para la acumulación de datos y un puntero que apunta al último dato incorporado. La estructura que adopte una pila puede ser muy variada: almacenando datos en direcciones crecientes o decrecientes, con capacidad de almacenamiento flexible, con punteros que apunten al último elemento o a la posición que deberá ocupar el próximo elemento que se incorpore… En cualquier caso, quedará definida por su algoritmo: último en entrar, primero en salir.

Soporte de Hardware

Muchas CPUs tienen registros que se pueden utilizar como punteros de pila. Algunas, como Intel x86, tienen instrucciones especiales que implícitan el uso de un registro dedicado a la tarea de ser un puntero de pila. Otras, como DEC PDP-11 y de la familia 68000 de Motorola, Inc. tienen que hacer frente a los modos de hacer posible la utilización de toda una serie de registros como un puntero de pila. La serie Intel 80x87 de coprocesadores numéricos tiene un conjunto de registros al que se puede acceder ya sea como una pila o como una serie de registros numerados. Algunos microcontroladores, por ejemplo algunos PICs, tienen un fondo fijo de pila que no es directamente accesible. También hay una serie de microprocesadores que aplican una pila directamente en el hardware:

Computer vaqueros MuP21 Harris RTX línea Novix NC4016

Muchas pilas basadas en los microprocesadores se utilizan para aplicar el lenguaje de programación Forth en el nivel de microcódigo. también se utilizaron las pilas como base de una serie de mainframes y miniordenadores. Esas máquinas fueron llamadas máquina de pila, el más famoso es el Burroughs B5000.

Soporte de Software

En programas de aplicación escrito en un lenguaje de alto nivel, una pila puede ser implementada de manera eficiente, ya sea usando vectores o listas enlazadas. En LISP no hay necesidad de aplicar la pila, puesto que las funciones apilar y desapilar están disponibles para cualquier lista. Adobe PostScript también está diseñada en torno a una pila que se encuentra directamente visible y manipuladas por el programador. El uso de las pilas está muy presente en el desarrollo de software por ello la importancia de las pilas como tipo abstracto de datos.

Expresión de evaluación y análisis sintáctico

Se calcula empleando la notación polaca inversa utilizando una estructura de pila para almacenar temporalmente los valores. Las expresiones pueden ser representadas en prefijo, infijo, postfijo. La conversión de una forma de expresión a otra forma, necesita de una pila. Muchos compiladores utilizan una pila para analizar la sintaxis de las expresiones, bloques de programa, etc. antes de traducir a código de bajo nivel. Los lenguajes de programación de alto nivel son compilados o traducidos a código máquina realizando la conversión de expresiones a la notación que mejor se adapte a las características de su modo de operar, buscando siempre la simplicidad.

Por ejemplo, el cálculo: ((1 + 2) * 4) + 3, se traduciría o notación postfija con la ventaja de no tener que atender a la jerarquía de prioridades:

En notación postfija: 1 2 + 4 * 3 +

La expresión es evaluada de izquierda a derecha utilizando una pila:

Apilar cuando el dato sea un operando Desapilar dos operandos y evaluar el valor cuando el dato sea un operador. Apilar el resultado de la operación.

(los datos de la pila se muestran después de haberse llevado a cabo la operación):

ENTRADA OPERACIÓN PILA

1 Apilar operando 1 2 Apilar operando 1, 2 + Sumar operandos* 3 4 Apilar operando 3, 4 * Multiplicar operandos* 12 3 Apilar operando 12, 3 + Sumar operandos* 15

El resultado final, 15, se encuentra en la pila, y el puntero apuntado a su dirección. Se lee haciendo pop y la pila vuelve a quedar vacía.

*.- Se extraen los dos operandos con lo que el puntero los da por eliminados y, atendiendo a su orden (necesario en operaciones de resta, división y potencia) se realiza la operación. El resultado se coloca en la pila.

Implementación en aplicaciones informáticas Supongamos que se está procesando una función y en su interior llama a otra función. La función se abandona para procesar la función de la llamada, pero antes se almacena en una pila la dirección que apunta a la función. Ahora supongamos que esa nueva función llama a su vez a otra función. Igualmente, se almacena su dirección, se abandona y se atiende la petición. Así en tantos casos como existan peticiones. La ventaja de la pila es que no requiere definir ninguna estructura de control ni conocer las veces que el programa estará saltando entre funciones para después retomarlas, con la única limitación de la capacidad de almacenamiento de la pila. Conforme se van cerrando las funciones, se van rescatando las funciones precedentes mediante sus direcciones almacenadas en la pila y se va concluyendo su proceso, esto hasta llegar a la primera.

El caso típico es el de una función recursiva (que se llama a sí misma), esto es posible implementarlo con sencillez mediante una pila. La función se llama a sí misma tantas veces como sea necesario hasta que el resultado de la función cumpla la condición de retorno; entonces, todas las funciones abiertas van completando su proceso en cascada. No se necesita saber cuántas veces se anidará y, por tanto, tampoco cuando se cumplirá la condición, con la única limitación de la capacidad de la pila. De sobrepasarse ese límite, normalmente porque se entra en un bucle sin final, se produce el «error de desbordamiento de la pila».

La ordenación de datos por el método de la burbuja se resuelve mediante una función recursiva.

Tiempo de ejecución de la gestión de memoria

Artículo principal: Pila basada en la asignación de memoria y Pila máquina. Una serie de lenguajes de programación están orientadas a la pila, lo que significa que la mayoría definen operaciones básicas (añadir dos números, la impresión de un carácter) cogiendo sus argumentos de la pila, y realizando de nuevo los valores de retorno en la pila. Por ejemplo, PostScript tiene una pila de retorno y un operando de pila, y también tiene un montón de gráficos estado y un diccionario de pila.