Una lista se comporta como una pila si las inserciones y extracciones las hacemos por un mismo lado de la lista. También se las llama listas LIFO (Last In First Out - último en entrar primero en salir)
Importante: Una pila al ser una lista puede almacenar en el campo de información cualquier tipo de valor (int, char, float, vector de caracteres, un objeto, etc.)
Para estudiar el mecanismo de utilización de una pila supondremos que en el campo de información almacena un entero (para una fácil interpretación y codificación)
Inicialmente la PILA está vacía y decimos que el puntero raiz apunta a NULL (Si apunta a NULL decimos que no tiene una dirección de memoria, en realidad este valor NULL es el valor cero):
Insertamos un valor entero en la pila: insertar(10)
Luego de realizar la inserción la lista tipo pila queda de esta manera: un nodo con el valor 10 y raiz apunta a dicho nodo. El puntero del nodo apunta a NULL ya que no hay otro nodo después de este.
Insertamos luego el valor 4: insertar(4)
Ahora el primer nodo de la pila es el que almacena el valor cuatro. raiz apunta a dicho nodo. Recordemos que raiz es el puntero externo a la lista que almacena la dirección del primer nodo.
El nodo que acabamos de insertar en el campo puntero guarda la dirección del nodo que almacena el valor 10.
Ahora qué sucede si extraemos un nodo de la pila. ¿Cuál se extrae? Como sabemos en una pila se extrae el último en entrar.
Al extraer de la pila tenemos: extraer()
La pila ha quedado con un nodo.
Hay que tener cuidado que si se extrae un nuevo nodo la pila quedará vacía y no se podrá extraer otros valores (avisar que la pila está vacía)
Problema 1:
Confeccionar una clase que administre una lista tipo pila (se debe poder insertar, extraer e imprimir los datos de la pila)
Programa:
#include <iostream>
using namespace std;
class Pila {
private:
class Nodo {
public:
int info;
Nodo *sig;
};
Nodo *raiz;
public:
Pila();
~Pila();
void insertar(int x);
int extraer();
void imprimir();
};
Pila::Pila()
{
raiz = NULL;
}
void Pila::insertar(int x)
{
Nodo *nuevo;
nuevo = new Nodo();
nuevo->info = x;
if (raiz == NULL)
{
raiz = nuevo;
nuevo->sig = NULL;
}
else
{
nuevo->sig = raiz;
raiz = nuevo;
}
}
void Pila::imprimir()
{
Nodo *reco = raiz;
cout << "Listado de todos los elementos de la pila.\n";
while (reco != NULL)
{
cout << reco->info << "-";
reco = reco->sig;
}
cout << "\n";
}
int Pila::extraer()
{
if (raiz != NULL)
{
int informacion = raiz->info;
Nodo *bor = raiz;
raiz = raiz->sig;
delete bor;
return informacion;
}
else
{
return -1;
}
}
Pila::~Pila()
{
Nodo *reco = raiz;
Nodo *bor;
while (reco != NULL)
{
bor = reco;
reco = reco->sig;
delete bor;
}
}
void main()
{
Pila *pila1;
pila1= new Pila();
pila1->insertar(10);
pila1->insertar(40);
pila1->insertar(3);
pila1->imprimir();
cout<<"Extraemos de la pila:" <<pila1->extraer()<<"\n";
pila1->imprimir();
cout<<"Retornamos primero de la pila:" <<pila1->retornar()<<"\n";
pila1->imprimir();
delete pila1;
cin.get();
}
Este proyecto lo puede descargar en un zip desde este enlace : Pila1.zip
Analicemos las distintas partes de este programa:
Lo nuevo que vemos en el lenguaje C++ es la posibilidad de declarar clases dentro de otra clase. Esto hace que podamos encapsular una clase para que solo tenga acceso la clase que la contiene:
class Pila {
private:
class Nodo {
public:
int info;
Nodo *sig;
};
Nodo *raiz;
public:
Pila();
~Pila();
void insertar(int x);
int extraer();
int retornar();
void imprimir();
};
La clase Nodo es interna a la clase Pila. Como podemos observar hemos declarado dentro de la clase Nodo dos atributos y los hemos definido de tipo public (lo hacemos public para accederlos directamente y no por medio de un método para que el código generado sea más eficiente y para respetar el encapsulamiento de datos propuesto por la programación orientada a objetos planteamos una clase interna)
Para declarar un nodo dijimos que utilizamos una clase. En este caso la información del nodo (info) es un entero y siempre el nodo tendrá una referencia o puntero de tipo Nodo, que le llamamos sig.
El puntero sig apunta al siguiente nodo o a NULL en caso que no exista otro nodo. Este puntero es interno a la clase Nodo.
También definimos un puntero de tipo Nodo llamado raiz. Este puntero tiene la dirección del primer nodo de la lista. En caso de estar vacía la lista, raiz apunta a NULL (es decir no tiene dirección)
raiz es un puntero externo a la pila y por eso lo definimos fuera de la clase Nodo pero dentro de la clase Pila.
El puntero raiz es fundamental porque al tener la dirección del primer nodo de la lista nos permite acceder a los demás nodos.
Pila::Pila()
{
raiz = NULL;
}
En el constructor de la clase hacemos que raiz guarde el valor NULL. Tengamos en cuenta que si raiz tiene almacenado NULL la lista está vacía, en caso contrario tiene la dirección del primer nodo de la lista.
void Pila::insertar(int x)
{
Nodo *nuevo;
nuevo = new Nodo();
nuevo->info = x;
if (raiz == NULL)
{
raiz = nuevo;
nuevo->sig = NULL;
}
else
{
nuevo->sig = raiz;
raiz = nuevo;
}
}
Uno de los métodos más importantes que debemos entender en una pila es el de insertar un elemento en la pila.
Al método llega la información a insertar, en este caso en particular es un valor entero.
La creación de un nodo requiere dos pasos:
- Definición de un puntero o referencia a un tipo de dato Nodo:
Nodo *nuevo;
- Creación del nodo (creación de un objeto):
nuevo = new Nodo();
Cuando se ejecuta el operador new se reserva espacio para el nodo. Realmente se crea el nodo cuando se ejecuta el new.
Paso seguido debemos guardar la información del nodo (como el atributo info es público luego lo accedemos mediante el operador ->):
nuevo->info = x;
En el campo info almacenamos lo que llega en el parámetro x. Por ejemplo si llega un 5 el nodo queda:
Por último queda enlazar el nodo que acabamos de crear al principio de la lista.
Si la lista está vacía debemos guardar en el atributo sig del nodo el valor NULL para indicar que no hay otro nodo después de este, y hacer que raiz apunte al nodo creado (sabemos si una lista esta vacía si raiz almacena un NULL, es decir el valor que le almacenamos en el constructor)
if (raiz == NULL)
{
nuevo->sig = NULL;
raiz = nuevo;
}
Gráficamente podemos observar que cuando indicamos raiz=nuevo, el puntero raiz guarda la dirección del nodo apuntado por nuevo.
Tener en cuenta que cuando finaliza la ejecución del método el puntero nuevo desaparece, pero no el nodo creado con el operador new.
En caso que la lista no esté vacía, el puntero sig del nodo que acabamos de crear debe apuntar al que es hasta este momento el primer nodo, es decir al nodo que apunta raiz actualmente.
else
{
nuevo->sig = raiz;
raiz = nuevo;
}
Como primera actividad cargamos en el puntero sig del nodo apuntado por nuevo la dirección de raiz, y posteriormente raiz apunta al nodo que acabamos de crear, que será ahora el primero de la lista.
Antes de los enlaces tenemos:
Luego de ejecutar la línea:
nuevo->sig = raiz;
Ahora tenemos:
Por último asignamos a raiz la dirección que almacena el puntero nuevo.
raiz = nuevo;
La lista queda:
El método extraer:
int Pila::extraer()
{
if (raiz != NULL)
{
int informacion = raiz->info;
Nodo *bor = raiz;
raiz = raiz->sig;
delete bor;
return informacion;
}
else
{
return -1;
}
}
El objetivo del método extraer es retornar la información del primer nodo y además borrarlo de la lista.
Si la lista no está vacía (es decir raiz tiene un valor distinto a NULL) guardamos en una variable local la información del primer nodo:
int informacion = raiz->info;
Creamos un puntero auxiliar y hacemos que apunte al nodo que vamos a borrar:
Nodo *bor = raiz;
Avanzamos raiz al segundo nodo de la lista, ya que borraremos el primero (si no hay otro nodo más adelante en raiz se guarda NULL ya que el último nodo de la lista tiene en el puntero sig dicho valor):
raiz = raiz->sig;
Procedemos a eliminar el primer nodo de la lista llamando al operador delete:
delete bor;
Retornamos la información:
return informacion;
En caso de estar vacía la pila retornamos el número -1 y lo tomamos como código de error (es decir nunca debemos guardar el entero -1 en la pila)
else
{
return -1;
}
Es muy importante entender gráficamente el manejo de las listas. La interpretación gráfica nos permitirá plantear inicialmente las soluciones para el manejo de listas.
Expliquemos el método para recorrer una lista en forma completa e imprimir la información de cada nodo:
void Pila::imprimir()
{
Nodo *reco = raiz;
cout << "Listado de todos los elementos de la pila.\n";
while (reco != NULL)
{
cout << reco->info << "-";
reco = reco->sig;
}
cout << "\n";
}
Definimos un puntero auxiliar reco y hacemos que apunte al primer nodo de la lista:
Nodo *reco = raiz;
Disponemos una estructura repetitiva que se repetirá mientras reco sea distinto a NULL. Dentro de la estructura repetitiva hacemos que reco avance al siguiente nodo:
while (reco != NULL)
{
cout << reco->info << "-";
reco = reco->sig;
}
Es muy importante entender la línea:
reco = reco->sig;
Estamos diciendo que reco almacena la dirección que tiene el puntero sig del nodo apuntado actualmente por reco.
Gráficamente:
Al analizarse la condición:
while (reco != NULL)
Es verdadero ya que reco apunta a un nodo y se vuelve a ejecutar la línea:
reco = reco->sig;
Ahora reco apunta al siguiente nodo:
La condición del while nuevamente se valúa en verdadera y avanza el puntero reco al siguiente nodo:
reco = reco->sig;
Ahora sí reco apunta a NULL (tiene almacenado un NULL) y ha llegado el final de la lista (Recordar que el último nodo de la lista tiene almacenado en el puntero sig el valor NULL, con el objetivo de saber que es el último nodo)
El último método a analizar es el destructor de la clase que tiene por objetivo liberar el espacio ocupado por los nodos de la lista, esta actividad es fundamental:
Pila::~Pila()
{
Nodo *reco = raiz;
Nodo *bor;
while (reco != NULL)
{
bor = reco;
reco = reco->sig;
delete bor;
}
}
Definimos dos punteros auxiliares: reco y bor. A reco lo inicializamos con el primer nodo de la lista (en forma similar a como hicimos el imprimir donde recorremos toda la lista):
Nodo *reco = raiz;
Nodo *bor;
Mediante un while recorreremos toda la lista:
while (reco != NULL)
Dentro del while inicializamos el puntero bor con la dirección del nodo que apunta reco:
bor = reco;
Inmediatamente avanzamos reco al siguiente nodo:
reco = reco->sig;
Y procedemos a borrar el nodo apuntado por bor:
delete bor;
Este while se repite mientras haya nodos en la lista.
Para poder probar esta clase recordemos que debemos definir un objeto de la misma y llamar a sus métodos:
void main()
{
Pila *pila1;
pila1= new Pila();
pila1->insertar(10);
pila1->insertar(40);
pila1->insertar(3);
pila1->imprimir();
cout<<"Extraemos de la pila:" <<pila1->extraer()<<"\n";
pila1->imprimir();
cout<<"Retornamos primero de la pila:" <<pila1->retornar()<<"\n";
pila1->imprimir();
delete pila1;
cin.get();
}
Insertamos 3 enteros, luego imprimimos la pila, extraemos uno de la pila y finalmente imprimimos nuevamente la pila.
Problema 2:
Agregar a la clase Pila un método que retorne la cantidad de nodos y otro que indique si esta vacía.
Programa:
#include <iostream>
using namespace std;
class Pila {
private:
class Nodo {
public:
int info;
Nodo *sig;
};
Nodo *raiz;
public:
Pila();
~Pila();
void insertar(int x);
int extraer();
void imprimir();
int cantidad();
bool vacia();
};
Pila::Pila()
{
raiz = NULL;
}
void Pila::insertar(int x)
{
Nodo *nuevo;
nuevo = new Nodo();
nuevo->info = x;
if (raiz == NULL)
{
raiz = nuevo;
nuevo->sig = NULL;
}
else
{
nuevo->sig = raiz;
raiz = nuevo;
}
}
void Pila::imprimir()
{
Nodo *reco = raiz;
cout << "Listado de todos los elementos de la pila.\n";
while (reco != NULL)
{
cout << reco->info << "-";
reco = reco->sig;
}
cout << "\n";
}
int Pila::extraer()
{
if (raiz != NULL)
{
int informacion = raiz->info;
Nodo *bor = raiz;
raiz = raiz->sig;
delete bor;
return informacion;
}
else
{
return -1;
}
}
Pila::~Pila()
{
Nodo *reco = raiz;
Nodo *bor;
while (reco != NULL)
{
bor = reco;
reco = reco->sig;
delete bor;
}
}
int Pila::cantidad()
{
Nodo *reco = raiz;
int cant = 0;
while (reco != NULL)
{
cant++;
reco = reco->sig;
}
return cant;
}
bool Pila::vacia()
{
if (raiz == NULL)
return true;
else
return false;
}
void main()
{
Pila *pila1;
pila1 = new Pila();
pila1->insertar(10);
pila1->insertar(40);
pila1->insertar(3);
pila1->imprimir();
cout << "La cantidad de nodos de la pila es:" << pila1->cantidad() << "\n";
while (pila1->vacia() == false)
{
cout << "Extraemos de la pila:" << pila1->extraer() << "\n";
}
delete pila1;
cin.get();
}
Este proyecto lo puede descargar en un zip desde este enlace : Pila2.zip
Para verificar si la pila esta vacía verificamos el contenido de la variable raiz, si tiene NULL luego la lista esta vacía y por lo tanto retornamos un true (el tipo de dato bool en C++ puede almacenar solo alguno de estos dos valores: true o false):
bool Pila::vacia()
{
if (raiz == NULL)
return true;
else
return false;
}
El algoritmo para saber la cantidad de nodos es similar al imprimir, pero en lugar de mostrar la información del nodo procedemos a incrementar un contador:
int Pila::cantidad()
{
Nodo *reco = raiz;
int cant = 0;
while (reco != NULL)
{
cant++;
reco = reco->sig;
}
return cant;
}
Para probar esta clase en la main creamos un objeto de la clase Pila insertamos tres enteros:
Pila *pila1;
pila1 = new Pila();
pila1->insertar(10);
pila1->insertar(40);
pila1->insertar(3);
Imprimimos la pila (nos muestra los tres datos):
pila1->imprimir();
Llamamos al método cantidad (nos retorna un 3):
cout << "La cantidad de nodos de la pila es:" << pila1->cantidad() << "\n";
Luego mientras el método vacía nos retorne un false (lista no vacía) procedemos a llamar al método extraer:
while (pila1->vacia() == false)
{
cout << "Extraemos de la pila:" << pila1->extraer() << "\n";
}
Para entender el concepto de punteros el Visual Studio nos provee una herramienta de ejecutar línea a línea un programa y poder ver el estado de las variables.
Para ejecutar paso a paso debemos seleccionar desde el menú de opciones DEBUG -> Step Into (o más fácil presionar la tecla F11):
Cada vez que presionemos F11 se ejecutará una línea de código de nuestro programa y podremos ver en una ventana el contenido de las variables definidas:
Como vemos presionando F11 se ejecuta una línea de código, en el caso que se llama a un método vemos como la ejecución continua dentro de cada línea del método y al finalizar vuelve a la main para ingresar al siguiente método y así sucesivamente.
Cuando se ejecuta el cout podemos ver el código fuente del mismo, en muchos casos esto no nos sirve y podemos hacer que se ejecute en un solo paso presionando la tecla F10 (Step Over) en lugar de F11
Problema propuesto
- Agregar un método a la clase Pila que retorne la información del primer nodo de la Pila sin borrarlo.
#include <iostream>
using namespace std;
class Pila {
private:
class Nodo {
public:
int info;
Nodo *sig;
};
Nodo *raiz;
public:
Pila();
~Pila();
void insertar(int x);
int extraer();
int retornar();
void imprimir();
int cantidad();
bool vacia();
};
Pila::Pila()
{
raiz = NULL;
}
void Pila::insertar(int x)
{
Nodo *nuevo;
nuevo = new Nodo();
nuevo->info = x;
if (raiz == NULL)
{
raiz = nuevo;
nuevo->sig = NULL;
}
else
{
nuevo->sig = raiz;
raiz = nuevo;
}
}
void Pila::imprimir()
{
Nodo *reco = raiz;
cout << "Listado de todos los elementos de la pila.\n";
while (reco != NULL)
{
cout << reco->info << "-";
reco = reco->sig;
}
cout << "\n";
}
int Pila::extraer()
{
if (raiz != NULL)
{
int informacion = raiz->info;
Nodo *bor = raiz;
raiz = raiz->sig;
delete bor;
return informacion;
}
else
{
return -1;
}
}
int Pila::retornar()
{
if (raiz != NULL)
{
return raiz->info;
}
else
return -1;
}
Pila::~Pila()
{
Nodo *reco = raiz;
Nodo *bor;
while (reco != NULL)
{
bor = reco;
reco = reco->sig;
delete bor;
}
}
int Pila::cantidad()
{
Nodo *reco = raiz;
int cant = 0;
while (reco != NULL)
{
cant++;
reco = reco->sig;
}
return cant;
}
bool Pila::vacia()
{
if (raiz == NULL)
return true;
else
return false;
}
void main()
{
Pila *pila1;
pila1 = new Pila();
pila1->insertar(10);
pila1->insertar(40);
pila1->insertar(3);
pila1->imprimir();
cout << "El primer valor de la pila es:" << pila1->retornar() << "\n";
pila1->imprimir();
delete pila1;
cin.get();
}
Este proyecto lo puede descargar en un zip desde este enlace :Pila3.zip