Pilas Programación

República Bolivariana de Venezuela

Ministerio del Poder Popular para la Educación Superior

U.P.T.P “Luis Mariano Rivera”

P.N.F en Informática

Pilas

Carúpano; Enero de 2014

INTRODUCCION

Las pilas son conjuntos son conjuntos de elementos ordenado, en los cuales en un extremo se puede sumar o eliminar. Según la definición estos nuevos elementos se colocan en la parte superior de la pila, el TOPE puede moverse hacia arriba para dar lugar a un nuevo elemento o puede moverse hacia abajo para la eliminación de un elemento. Los cambios que se pueden realizar en las pilas tienen nombres especiales como “push” y “pop” que viene refiriéndose al agregar o eliminar una pila.

Definición;

Las pilas son estructuras de datos que tienes dos operaciones básicas: push (para insertar un elemento) y pop (para extraer un elemento). Su característica fundamental es que al extraer se obtiene siempre el último elemento que acaba de insertarse. Por esta razón también se conocen como estructuras de datos LIFO (del inglés Last In First Out). Una posible implementación mediante listas enlazadas sería insertando y extrayendo siempre por el principio de la lista. Gracias a las pilas es posible el uso de la recursividad (lo veremos en detalle en el tema siguiente). La variable que llama al mismo procedimiento en el q está, habrá que guardarla así como el resto de variables de la nueva llamada, para a la vuelta de la recursividad ir sacandolas, esto es posible a la implementación de pilas.

Las pilas se utilizan en muchas aplicaciones que utilizamos con frecuencia. Por ejemplo, la gestión de ventanas en Windows (cuando cerramos una ventana siempre recuperamos la que teníamos detrás). Otro ejemplo es la evaluación general de cualquier expresión matemática para evitar tener que calcular el número de variables temporales que hacen falta.

Construir un modelo de 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 debe ser del mismo tipo que el elemento, de lo contrario no podrá apuntar hacia el elemento.

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

typedef struct ElementoLista {

char *dato;

struct ElementoLista *siguiente;

}Elemento;

Para permitir las operaciones sobre la pila, vamos a guardar ciertos elementos:

• el primer elemento

• el numero de elementos

El primer elemento, que se encuentra en la cabeza de la pila, nos permitirá realizar la operación de recuperación de los datos situados en la parte superior de la pila. Para ello, será utilizada otra estructura (no es obligatorio, pueden ser utilizadas variables).

typedef struct ListaUbicación{

Elemento *inicio;

int tamaño;

} Pila;

El puntero inicio contendrá la dirección del 1er elemento de la lista. La variable tamaño contiene el numero de elementos.

Cualquiera que sea la posición en la lista, el puntero inicio apunta siempre hacia el 1er elemento, que estará en la cabeza de la pila. El campo tamaño contendrá el numero de elementos de la pila, cualquiera que sea la operación efectuada sobre la pila.

Operaciones con PILA

A. Inicializacion

void inicialización (Pila *tas);

Esta operación debe ser hecha antes de cualquier otra operación sobre la pila. Esta inicializa el puntero inicio con el puntero NULL, y el tamaño con el valor 0. La función:

void inicialización (Pila * tas){

tas->inicio = NULL;

tas->tamaño = 0;

}

B. Inserción de un elemento en la pila

A continuación el algoritmo de inserción y registro de los elementos:

• declaración del elemento a insertar

• asignación de la memoria para el nuevo elemento

• rellenar el contenido del campo de datos

• actualizar el puntero inicio hacia el 1er elemento (la cabeza de la pila)

• Actualizar el tamaño de la pila.

Modelo de la función:

int apilar (Pila *tas, char *dato);

La primera imagen muestra el inicio de la inserción, por lo tanto la lista de tamaño 1 después de la inserción. La característica de la pila no es muy apreciada con un solo elemento, ya que es el único a recuperar.

La función:

/* apilar (añadir) un elemento en la pila */

int apilar (Pila * tas, char *dato){

Elemento *nuevo_elemento;

if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento))) == NULL)

return -1;

if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof (char)))

== NULL)

return -1;

strcpy (nuevo_elemento->dato, dato);

nuevo_elemento->siguiente = tas->inicio;

tas->inicio = nuevo_elemento;

tas->tamaño++;

...