Pilas en C
Las pilas o stacks son estructuras de datos que tienen una característica, los elementos de la pila o stack se agregan y se sacan desde el tope de la misma y solo desde el tope, lo que desemboca en lo que llamaremos la política de la pila:
“Último en entrar, primero en salir”.
Para llevar esto al mundo real podemos pensar en una pila de platos, cuando los vamos a guardar empezamos a colocar uno encima del otro, formando la pila.
Luego cuando queramos sacar los platos tendremos que hacerlo desde el tope, entonces el ultimo plato que colocamos para formar la pila, sera el primer plato que sacaremos para des hacerla.
Operaciones de la Pila
Las pilas tienen algunas operaciones básicas que rigen su uso, a saber:
- new (crear): esta operación crea e inicializa una pila haciendo posible el empezar a usarla.
- push (encolar): con esta operación agregamos un elemento a la pila, haciendo que la cantidad de elementos dentro de la pila ascienda en uno.
- pop (desencolar): con esta operación sacamos un elemento de la pila (el último) y decrementamos la cantidad de elementos de la pila en uno.
- isEmpty (estaVacia): esta operación tiene una respuesta booleana y da verdadero cuando la pila está vacía y falso cuando no.
- isFull(estaLlena): esta operación tiene una respuesta booleana y da verdadero cuando la pila está llena y falso cuando no.
- count (cuenta): nos dice cuántos elementos hay almacenados en la pila.
No importa que tipo de elementos contenga nuestra pila, las operaciones son exactamente iguales. De la misma forma que en el mundo real no importa si la pila es de platos, libros, cajas, revistas, periódicos… siempre colocamos el último elemento al tope de la pila, y ese último elemento es el primero que vamos a tomar a la hora de sacar.
Ahora bien si deseamos abstraer una pila a cualquier lenguaje de programación debemos también respetar la regla o política de la pila, e implementar sus operaciones básicas.
Implementación en C
Lo primero que tenemos que tener claro es que las pilas no son estructuras de datos fundamentales como los arreglos o variables. Las pilas hacen uso de estos tipos de datos para ser implementadas.
Esta primera aproximación de la implementación de pilas la llamaremos pilas estáticas:
Pilas estáticas
Se les llama pilas estáticas puesto que su tamaño se define al momento de su creación y no puede ser cambiado luego. Este tipo de pilas se implementa con arreglos.
En este caso tenemos el código para crear una pila, en esta implementación hacemos uso de estructuras para representar tanto los elementos como la pila misma, puesto que brindan bastante contención, tenemos todos los datos inherentes a la pila en una sola estructura de datos.
La implementación de la función de creación de la pila esta a partir de la línea 64 como puede verse lo primero que hacemos es validar que el parámetro que nos da el usuario sea el correcto, es decir, sea un número positivo mayor a cero, si esto es así, retornamos el valor de nulo, para indicar que la entrada fue errónea.
Ahora bien, para introducir un elemento en la pila la implementación está a partir de la línea 79, nótese la importancia de la validación de los parámetros de entrada. También hay que notar que antes de hacer la introducción del elemento en la pila hay que corroborar que la pila no esta llena. Si la pila no está llena sencillamente se incluye el elemento.
Sacar un elemento de la pila está implementado desde la línea 103 nuevamente, en las líneas 107 y 109 lidiamos con un elemento vacío y una pila vacía, de resultar esos los casos nótese que retorna mensajes de error en forma de números negativos.
Las siguientes implementaciones nos permiten conocer si la pila está llena o vacía.
Y por último en la linea 139 tenemos una función que nos retorna la cantidad de elementos en la pila.
Pilas dinámicas
Las pilas dinámicas trabajan en estructuras que se enlazan para formar la pila, como crear estas estructuras solo depende de la cantidad de memoria de la que dispone nuestra máquina podemos crear y enlazar casi tantas como queramos. De ahí el nombre de dinámicas.
Esta implementación de la pila cuenta con todas las funcionalidades de la pila estática menos la función isFull, puesto que no tiene sentido. La pila dinámica no posee límite definido de elementos.
La parte interesante está en la línea 76 que es donde creamos el nuevo elemento a introducir en la pila. Notemos aún y cuando el usuario nos proporcionó un elemento nosotros creamos uno nuevo para introducir en la pila, así aislamos la pila de cualquier influencia externa.
La llamada a función malloc devuelve NULL si no le es posible asignar un espacio de memoria contigua para suplir nuestra petición. En este caso retornamos un valor de -1 para indicar que la función falló.
Nota final
Implementaciones de pilas existen muchísimas, estas a penas son un par de estas. Adelante, intenta implementar tu propia pila estática y dinámica.
