Push en una Pila

Cuando nos explican el concepto de Pilas lo principal es que: "el primero que entra es el primero que sale":

con esto parece que tenemos toda la teoría aprendida, el problema viene cuando intentamos implementarlo y no sabemos por dónde empezar.

Por lo general cuando se explica este tema se hace en C++ y utilizando estructuras, por tanto antes de continuar esta explicación os recomiendo leer previamente el post relacionado a estructuras

Vemos en la imagen que cada elemento de la pila está formado por un círculo con un valor y una flecha que lo une con el siguiente círculo, con estos dos elementos formaremos un elemento de la Pila, de esta forma:

struct ElemPila{
  int valor; //esto representa el valor que está dentro del círculo
  struct ElemPila * siguienteElem; //esto representa la flecha, observar que es un puntero
};

Hasta aquí tenemos definida la estructura, pero aún no la estamos utilizando, ahora veremos como desde el programa utilizamos esta esta estructura para agregar los elementos: 1, 2 y 3:

int main()
{
  / /Creamos el primer elemento, con valor 1 y la flecha que apunta al siguiente elemento apunta a NULL
   struct ElemPila* elem1 = new ElemPila; //reserva memoria para el contenido de la estructura
   elem1->valor = 1; //inicializa el valor de la estructura
   elem1->siguienteElem = NULL; //inicializa el valor hacia donde apunta el siguiente
   
   struct ElemPila* elem2 = new ElemPila;
   elem2->valor = 2;
   elem2->siguienteElem = NULL;
   
   struct ElemPila* elem3 = new ElemPila;
   elem3->valor = 3;
   elem3->siguienteElem = NULL;
      
   return 0;
}

Al ejecutar este programa lo que logramos es tener 3 elementos independientes, así:

Como paso siguiente modificaremos el programa para introducir el puntero que será cabeza de la pila e introduciremos sólo el primer elemento a la pila:

int main()
{
   struct ElemPila* elem1 = new ElemPila;
   elem1->valor = 1;
   elem1->siguienteElem = NULL;
   
   struct ElemPila* elem2 = new ElemPila;
   elem2->valor = 2;
   elem2->siguienteElem = NULL;
   
   struct ElemPila* elem3 = new ElemPila;
   elem3->valor = 3;
   elem3->siguienteElem = NULL;
   
   struct ElemPila* cabezaPila; //creamos el puntero
   cabezaPila = elem1; //hacemos que apunte al primer elemento
   
   return 0;
}

Para incluir el segundo elemento en la pila, lo que tenemos que hacer es que el segundo elemento apunte al primero (elem1) y la cabeza de pila apunte al segundo:

int main()

{

   struct ElemPila* elem1 = new ElemPila;

   elem1->valor = 1;

   elem1->siguienteElem = NULL;

   struct ElemPila* elem2 = new ElemPila;

   elem2->valor = 2;

   elem2->siguienteElem = NULL;

   struct ElemPila* elem3 = new ElemPila;

   elem3->valor = 3;

   elem3->siguienteElem = NULL;

   struct ElemPila* cabezaPila;

   cabezaPila = elem1;

   elem2-> siguienteElem = cabezaPila;

   cabezaPila = elem2;

   return 0;

}

Finalmente incluimos el tercer elemento, siguiendo los mismo pasos que el anterior, que es hacer que el siguiente de elemento 3 apunte al elemento 2 y la cabeza de la pila apunte a elemento 3:

int main()

{

   struct ElemPila* elem1 = new ElemPila;

   elem1->valor = 1;

   elem1->siguienteElem = NULL;

 

   struct ElemPila* elem2 = new ElemPila;

   elem2->valor = 2;

   elem2->siguienteElem = NULL;

 

   struct ElemPila* elem3 = new ElemPila;

   elem3->valor = 3;

   elem3->siguienteElem = NULL;

 

   struct ElemPila* cabezaPila;

   cabezaPila = elem1;

 

   elem2->siguienteElem = cabezaPila;

   cabezaPila = elem2;

 

   elem3->siguienteElem = cabezaPila;

   cabezaPila = elem3;

 

   return 0;

}

Si observamos atentamente el código y las imágenes veremos que las variables elem1 y elem2 se quedan apuntando a elementos de la pila que en teoría no se deberían acceder directamente (el acceso es sólo con la cabeza de pila), por tanto podríamos deducir que con una sola variable de tipo ElemenPila sería suficiente. De la misma forma podemos observar en el código que el mecanismo para agregar un elemento es el mismo, por lo tanto podríamos utilizar una función para reutilizar el código. todo esto de esta forma:

#include <iostream>

struct ElemPila{

  int valor;

  struct ElemPila * siguienteElem;

};

using namespace std;

//incluimos una función de impresión para comprobar el orden en que se han guardado

void imprimir(struct ElemPila* cabezaPila)

{

    struct ElemPila* auxiliar = cabezaPila;

    while(auxiliar != NULL)

    {

      cout << auxiliar->valor << " - ";

      auxiliar = auxiliar -> siguienteElem;

    }

    cout << "=====================\n";

}

//función que realiza el push de forma genérica para cualquier elemento

struct ElemPila* push(int pValor, struct ElemPila* elem, struct ElemPila* cabezaPila)

{

   elem = new ElemPila;    

   elem->valor = pValor;

   elem->siguienteElem = NULL;

   elem->siguienteElem = cabezaPila;

   cabezaPila = elem;

   return cabezaPila;

}

int main()

{

   struct ElemPila* cabezaPila = NULL;

   struct ElemPila* elem = NULL;

   cabezaPila = push(1, elem, cabezaPila);   

   imprimir(cabezaPila);

       

   cabezaPila = push(2, elem, cabezaPila);   

   imprimir(cabezaPila);

   

   cabezaPila = push(3, elem, cabezaPila);   

   imprimir(cabezaPila);

   

   return 0;

}

Executing the program....

1 - =====================
2 - 1 - =====================
3 - 2 - 1 - =====================