Pila (informática)
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 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.
Forth utiliza dos pilas, una para pasar argumentos y una subrutina de direcciones de retorno. El uso de una pila de retorno es muy común, pero el uso poco habitual de un argumento para una pila legible para humanos es el lenguaje de programación Forth razón que se denomina una pila basada en el idioma.
Muchas máquinas virtuales también están orientadas hacia la pila, incluida la p-código máquina y la máquina virtual Java.
Casi todos los entornos de computación de tiempo de ejecución de memoria utilizan una pila especial PILA para tener información sobre la llamada de un procedimiento o función y de la anidación con el fin de cambiar al contexto de la llamada a restaurar cuando la llamada termina. Ellos siguen un protocolo de tiempo de ejecución entre el que llama y el llamado para guardar los argumentos y el valor de retorno en la pila. Pila es una forma importante de apoyar llamadas anidadas o a funciones recursivas. Este tipo de pila se utiliza implícitamente por el compilador para apoyar CALL y RETURN estados (o sus equivalentes), y no es manipulada directamente por el programador.
Algunos lenguajes de programación utilizan la pila para almacenar datos que son locales a un procedimiento. El espacio para los datos locales se asigna a los temas de la pila cuando el procedimiento se introduce, y son borradas cuando el procedimiento termina. El lenguaje de programación C es generalmente aplicado de esta manera. Utilizando la misma pila de los datos y llamadas de procedimiento tiene importantes consecuencias para la seguridad (ver más abajo), de los que un programador debe ser consciente, a fin de evitar la introducción de graves errores de seguridad en un programa.
Solucionar problemas de búsqueda
La búsqueda de la solución de un problema, es independientemente de si el enfoque es exhaustivo u óptimo, necesita espacio en la pila. Ejemplos de búsqueda exhaustiva métodos son fuerza bruta y backtraking. Ejemplos de búsqueda óptima a explorar métodos,son branch and bound y soluciones heurísticas. Todos estos algoritmos utilizan pilas para recordar la búsqueda de nodos que se han observado, pero no explorados aún. La única alternativa al uso de una pila es utilizar la recursividad y dejar que el compilador sea recursivo (pero en este caso el compilador todavía está utilizando una pila interna). El uso de pilas es frecuente en muchos problemas, que van desde almacenar la profundidad de los árboles hasta resolver crucigramas o jugar al ajedrez por ordenador. Algunos de estos problemas pueden ser resueltos por otras estructuras de datos como una cola.
Seguridad
La seguridad a la hora de desarrollar software usando estructuras de datos de tipo pila es un factor a tener en cuenta debido a ciertas vulnerabilidades que un uso incorrecto de estas puede originar en la seguridad de nuestro software o en la seguridad del propio sistema que lo ejecuta. Por ejemplo, algunos lenguajes de programación usan una misma pila para almacenar los datos para un procedimiento y el enlace que permite retornar a su invocador. Esto significa que el programa introduce y extrae los datos de la misma pila en la que se encuentra la información crítica con las direcciones de retorno de las llamadas a procedimiento, supongamos que al introducir datos en la pila lo hacemos en una posición errónea de manera que introducimos datos de mayor tamaño al soportado por la pila corrompiendo así las llamadas a procedimientos, provocaríamos un fallo en nuestro programa. Esta técnica usada de forma maliciosa (es similar, pero en otro ámbito al buffer overflow) permitiría a un atacante modificar el funcionamiento normal de nuestro programa y nuestro sistema, y es al menos una técnica útil si no lo evitamos en lenguajes muy populares como el ejemplo C++.
Pilas en Java
Este tipo de estructura de datos se puede implementar de forma dinámica o estática, es decir, ya sea con un arreglo o con una lista enlazada. Al hablar de una pila estática, se considera que la pila tendrá un tamaño definido y no podrá superar dicha capacidad para el almacenamiento de más información, solamente la indicada. Y con respecto a una pila dinámica corresponde a una pila que no tendrá un límite de capacidad, es decir, podemos hacer n número de inserciones.
A continuación se presenta la Pila estática, la cual es implementada con base en un arreglo:
public class PilaEstatica{ private int pila[]; private int top;//indica la posición del último elemento insertado private int capacidad; public PilaEstatica(int cap){ capacidad=cap; pila=new int[capacidad]; top=-1; } public boolean estaVacia(){ return(top==-1); } public boolean estaLlena(){ return((top+1)==capacidad); } public void apilar(int elemento){ if(estaLlena()==false) pila[++top]=elemento; else System.out.println("Desbordamiento superior, no se puede apilar"); } public int desapilar(){ if(estaVacia()==false){ return pila[top--]; } else{ System.out.println("Desbordamiento inferior, no se puede desapilar"); } return -1; } public static void main (String args[]){ PilaEstatica pilita=new PilaEstatica(5); pilita.apilar(1); pilita.apilar(12); pilita.apilar(3); int r=pilita.desapilar(); System.out.println("El dato eliminado es "+r); boolean b=pilita.estaVacia(); boolean c=pilita.estaLlena(); System.out.println("¿Está vacia la pla? "+b); System.out.println("¿Está llena la pla? "+c); } } Enseguida se presenta la implementación de la Pila de forma dinámica, implementada en base a una lista simplemente enlazada:
Descargar Código.
Clase Nodo
package pilas; /** * * @author Mauricio López Ramírez */ public class Nodo { private char dato; private Nodo siguiente; public Nodo(char dato) { this.dato = dato; } public char getDato() { return dato; } public void setDato(char dato) { this.dato = dato; } public Nodo getSiguiente() { return siguiente; } public void setSiguiente(Nodo siguiente) { this.siguiente = siguiente; } } Clase Pila
package pilas; /** * * @author Mauricio López Ramírez */ public class Pila { Nodo tos;//Top Of Stack public void apilar(char dato) { Nodo nuevo = new Nodo(dato); if (tos == null) { tos = nuevo; } else { nuevo.setSiguiente(tos); tos = nuevo; } } public char desapilar() { Nodo temp = tos; tos = tos.getSiguiente(); return temp.getDato(); } public void imprimir() { Nodo temp = tos; while (temp != null) { System.out.print(temp.getDato() + "\n"); temp = temp.getSiguiente(); } } } Clase Manejador
package pilas; /** * * @author Mauricio López Ramírez */ public class Manejador { public static void main(String[] args) { Pila nuevaPila = new Pila(); nuevaPila.apilar('A'); nuevaPila.apilar('B'); nuevaPila.apilar('C'); nuevaPila.imprimir(); System.out.println(); nuevaPila.desapilar(); nuevaPila.imprimir(); } } Véase también
Enlaces externos
- Estructuras de datos/Pilas y colas, en Wikibooks (inglés)
- Distintas implementaciones del manejo de pilas en RosettaCode.org
- Implementación en java desde: trabajosdeotrosparalau.blogspot.com