40 - Estructuras dinámicas en C: Listas tipo Pila
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):
//variable global que apunta al
//primer nodo de la lista
struct nodo *raiz=NULL
1.- El Nodo:
// Un nodo tiene un dato, el cual es el número. Y otro nodo al que apunta
struct nodo {
int numero;
struct nodo *siguiente;
};
Insertamos un valor entero en la pila: insertar(10)
struct nodo *nuevo;
nuevo = malloc(sizeof(struct nodo));
nuevo->numero = x;
if (raiz == NULL)
{
raiz = nuevo;
nuevo->sig = NULL;
}
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) else if (raiz != NULL)
{
nuevo->sig = raiz;
raiz = nuevo;
}
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:
if (raiz != NULL)
{
int informacion = raiz->numero
struct nodo *bor = raiz;
raiz = raiz->sig;
extraer()
free(bor);
return informacion;
}
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 numero;
struct nodo *sig;
};
//variable global que apunta al primer nodo de la lista
struct nodo *raiz=NULL
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->numero = x;
if (raiz == NULL)
{
raiz = nuevo;
nuevo->sig = NULL;
}
else
{
nuevo->sig = raiz;
raiz = nuevo;
}
}
La función extraer:
int extraer()
{
if (raiz != NULL)
{
int informacion = raiz->numero;
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) // la Lista no esta Vacia
{
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;
free(bor);
return informacion;
void imprimir() void liberar()
{ {
struct nodo *reco=raiz; struct nodo *reco = raiz;
printf("Lista completa.\n"); struct nodo *bor;
while (reco!=NULL) while (reco != NULL)
{ {
printf("%i ",reco->info); bor = reco;
reco=reco->sig; reco = reco->sig;
} free(bor);
printf("\n"); }
} }
Implementar una stack dinámica en C;
1.- El Nodo:
// Un nodo tiene un dato, el cual es el número. Y otro nodo al que apunta
struct nodo {
int numero;
struct nodo *siguiente;
};
Esto es de lo que estará compuesta nuestra pila, para ello usaremos una lista
ligada en donde un nodo apunta a otro y este otro a otro (opcionalmente),
así infinitamente.
Claro que el elemento siguiente de un nodo es opcional; porque el elemento de
hasta abajo no apunta a nadie.
También tiene un número, que es el dato en sí que guardaremos en la pila.
Si quisiéramos que nuestra pila fuera de strings entonces comenzaríamos
cambiando el tipo de dato de int a char[].
2.- El elemento superior
En el inicio de todos los tiempos, debe haber un elemento superior aunque
no tenga valor y no apunte a nada. Es decir, aunque la pila esté vacía debemos
tener un elemento que será el inicio de todo:
// Todo comienza con el nodo superior
struct nodo *superior = NULL;
3.- Agregar elementos a la pila: push
void agregar(int numero) {
printf("Agregando %d\n", numero);
// El que se agregará; reservamos memoria
struct nodo *nuevoNodo = malloc(sizeof(struct nodo));
// Le ponemos el dato
nuevoNodo->numero = numero;
// Y ahora el nuevo nodo es el superior, y su siguiente
// es el que antes era superior
nuevoNodo->siguiente = superior;
superior = nuevoNodo;
}
|datto|siguiente| → |dato|siguiente|
superior → NULL
nuevoNodo →numero = numero;
nuevoNodo →siguiente → superior → NULL
Superior
NuevoNodo→siguiente = Null
superior → nuevoNodo
superior->|nuevoNodo|siguiente|->Null
4.- Eliminar el último elemento (operación pop)
// Operación pop, eliminar el de hasta arriba
void eliminarUltimo(void) {
printf("Eliminando el último\n");
if (superior != NULL) {
// Para liberar la memoria más tarde debemos
// tener la referencia al que vamos a eliminar
struct nodo *temporal = superior;
// Ahora superior es a lo que apuntaba su siguiente
superior = superior->siguiente;
// Liberar memoria que estaba ocupando el que eliminamos
free(temporal);
}
}
5.- Imprimir pila
Imprimir la pila no es una operación necesaria, pero como este es
un ejercicio sí lo haremos. Únicamente recorremos toda la pila mientras
haya un apuntador a siguiente:
void imprimir(void) {
printf("Imprimiendo...\n");
struct nodo *temporal = superior;
while (temporal != NULL) {
printf("%d\n", temporal->numero);
temporal = temporal->siguiente;
}
}
6.- Tamaño de pila o stack en C
Esto es muy parecido al de imprimir; pero en lugar de imprimir
vamos aumentando un contador dentro del ciclo:
int tamanio(void){
int contador = 0;
if(superior == NULL) return contador;
struct nodo *temporal = superior;
while (temporal != NULL) {
contador++;
temporal = temporal->siguiente;
}
return contador;
}
7.- Método para saber si la pila está vacía
bool vacia(void){
return superior == NULL;
}
8.- Operación top o peek de la pila: último elemento
Esto es fácil, se lee el último elemento de la pila y en
este caso es un entero.
int ultimo(){
if(superior == NULL) return -1;
return superior->numero;
}
