Ingeniera en Sistemas

**Todo sobre: Pila en programación**

Es una estructura lineal de nodos encadenados donde las inserciones y las eliminaciones se hacen siempre al inicio.. La analogía más común con esta estructura es una pila de platos, si uno va a agregar un plato a la pila pues lo pone al principio, y si va a sacar uno lo saca desde el principio. Bien, en programación simplemente nos ceñimos a eso estrictamente y tenemos una pila. 

Podemos entonces ver a la Pila como una lista encadenada caprichosa que solo admite movimientos en su inicio. Esto, aunque tal vez parezca tonto, resuelve muchos problemas. Piensen en qué hace un programa cuando ustedes eligen la opción Deshacer. Justamente deshace la última acción realizada, y si volvemos a elegir Deshacer pues desharemos la acción inmediata anterior realizada, y así, en el orden inverso al que se fueron realizando. Esto es porque las acciones se van guardando en una pila. Cuando deshacemos se va al inicio de la pila, se ve cuál fue la acción, se hace lo inverso y se quita esa entrada de la pila. 

Esta estructura se conoce como estructura LIFO del inglés Last In First Out que significa Último en Entrar Primero en Salir.

Aplicación de Pilas para determinar si una expresión es correcta.

Las pilas nos permiten realizar tareas de forma “sencilla” que si atacáramos sin ellas sería una masacre, inhumano y todos los adjetivos horribles que se les ocurran. Un ejemplo es verificar si se han abierto y cerrado todos los paréntesis de forma correcta. Una típica tarea de un compilador, ver si hemos abierto y cerrado todos los paréntesis como corresponde. Imaginen esta expresión: [()(())]

Queremos tener un programa que determine si el balance de paréntesis es correcto. En ese ejemplo lo es. ¿Qué se les ocurre? Pues contar la cantidad de símbolos de apertura y compararla con la cantidad de símbolos de cierre no sirve porque ahí no se toma en cuenta el orden en que aparecen.

La cosa es bien fácil, lo primero que se necesita es una pila vacía. Luego se debe leer cada símbolo de la expresión y hacemos lo siguiente:

Si es un símbolo de apertura se coloca en la pila.

Si es un símbolo de cierre se debe ir al tope de la pila.

Si el símbolo que hay es del mismo tipo que el que tenemos, se elimina ese símbolo de la pila y se continúa.

Si el símbolo que hay no es del mismo tipo entonces la expresión es incorrecta.

Al final, si la expresión fuera incorrecta debemos  mirar la pila para determinarlo. Si esta está vacía entonces la expresión era correcta, en otro caso no lo era. A continuación un ejemplo de ejecución de este algoritmo con la expresión anterior:

Leemos el primer símbolo y vimos que era un corchete de apertura, por tanto lo agregamos a la pila.

Leemos el segundo símbolo, como también es de apertura lo enviamos a la pila.

El tercer símbolo es un paréntesis de cierre. Visualizamos el tope de la pila, como allí encontramos justo un paréntesis de apertura entonces lo quitamos y continuamos. Tener en cuenta que ambos símbolos eran del mismo tipo (paréntesis). Si hubiera encontrado un corchete entonces ya estaba mal.

Un paréntesis de apertura, lo agregamos a la pila.

  

La elaboración del modelo de un elemento de la pila

Para definir un elemento de la pila será utilizado el tipo struct:

El elemento de la pila contendrá un campo dato y un puntero siguiente.

El puntero siguiente tiene que ser de la misma clase que el elemento, de lo contrario no va a poder apuntar hacia el elemento.

El puntero siguiente permitirá el acceso al próximo elemento.

typedef struct ElementoLista {

    char *dato;

    struct ElementoLista *siguiente;

}Elemento;

Arquitectura básica de una pila

Una pila típica es un área de la memoria de los computadores con un origen fijo y un tamaño variable. Al principio, el tamaño de la pila es cero. Un puntero de pila, por lo general en forma de un registro de hardware, apunta a la más reciente localización en la pila; cuando la pila tiene un tamaño de cero, el puntero de pila de puntos en el origen de la pila.

Las dos operaciones aplicables a todas las pilas son:

• Una operación apilar, en el que un elemento de datos se coloca en el lugar apuntado por el puntero de pila, y la dirección en el puntero de pila se ajusta por el tamaño de los datos de partida.
• Una operación desapilar: un elemento de datos en la ubicación actual apuntado por el puntero de pila es eliminado, y el puntero de pila se ajusta por el tamaño de los datos de partida.

OPERACIONES

Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.

• Crear: se crea la pila vacía. (constructor)
• Tamaño: regresa el número de elementos de la pila. (size)
• Apilar: se añade un elemento a la pila.(push)
• Desapilar: se elimina el elemento frontal de la pila.(pop)
• Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)
• Vacía: devuelve cierto si la pila está sin elementos o falso en caso de que contenga uno. (empty).

Soporte 

[Hardware Y Software]

Soporte de Hardware

MUCHAS CPUS TIENEN REGISTROS QUE SE PUEDEN UTILIZAR COMO PUNTEROS DE PILA. ALGUNOS, COMO EL INTEL X86, TIENEN INSTRUCCIONES ESPECIALES QUE IMPLÍCITAMENTE EL USO DE UN REGISTRO DEDICADO A LA TAREA DE SER UN PUNTERO DE PILA. OTROS, COMO EL 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 NUMÉRICO DE COPROCESSORS TIENE UN CONJUNTO DE REGISTROS 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 APLICAR 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. Pila también se utilizaron como base de una serie de mainframes y miniordenadores. Esas máquinas fueron llamados pila de máquinas, 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 los posibles valores. Las expresiones pueden ser representadas en prefijo, infijo, postfijo. La conversión de una forma de la 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 el código de bajo nivel. La mayoría de los lenguajes de programación son de contexto libre de los idiomas que les permite ser analizados con máquinas basadas en la pila.

Por ejemplo, el cálculo: ((1 + 2) * 4) + 3, puede ser anotado como en notación postfija con la ventaja de no prevalecer las normas y los paréntesis necesario:

1 2 + 4 * 3 +

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

• Apilar cuando se enfrentan a un operando y
• Desafilar dos operandos y evaluar el valor cuando se enfrentan a una operación.
• Apilar el resultado.

De la siguiente manera (la Pila se muestra después de que la operación se haya llevado a cabo):

 ENTRADA         OPERACIÓN                 PILA
 
 1             Apilar operando             1
 2             Apilar operando             1, 2
 +             Añadir                      3
 4             Apilar operando             3, 4
 *             Multiplicar                 12
 3             Apilar operando             12, 3
 +             Añadir                      15 

El resultado final, 15, se encuentra en la parte superior de la pila al final del cálculo.

Manipulación de información. 

Pilas y Colas

PILA DE LA COMPUTADORA

La pila es una pequeña batería de 3v (a veces 5v) la cual va en la placa madre del PC, la función de la pila tipo botón es entregarle energía continua a la placa madre para que almacene la información de los BIOS y ser guardada en la memoria RAM CMOS, cuando la pila se saca la BIOS se resetean, existen varias pilas virtuales en cuestiones de memoria las utiliza el sistema operativo.

La Pila es propiamente la memoria de la que dispone. Es una estructura de datos de LIFO (Last In, First Out).

Para fines prácticos se podría ver propiamente como un arreglo donde se va introduciendo los datos y de ahí alimenta a los programas que corres en tu maquina.

Por ejemplo, si has trabajado con Windows 98 era muy común el FATAL ERROR de VOLCADO DE PILA. Y no es que la pila de tu PC se estuviese terminando, si no que la memoria había llegado a su limite físico y no podía almacenar mas.

La batería:  Le da energía al Chip del BIOS que es el encargado de administrar la configuración de hardware básica de la computadora, entre otras cosas.