Pilas

De Departamento de Informatica
Saltar a: navegación, buscar

Pilas

Las pilas son un tipo de estructuras de datos lineales (al igual que las listas o colas) y en el cuál, todos los datos son del mismo tipo.

La propiedad especial de las pilas y que las diferencia del resto de las estructuras de datos es que los elementos (o datos) ingresan por un extremo de la estructura, y para obtener o eliminar datos, se obtienen o eliminan por el mismo extremo, es por esto que a las Pilas se les denominan LIFO (Last In First Out), es decir, el primer elemento en ingresar es el último en salir (lógicamente, pues como se ve en la imagen que viene a continuación, el primer elemento en ingresar queda en la parte "mas abajo" de la pila). Esto puede ser representado de la siguiente manera:

Stack.gif

Funciones propias de una Pila

Las pilas tienen ciertas funciones que deben estar en toda pila y que las caracterizan, estas son:

  • Push: Ingresa un elemento a la pila (por un extremo).
  • Pop: Saca un elemento de la pila (por el mismo extremo).

Por la forma en que trabaja pop, se puede uno dar cuenta de que el ultimo elemento en ser ingresado va a ser el primero en ser retirado de esta. También imporante es que la función Pop de la pila borre el elemento de la pila.

Opcionalmente se puede tener una función “get” que retorne el primer valor disponible de la pila sin necesidad de borrarlo, pero esto no es obligación.

El acceso aleatorio a la pila no esta permitido, pues recordar que la principal propiedad de la pila es el ingreso, obtencion y retirada de datos por un sólo lado de la estructura.

Implementaciones de una Pila

La pila puede ser implementada principalmente de 2 formas:

  • Por medio de un arreglo.
  • Por el uso de nodos enlazados por medio de punteros.

La idea es no implementar una pila por medio de un arreglo, incluso si se tiene pensado ir modificando el tamaño de dicho arreglo dinámicamente, sino que lo ideal, es implementarla por medio de una lista de nodos enlazados por punteros. Esto es representado graficamente así:

Stacks-dynamic clip image002.jpg

La idea de esto es poder generar los nodos de manera dinámica a medida que se vayan necesitando, y no gastar memoria que quizás nunca será utilizada.

La forma de esto implementar esto es, como se dijo anteriormente, por medio de punteros. Cada uno apunta al siguiente nodo y asi se puede obtener una lista enlazada. Se puede uno dar cuenta en la imágen de arriba que los datos no estan colocados contiguamente, esto es porque al generarse la memoria de manera dinámica, y es por esto que se utilizan los punteros, para guardar la dirección de memoria del nodo siguiente.

Cabe mencionar como dato imporante, que las pilas son un tipo especial de lista, al igual que la cola.

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas