Cómo programar las pilas en lenguaje C

El objetivo de este artículo es que el lector entienda el empleo de las pilas. Para explicar el algoritmo utilizaremos una lista enlazada simple. Por lo tanto la comprensión de las listas enlazadas es necesaria.

¿Cuáles son los requisitos?

Los requisitos son los tipos de datos, las estructuras, el uso de typedef, los punteros, las funciones de usuario, las listas simplemente enlazadas, las listas doblemente enlazadas.

¿Cuál es la definición de una pila?

• La pila es una estructura de datos que permite almacenar datos en el orden LIFO (Last In First Out)
• La recuperación de los datos es realizada en el orden inverso de su inserción.
• Para la implementación hemos elegido una lista enlazada simple, presentada sobre la vertical.

Ya que la inserción es siempre hecha al inicio de la lista, el primer elemento de la lista será el último elemento ingresado, por lo tanto estará en la cabeza de la pila. No hemos utilizado un puntero fin, como en el caso de la lista enlazada simple, ya que el objetivo no es el de tratar una lista enlazada, sino una pila.

Lo interesante es que el último elemento ingresado, será el primer elemento recuperado:

¿Cómo elaborar el 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 tiene que ser de la misma clase que el elemento, de lo contrario no va a poder 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 primero y el número 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, se utilizará otra estructura (no es obligatorio, pueden ser utilizadas variables):

typedef struct ListaUbicación{
  Elemento *inicio;
  int tamaño;
} Pila;

El puntero inicio indicará la dirección del primer elemento de la lista. La variable tamaño contiene el número de elementos.

Nota: Esta vez no utilizamos un puntero fin (ver la lista enlazada simple). No lo necesitamos puesto que únicamente trabajamos al inicio de la lista.

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

¿Cuáles son las operaciones sobre las pilas?

Inicialización

Modelo de la función:

void inicialización (Pila *tas);

Esta operación debe ser realizada antes que 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;
}

Inserción de un elemento en la pila

A continuación, veremos el algoritmo de inserción y el registro de los elementos: declaración del elemento que va a insertarse, asignación de la memoria para el siguiente elemento, introducir el contenido del campo de los datos, actualizar el puntero inicio hacia el primer 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 comienzo 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:

En cambio la segunda imagen nos permite observar el comportamiento de la pila. Lo que debemos retener es que la inserción siempre se hace en la parte superior de la pila (al inicio de la lista):

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++;
}

Eliminar un elemento de la pila

Para eliminar un elemento de la pila, simplemente hay que eliminar el elemento hacia el cual apunta el puntero inicio. Esta operación no permite recuperar el dato en la cabeza de la pila, solo eliminarlo.

Modelo de la función:

int desapilar (Pila *tas);

La función da como resultado -1 en caso de error, si no devuelve 0.

Las etapas:

El puntero sup_elemento contendrá la dirección del primer elemento.

El puntero inicio apuntará hacia el segundo elemento (después de la eliminación del primer elemento, el segundo elemento estará en la cabeza de la pila).

El tamaño de la pila disminuirá un elemento:

La función:

int desapilar (Pila * tas){
  Elemento *sup_elemento;
  if (tas->tamaño == 0)
    return -1;
  sup_elemento = tas->inicio;
  tas->inicio = tas->inicio->siguiente;
  free (sup_elemento->dato);
  free (sup_elemento);
  tas->tamaño--;
  return 0;
}

Visualización de la pila

Para mostrar la pila entera, es necesario posicionarse al inicio de la pila (el puntero inicio lo permitirá). Luego, utilizando el puntero siguiente de cada elemento, la pila es recorrida del primero hacia el último elemento. La condición para detenerse es determinada por el tamaño de la pila.

La función:

/* visualización de la pila */
void muestra (Pila * tas){
  Elemento *actual;
  int i;
  actual = tas->inicio;

  for(i=0;i<tas->tamaño;++i){
    printf("\t\t%s\n", actual->dato);
    actual = actual->siguiente;
  }
}

Recuperación del dato en la cabeza de la pila

Para recuperar el dato en la cabeza de la pila sin eliminarlo, he utilizado una macro. La macro lee los datos en la parte superior de la pila utilizando el puntero inicio.

#define pila_dato(tas)  tas->inicio->dato

¿Cuál es un ejemplo completo?

pila.h

/*          pila.h         */

typedef struct ElementoLista{  
char *dato;  
struct ElementoLista *siguiente;} Elemento;
typedef struct ListaUbicación{  
Elemento *inicio;  
int tamaño;} Pila;

/* inicialización */
void inicialización (Pila *tas);

/* APILAR*/
int apilar (Pile *tas, char *dato);

/* DESAPILAR*/
int desapilar (Pila *tas);

/* Visualización del elemento en la cabeza de la pila (LastInFirstOut) */
#define pila_dato(tas)  
tas->inicio->dato

/* muestra la pila */
void muestra (Pila *tas);

pila_function.h

/*          pila_function.h         */

void inicialización (Pila * tas){  
tas->inicio = NULL;  
tas->tamaño = 0;}

/* 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++;
}

/* desapilar (eliminar un elemento de la pila) */
int desapilar (Pila * tas){  
Elemento *sup_elemento;  
if (tas->tamaño == 0)    return -1;  
sup_elemento = tas->inicio;  
tas->inicio = tas->inicio->siguiente;  
free (sup_elemento->dato);  
free (sup_elemento);  
tas->tamaño--;  
return 0;
}

/* visualización de la pila */
void muestra (Pila * tas) 
{  
Elemento *actual;  
int i;  
actual = tas->inicio;  
for(i=0;i<tas->tamaño;++i) 
{    
printf("\t\t%s\n", actual->dato);    
actual = actual->siguiente;  
}
}

pila.c

/*          pila.c         */

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "pila.h"
#include "pila_function.h"
int main () {  
Pila *tas;  
char *nom;  
if ((tas = (Pila *) malloc (sizeof (Pila))) == NULL)    return -1;  
if ((nom = (char *) malloc (50 * sizeof (char))) == NULL)    return -1;  
inicialización (tas);  
printf ("Ingrese una palabra: ");  
scanf ("%s", nom);  
apilar (tas, nom);  
printf ("La pila (%de elementos): \n",tas->tamaño);  
printf("\n********** Cabeza de la PILA **********\n");  
muestra(tas);  
printf("__________ Bajo de la PILA __________\n\n");  
printf ("Ingrese una palabra: ");  
scanf ("%s", nom);  
apilar (tas, nom);  
printf ("La pila (%de elementos): \n",tas->tamaño);  
printf("\n********** Cabeza de la PILA **********\n");  
muestra(tas);  
printf("__________ Bajo de la PILA __________\n\n");  
printf ("Ingrese una palabra: ");  
scanf ("%s", nom);  
apilar (tas, nom);  
printf ("La pila (%de elementos): \n",tas->tamaño);  
printf("\n********** Cabeza de la PILA **********\n");  
muestra(tas);  
printf("__________ Bajo de la PILA __________\n\n");  
printf ("\nLa ultima entrada (LastInFirstOut) [ %s ] sera eliminada",                  pile_dato(tas));  printf ("\nLa ultima entrada es eliminada\n");  
desapilar (tas);              

/* eliminación del ultimo elemento ingresado */  
printf ("La pila (%de elementos): \n",tas->tamaño);  
printf("\n********** Cabeza de la PILA **********\n");  
muestra(tas);  
printf("__________ Bajo de la PILA __________\n\n");  
return 0;
}