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 registro, 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 programa que administre una lista tipo pila (se debe poder insertar, extraer e imprimir los datos de la pila)
Programa: programa160.c
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct nodo {
int info;
struct nodo *sig;
};
//variable global que apunta al primer nodo de la lista
struct nodo *raiz=NULL;
void insertar(int x)
{
struct nodo *nuevo;
nuevo = malloc(sizeof(struct nodo));
nuevo->info = x;
if (raiz == NULL)
{
raiz = nuevo;
nuevo->sig = NULL;
}
else
{
nuevo->sig = raiz;
raiz = nuevo;
}
}
void imprimir()
{
struct nodo *reco=raiz;
printf("Lista completa.\n");
while (reco!=NULL)
{
printf("%i ",reco->info);
reco=reco->sig;
}
printf("\n");
}
int extraer()
{
if (raiz != NULL)
{
int informacion = raiz->info;
struct nodo *bor = raiz;
raiz = raiz->sig;
free(bor);
return informacion;
}
else
{
return -1;
}
}
void liberar()
{
struct nodo *reco = raiz;
struct nodo *bor;
while (reco != NULL)
{
bor = reco;
reco = reco->sig;
free(bor);
}
}
int main()
{
insertar(10);
insertar(40);
insertar(3);
imprimir();
printf("Extraemos de la pila:%i\n",extraer());
imprimir();
liberar();
getch();
return 0;
}
Analicemos las distintas partes de este programa:
Declaramos un registro con dos campos. Un entero que es la información que guardará cada nodo y un puntero al siguiente nodo:
struct nodo {
int info;
struct nodo *sig;
};
Algo nuevo que no habíamos hecho hasta este momento es la definición de una variable global en nuestro programa, si bien en programas grandes puede traer inconvenientes las presentamos en este momento para facilitar la comprensión del concepto de listas:
//variable global que apunta al primer nodo de la lista struct nodo *raiz=NULL;
La variable raiz es un puntero que apunta a registros de tipo nodo. Dijimos que un puntero es una variable que puede almacenar una dirección de memoria, si guardamos la macro NULL estamos indicando que la variable no almacena en este momento una dirección.
El valor NULL nos permite identificar si un puntero tiene almacenada una dirección o no.
La variable raiz al ser una variable global no es necesaria pasarla como parámetro a cada función que la necesite.
Todo programa en C comienza a ejecutarse desde la función main, previo a iniciar la main reserva espacio para todas las variables globales (en nuestro caso raiz) desde la main llamamos a las distintas funciones para administrar la lista:
int main()
{
insertar(10);
insertar(40);
insertar(3);
imprimir();
printf("Extraemos de la pila:%i\n",extraer());
imprimir();
liberar();
getch();
return 0;
}
La función insertar nos permite agregar un nodo al principio de la lista:
void insertar(int x)
{
struct nodo *nuevo;
nuevo = malloc(sizeof(struct nodo));
nuevo->info = x;
if (raiz == NULL)
{
raiz = nuevo;
nuevo->sig = NULL;
}
else
{
nuevo->sig = raiz;
raiz = nuevo;
}
}
A la función 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 modo:
struct nodo *nuevo;
- Creación del nodo (reserva de espacio en la memoria dinámica):
nuevo = malloc(sizeof(struct nodo));
Cuando se ejecuta la función malloc se reserva espacio para el nodo. Realmente se crea el nodo cuando se ejecuta la función malloc.
Paso seguido debemos guardar la información del nodo (el campo info 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 campo 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 cuando definimos la variable)
Tener en cuenta que podemos acceder a raiz sin haberla pasado como parámetro ya que es una variable global y puede ser accedida por cualquier función luego de su definición:
if (raiz == NULL)
{
raiz = nuevo;
nuevo->sig = NULL;
}
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 de la función el puntero "nuevo" desaparece, pero no el nodo creado mediante la función malloc.
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:
La función extraer:
int extraer()
{
if (raiz != NULL)
{
int informacion = raiz->info;
struct nodo *bor = raiz;
raiz = raiz->sig;
free(bor);
return informacion;
}
else
{
return -1;
}
}
El objetivo de la función 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:
if (raiz != NULL)
{
int informacion = raiz->info;
Creamos un puntero auxiliar y hacemos que apunte al nodo que vamos a borrar:
struct 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 a la función free (si no hacemos esto no se genera error en el programa pero dicho espacio de memoria no se podrá asignar cuando hagamos otra llamada a la función malloc):
free(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, podemos utilizar cualquier otro entero que indique lista vacía)
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 la función para recorrer una lista en forma completa e imprimir la información de cada nodo:
void imprimir()
{
struct nodo *reco=raiz;
printf("Lista completa.\n");
while (reco!=NULL)
{
printf("%i ",reco->info);
reco=reco->sig;
}
printf("\n");
}
Definimos un puntero auxiliar reco y hacemos que apunte al primer nodo de la lista:
struct 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)
{
printf("%i ",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)
La última función a analizar es liberar que tiene por objetivo liberar el espacio ocupado por los nodos de la lista, esta actividad es fundamental:
void liberar()
{
struct nodo *reco = raiz;
struct nodo *bor;
while (reco != NULL)
{
bor = reco;
reco = reco->sig;
free(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):
struct nodo *reco = raiz;
struct 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:
free(bor);
Este while se repite mientras haya nodos en la lista.
Problema 2:
Agregar al problema anterior otras dos funciones: que retorne la cantidad de nodos y otro que indique si esta vacía (1=vacía y 0=no vacía).
Programa: programa161.c
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct nodo {
int info;
struct nodo *sig;
};
//variable global que apunta al primer nodo de la lista
struct nodo *raiz=NULL;
void insertar(int x)
{
struct nodo *nuevo;
nuevo = malloc(sizeof(struct nodo));
nuevo->info = x;
if (raiz == NULL)
{
raiz = nuevo;
nuevo->sig = NULL;
}
else
{
nuevo->sig = raiz;
raiz = nuevo;
}
}
void imprimir()
{
struct nodo *reco=raiz;
printf("Lista completa.\n");
while (reco!=NULL)
{
printf("%i ",reco->info);
reco=reco->sig;
}
printf("\n");
}
int extraer()
{
if (raiz != NULL)
{
int informacion = raiz->info;
struct nodo *bor = raiz;
raiz = raiz->sig;
free(bor);
return informacion;
}
else
{
return -1;
}
}
void liberar()
{
struct nodo *reco = raiz;
struct nodo *bor;
while (reco != NULL)
{
bor = reco;
reco = reco->sig;
free(bor);
}
}
int cantidad()
{
struct nodo *reco = raiz;
int cant = 0;
while (reco != NULL)
{
cant++;
reco = reco->sig;
}
return cant;
}
int vacia()
{
if (raiz == NULL)
return 1;
else
return 0;
}
int main()
{
insertar(10);
insertar(40);
insertar(3);
imprimir();
printf("Extraemos de la pila:%i\n",extraer());
imprimir();
printf("La cantidad de nodos de la pila es:%i\n",cantidad());
while (vacia() == 0)
{
printf("Extraemos de la pila:%i\n",extraer());
}
liberar();
getch();
return 0;
}
Para verificar si la pila esta vacía controlamos el contenido de la variable raiz, si tiene NULL luego la lista esta vacía y por lo tanto retornamos un 1 (normalmente en el lenguaje C el 0 representa falso y un valor distinto a 0 representa el verdadero):
int vacia()
{
if (raiz == NULL)
return 1;
else
return 0;
}
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 cantidad()
{
struct nodo *reco = raiz;
int cant = 0;
while (reco != NULL)
{
cant++;
reco = reco->sig;
}
return cant;
}
Para probar este programa en la main llamamos a insertar tres enteros:
int main()
{
insertar(10);
insertar(40);
insertar(3);
Imprimimos la pila (nos muestra los tres datos):
imprimir();
Llamamos a la función cantidad (nos retorna un 3):
printf("La cantidad de nodos de la pila es:%i\n",cantidad());
Luego mientras la función vacía nos retorne un cero (lista no vacía) procedemos a llamar a la función extraer:
while (vacia() == 0)
{
printf("Extraemos de la pila:%i\n",extraer());
}
}
Problema propuesto
- Agregar otra función al programa desarrollado para administrar una pila que retorne la información del primer nodo de la Pila sin borrarlo.
programa162.c
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct nodo {
int info;
struct nodo *sig;
};
//variable global que apunta al primer nodo de la lista
struct nodo *raiz=NULL;
void insertar(int x)
{
struct nodo *nuevo;
nuevo = malloc(sizeof(struct nodo));
nuevo->info = x;
if (raiz == NULL)
{
raiz = nuevo;
nuevo->sig = NULL;
}
else
{
nuevo->sig = raiz;
raiz = nuevo;
}
}
void imprimir()
{
struct nodo *reco=raiz;
printf("Lista completa.\n");
while (reco!=NULL)
{
printf("%i ",reco->info);
reco=reco->sig;
}
printf("\n");
}
int extraer()
{
if (raiz != NULL)
{
int informacion = raiz->info;
struct nodo *bor = raiz;
raiz = raiz->sig;
free(bor);
return informacion;
}
else
{
return -1;
}
}
void liberar()
{
struct nodo *reco = raiz;
struct nodo *bor;
while (reco != NULL)
{
bor = reco;
reco = reco->sig;
free(bor);
}
}
int cantidad()
{
struct nodo *reco = raiz;
int cant = 0;
while (reco != NULL)
{
cant++;
reco = reco->sig;
}
return cant;
}
int vacia()
{
if (raiz == NULL)
return 1;
else
return 0;
}
int retornar()
{
if (raiz != NULL)
{
return raiz->info;
}
else
return -1;
}
int main()
{
insertar(10);
insertar(40);
insertar(3);
imprimir();
printf("El primer valor de la pila es:%i\n",retornar());
imprimir();
liberar();
getch();
return 0;
}