Representación en memoria de una pila

Las pilas no son estructuras de datos fundamentales, es decir, no están definidas como tales en los lenguajes de programación. Las pilas pueden representarse mediante el uso de :

• Arreglos.
• Listas enlazadas.

Nosotros ahora usaremos los arreglos. Por lo tanto debemos definir el tamaño máximo de la pila, además de un apuntador al último elemento insertado en la pila el cual denominaremos SP. La representación gráfica de una pila es la siguiente:

Como utilizamos arreglos para implementar pilas, tenemos la limitante de espacio de memoria reservada. Una vez establecido un máximo de capacidad para la pila, ya no es posible insertar más elementos.

Una posible solución a este problema es el uso de espacios compartidos de memoria. Supongase que se necesitan dos pilas , cada una con un tamaño máximo de n elementos. En este caso se definirá un solo arreglo de 2*n elementos, en lugar que dos arreglos de n elementos.

En este caso utilizaremos dos apuntadores: SP1 para apuntar al último elemento insertado en la pila 1 y SP2 para apuntar al último elemento insertado en la pila 2. Cada una de las pilas insertará sus elementos por los extremos opuestos, es decir, la pila 1 iniciará a partir de la localidad 1 del arreglo y la pila 2 iniciará en la localidad 2n. De este modo si la pila 1 necesita más de n espacios (hay que recordar que a cada pila se le asignaron n localidades) y la pila 2 no tiene ocupados sus n lugares, entonces se podrán seguir insertando elementos en la pila 1 sin caer en un error de desbordamiento.

Fuente: Apunte de Estructura de Datos del Instituto tecnológico de la Paz