Pila

Pilas


Introducción.
Una pila (stack) es una lista ordinal o estructura de datos en la que el
modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First
Out, último en entrar, primero en salir) que permite almacenar y
recuperar datos solo por uno de los extremos. En consecuencia, los
elementos de una pila serán retirados en orden inverso al que se
insertaron.

Lasutilidades de esta estructura son bastantes, entre ellas está la
construcción de calculadoras, simulación de recursión o recorrido
de arboles por niveles entre muchas otras cosas más.
Para el manejo de los datos se cuenta con dos operaciones
básicas: apilar (push), que coloca un objeto en la pila, y su operación
inversa, retirar (o desapilar, pop), que retira el último elemento apilado.

Encada momento sólo se tiene acceso a la parte superior de la pila, es decir,
al último objeto apilado (denominado TOS, Top of Stack en inglés). La

operación retirar permite la obtención de este elemento, que es retirado
de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que
pasa a ser el nuevo TOS.

Una metáfora que se utiliza con frecuencia es la idea de una pila deplatos
en una cafetería con muelle de pila.
En esa serie, sólo la primera placa es visible y accesible para el usuario,
todas las demás placas permanecen ocultas. Como se añaden las nuevas
placas, cada nueva placa se convierte en la parte superior de la pila. A
medida que la placa superior se elimina de la pila, la segunda placa se
convierte en la parte superior de la pila.
Dos principiosimportantes son ilustrados por esta metáfora:
En primer lugar la última salida es un principio, la segunda es que el
contenido de la pila está oculto. Sólo la placa de la parte superior es visible,
por lo que para ver lo que hay en la tercera placa, el primer y segundo
platos tendrán que ser retirados.

Operaciones
Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar.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.

Pseudocódigo de los métodos push y pop

Este algoritmo almacena el valor dato en la pila manejando la variabletope como
el puntero del último elemento.
max es el numero máximo de elementos que puede almacenar la pila
push(pila, max, tope, dato)
si tope < max entonces //solo si deseamos manejar un límite de elementos en la pila
tope=tope + 1
si no, no es necesario
pila[tope]=dato
//almacena un nuevo elemento en el siguiente espacio disponible
si no
escribir “La pila esta llena”
fin //si tope pop(pila, tope, dato)
Fin //del método
si tope>0 entonces //vemos si hay elementos en la pila
dato=pila[tope]
tope=tope-1
si no
escribir “Ya no hay elementos en la pila
fin //si tope>0
Fin //del método

Para la implementación se he elegido
una lista enlazada simple.
Ya que la inserción es siempre hecha
al inicio de la lista, el 1er elemento de

la lista será el ultimo elementoingresado, por lo tanto estará en la
cabeza de la pila y será el 1er

elemento ha recuperar.

La construcció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 debe ser del mismo tipo que el elemento, de lo
contrario no podrá apuntar hacia elelemento.
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 1er elemento, que se encuentra en la cabeza de la pila, TOS.
typedef struct ListaUbicación...

Leer documento completo

Regístrate para leer el documento completo.