martes, 4 de octubre de 2011

Pilas












Concepto


 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).

Aplicaciones

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. Por ejemplo:

                                         3 + 4 * (8 – 2 * 5)


  5                
 -2                           -10            
  8                              8                               - 2    
  4                              4                                 4                             -8  
  3                              3                                 3                               3                   -5




Operaciones básicas de las pilas

Vamos a estudiar las principales operaciones a realizar sobre una pila, insertar y borrar.

Insertar

En primer lugar hay que decir que esta operación es muy comúnmente denominada push.
La inserción en una pila se realiza en su cima, considerando la cima como el último elemento insertado. Esta es una de las particularidades de las pilas, mientras el resto de estructuras de datos lineales se representan gráficamente en horizontal, las pilas se representan verticalmente. Por esta razón es por lo que se habla de cima de la pila y no de cola de la cima. Aunque en el fondo sea lo mismo, el último elemento de la estructura de datos.
Las operaciones a realizar para realizar la inserción en la pila son muy simples, hacer que el nuevo nodo apunte a la cima anterior, y definir el nuevo nodo como cima de la pila.
Vamos a ver un ejemplo de una inserción:
Pila: Cabeza 3, 76, -6
Al insertar sobre esta pila el elemento 0, la pila resultante sería:
Pila: Cabeza 0, 3, 76, -6

Borrar

Esta operación es normalmente conocida como pop.
Cuando se elimina un elemento de la pila, el elemento que se borra es el elemento situado en la cima de la pila, el que menos tiempo lleva en la estructura.
Las operaciones a realizar son muy simples, avanzar el puntero que apunta a la cima y extraer la cima anterior.
Si aplicamos la operación pop a la pila de 4 elementos representada arriba el resultado sería:
Pila: Cabeza 3, 76, -6. Eliminado el 0




No hay comentarios:

Publicar un comentario