Pilas - Stack

Concepto

Una pila es un tipo de estructura de datos de entradas ordenadas, donde, solo se podrán insertar y eliminar datos o elementos de la pila por un mismo extremo, al cual se le conoce como cima o tope. Al igual que los arreglos las pilas son estructuras de datos lineales, ya que, sus elementos ocupan espacios sucesivos en su estructura, además cada uno de sus elementos cuenta con un único sucesor (elemento siguiente) y predecesor (elemento anterior) a excepción del primer y ultimo elemento de la pila. En una estructura de datos de tipo pila solo se pueden añadir y eliminar nodos desde su parte superior. Por tal motivo se le conoce como estructura LIFO (last-input, first-output) el ultimo en entrar será el primero en salir.

A continuación un ejemplo sencillo sobre pilas.

En el ejemplo anterior se observa una torre de panqueques donde el primer panqueque listo será también el primero en ser colocado sobre el plato, no obstante, a medida que un nuevo panqueque esté listo se irá apilando sobre el anterior formando así una torre cada vez más grande.

- Nótese la forma en que se colocan los panqueques, a esto se llama, apilar.

- Nótese también como se sacan los panqueques, a esto otro se llama, desapilar.

Al aplicar pilas solo hay un punto por donde se inserta o quita un elemento, este punto es el tope, de allí el primero que entra ultimo que sale.

Declaración

Para declarar una pila en C++, es necesario crear una estructura Nodo. Dicha estructura esta constituida por dos partes, la primera corresponde al dato o los datos que se vayan a almacenar en la pila, y la segunda corresponde a la referencia, es decir, un apuntador al Nodo siguiente.

struct Nodo{

//dato(s)

int dato;

//apuntador al nodo siguiente

Nodo *siguiente;

};

Debajo de la estructura Nodo, es importante declarar un puntero referencial al cual se denominará *cima, que servirá para contralar justamente el tope de la pila, a cima se le asigna NULL por defecto.

El resultado quedaría así:

struct Nodo{

//dato(s)

int dato;

//apuntador al nodo siguiente

Nodo *siguiente;

};

Nodo *cima = NULL;

Operaciones Básicas

Insertar

Crear espacio en memoria para almacenar un nodo: Antes de crear el espacio en memoria para el nodo se debe crear una variable tipo nodo que sera puntero y se le denominara "cima" y será igualada a "NULL". Por ejemplo: Cuando tenemos contadores siempre se inicializan en 0, de esta forma se le indica a la variable puntero que está vacía. Ahora se crea una nueva variable puntero que se llama "nuevoNodo" y se reserva memoria con "New" para un nuevo nodo en especifico:

Nodo *nuevoNodo = New Nodo();

(Diagrama 1)

Cargar el valor dentro del nodo: Una vez reservado el espacio en memoria para un nodo, se le debe asignar el parametro del dato.

nuevoNodo->dato=valor;

(Diagrama 2)

Cargar el puntero cima dentro del nodo: Ahora se debe rellenar el parámetro del putero de la siguiente manera:

nuevoNodo->siguiente=cima;

Tomando en cuenta que cima es "NULL", esto indica que el nuevo nodo será el último nodo en la pila, ya que no hay ningún otro nodo después de él.

(Diagrama 3)

Asignar el nuevo nodo a la cima: Por el momento "cima" no está señalando a nada, por lo que cima es igualado a "nuevoNodo"

cima=nuevoNodo;

"cima" se utiliza para hacer referencia al nodo más reciente o último agregado a la pila. Al asignar "nuevoNodo" a "cima", se establece que el nuevo nodo es el último nodo de la pila, convirtiéndose así en la nueva cima.

(Diagrama 4)

Eliminar

Crear una variable auxiliar de tipo Nodo: Antes de crear la variable auxiliar, primero se verifica con una condicional si la pila esta vacía indicando, si "cima" es "NULL", entonces imprime un mensaje de que "la pila esta vacía" y termina el proceso, pero si no es el caso entonces, se necesita crear un nodo auxiliar puntero de tipo nodo y señalar a "cima"

Nodo *actual = cima;

Haciendo que "actual" señale hacía donde "cima" señala, ambos estarían apuntando al tope de la pila

(Diagrama 1)

(Diagrama 2)

Bajar un nivel en la pila: Cuando se ejecuta la línea de código:

cima = cima -> siguiente;

Se está actualizando "cima" para que apunte al siguiente nodo en la pila. En otras palabras, se "baja" un nivel en la pila.

(Diagrama 3)

Igualar el valor eliminado al dato: Posteriormente el valor a eliminar se almacena en una variable de la siguiente manera:

ValorEliminado = actual -> dato;

Se asigna el valor del miembro "dato" del nodo "actual" a la variable "ValorEliminado". Esto significa que se guarda el valor del nodo que se eliminó de la pila en la variable `ValorEliminado`

(Diagrama 4)

Eliminar el auxiliar "actual": El espacio en memoria fue creado con "New", por lo que se usa "delete" para eliminar el nodo:

(Diagrama 5) (Tachar con una X el nodo actual)

Quedando de la siguiente manera:

(Diagrama 6)

Imprimir

1- Se comprueba si la pila está vacía. Si está vacía, la función imprime "La pila está vacía" y devuelve. Esto se debe a que no hay elementos que mostrar si la pila está vacía.

2- Se crea un puntero actual que apunte a la cima de la pila. La cima de la pila es el primer elemento en la pila.

3- Se emplea un bucle while para iterar a través de los elementos de la pila. El bucle se ejecuta mientras el puntero actual no sea NULL.

4- Dentro del bucle, la función imprime el valor del dato en el puntero actual. El valor del dato es el valor del elemento actual en la pila.

5- Siguiendo dentro del bucle se mueve el puntero actual al siguiente nodo en la pila. Esto se hace para que la función pueda imprimir el siguiente elemento en la pila en el siguiente iteración del bucle.

Buscar

1- Se crea un puntero actual que apunte a la cima de la pila. La cima de la pila es el primer elemento en la pila.

2- Se emplea un bucle while para iterar a través de los elementos de la pila. El bucle se ejecuta mientras el puntero actual no sea NULL.

3- Dentro del bucle, el contador se incrementará en 1 hasta dar con el valor deseado en el caso que exista.

4- Si el valor del dato en el puntero actual es igual al valor ingresado por el usuario, la variable encontrado se establece a true y la variable posicion se establece al valor del contador. Luego, se imprime un mensaje al usuario indicando la posición del valor encontrado.

5- El puntero actual se mueve al siguiente nodo en la pila.

6- Si la variable encontrado es false, se imprime un mensaje al usuario indicando que el valor no existe.

Ejemplo de Pilas en C++