PILAS

¨

    Una pila es una estructura de datos a la cual se puede acceder solo por un extremo de la misma. Las operaciones de inserción y extracción se realizan a través del tope, por lo cual no se puede acceder a cualquier elemento de la pila. Se le suele llamar estructura L.I.F.O. como acrónimo de las palabras inglesas "last in, first out" (último en entrar, primero en salir). La pila se considera un grupo ordenado de elementos, teniendo en cuenta que el orden de los mismos depende del tiempo que lleven "dentro" de la estructura.

     La pila debe pensarse como una resma de hojas sobre un escritorio, con sólo dos posibles operaciones básicas: apilar (agregar o push) y desapilar (sacar o pop). Se agregan hojas una sobre la otra, y se retiran desde arriba hacia abajo. Esto significa que en todo momento, sólo se puede acceder directamente al último elemento agregado (el que está más arriba en la pila, que es llamado TOS).

Pila de llamadas

La Pila de llamadas es un segmento de memoria que utiliza esta estructura de datos para almacenar información sobre las llamadas a subrutinas actualmente en ejecución en un programa en proceso.

Cada vez que una nueva subrutina es llamada, se apila una nueva entrada con información sobre ésta tal como sus variables locales. En especial, se almacena aquí el punto de retorno al que regresar cuando esta subrutina termine (para volver a la subrutina anterior y continuar su ejecución después de esta llamada).

¨

¨Pila como tipo abstracto de datos

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. 'Pop' elimina y devuelve el actual nodo superior de la pila.

¨Operaciones

Crear: se crea la pila vacía.

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á vacía o falso en caso contrario.

¨Implementación

Un requisito típico de almacenamiento de una pila de n elementos es O(n). El requisito típico de tiempo de O(1) las operaciones también son fáciles de satisfacer con un array o con listas enlazadas simples.

La biblioteca de plantillas de C++ estándar proporciona una "pila" clase templated que se limita a sólo apilar/desapilar operaciones. Java contiene una biblioteca de la clase Pila que es una especialización de Vector. Esto podría ser considerado como un defecto, porque el diseño heredado get () de Vector método LIFO ignora la limitación de la Pila.

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

¨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         OPERACION                 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.

¨Ejemplo de pila en C

Supongamos que queremos construir una pila para almacenar números enteros. Haremos pruebas intercalando varios "push" y "pop", y comprobando el resultado.

Algoritmo de la función "push"

Creamos un nodo para el valor que colocaremos en la pila.

Hacemos que nodo->siguiente apunte a Pila.

Hacemos que Pila apunte a nodo.

void Push(Pila *pila, int v) \{

  pNodo nuevo;

 /* Crear un nodo nuevo */

   nuevo = (pNodo)malloc(sizeof(tipoNodo));

   nuevo->valor = v;

  

   /* Añadimos la pila a continuación del nuevo nodo */

   nuevo->siguiente = *pila;

   /* Ahora, el comienzo de nuestra pila es en nuevo nodo */

   *pila = nuevo;

}

¨

Algoritmo de la función "pop"

¨

Hacemos que nodo apunte al primer elemento de la pila, es decir a Pila.

Asignamos a Pila la dirección del segundo nodo de la pila: Pila->siguiente.

Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación pop equivale a leer y borrar.

Liberamos la memoria asignada al primer nodo, el que queremos eliminar.

   int Pop(Pila *pila) \{

   pNodo nodo; /* variable auxiliar para manipular nodo */

   int v;      /* variable auxiliar para retorno */

  

   /* Nodo apunta al primer elemento de la pila */

   nodo = *pila;

   if(!nodo) return 0; /* Si no hay nodos en la pila retornamos 0 */

   /* Asignamos a pila toda la pila menos el primer elemento */

   *pila = nodo->siguiente;

   /* Guardamos el valor de retorno */

   v = nodo->valor;

   /* Borrar el nodo */

   free(nodo);

   return v;

}