Requisitos previos: tener conocimientos en estructuras, funciones, memoria, operadores y conceptos básicos en C++.
¿Qué es una pila?
La pila o también llamada stack (apilar) en inglés, es una estructura de datos de tipo LIFO (Last in, first out) que se crea en base a la memoria dinámica principalmente y solo recibe datos por su extremo, o también llamado popularmente cima, al igual que su salida de datos que es por su cima.
Explicado de una forma más gráfica y llevado a la vida real podemos imaginar una pequeña columna de platos apilada. Si quisiéramos introducir un nuevo plato a esa columna la única manera seria poniendo un plato por encima del ultimo, asimismo, si quisiéramos sacar un plato tendríamos que retirar el plato de la cima. Por otro lado, si quisiéramos sacar un plato en específico tendríamos que sacar todos los superiores hasta dar con él.
Y como consecuencia de esto si ingresamos cierta cantidad de datos en una pila se nos será devuelta en orden inversa a la que entro, por ejemplo:
Si ingresamos los números 4 5 8, se nos devolverá en orden inverso tal que seria, 8 5 4.
Si ingresamos la palabra “mono” (letra por letra), se nos será devuelta la cadena “onom”. De esta misma manera si ingresamos una palabra palíndroma (que se lee igual en ambas direcciones) entonces nos devolverá la misma cadena.
¿Cómo empezar?
Primero debemos saber que una pila se crea en base a una estructura que contiene dos campos, uno seria el que guarda el o los datos que pueden ser de cualquier tipo y el otro campo sería un puntero del mismo tipo de la estructura ya que nos servirá para enlazar nuestras estructuras. También cabe mencionar que este solo es 1 algoritmo y es probable que encuentres otras formas mejores y más cómodas para ti según tu estilo. De momento se usará C++.
1
2
3
4
struct nodo {
int dato;
nodo *siguiente;
}
Previamente creamos un nuevo dato puntero del mismo tipo de la estructura y lo igualamos a nulo, ya que servirá para ir guardando los valores de dato y las direcciones de memoria que vamos usando para enlazar los nodos.
1
nodo *pilla=NULL
Acciones usualmente usadas para pila (stack)
Para trabajar con este tipo de datos tendremos 2 opciones básicas, las cuales son insertar o también llamado push y también quitar o también llamado pop.
¿Cómo insertar datos a una pila?
Para ingresar datos tendremos 5 sencillos pasos a seguir.
- Crear una función con sus respectivos parámetros
1
2
3
void agregarElementos(Nodo *&pila, int n){
}
Crear el espacio en memoria para el nuevo nodo
Como mencionamos inicialmente este tipo de estructura usa la memoria dinámica por lo que usaremos la función new, que sirve para asignar memoria dinámica a un tipo de dato durante la ejecución del programa. Primero creamos el tipo de dato puntero del tipo Nodo y posteriormente lo igualamos a la memoria que vamos usar.
1
2
3
void agregarElementos(nodo *&pila, int n){
nodo *nuevo_nodo = new nodo();
}
Guardar el valor a introducir en el campo dato del nodo
Como dice el titulo procederemos a guardar el dato, en este caso vamos a considerar el dato a guardar llamado “n”.
1
2
3
4
void agregarElementos(nodo *&pila, int n){
nodo *nuevo_nodo = new nodo();
nuevo_nodo -> dato=n;
}
Guardar la posición de memoria del puntero “pila” en el nuevo nodo
En este paso vamos a guardar dentro del nuevo nodo en el campo siguiente la posición de pila.
Observación: Recordemos que iniciamos a pila en nulo, por lo que el nuevo nodo ira guardando su posición sucesivamente, pero para esto debemos ir cambiando la posición de pila, lo cual será visto en el próximo paso.
- Asignar el nuevo nodo a pila
1
2
3
4
5
void agregarElementos(nodo *&pila, int n){
nodo *nuevo_nodo = new nodo();
nuevo_nodo -> dato=n;
nuevo_nodo -> siguiente=pila;
}
Es muy importante ir cambiando la posición de pila de caso contrario no se enlazarían los nodos.
1
2
3
4
5
6
void agregarElementos(nodo *&pila, int n){
nodo *nuevo_nodo = new nodo();
nuevo_nodo -> dato=n;
nuevo_nodo -> siguiente=pila;
pila=nuevo_nodo
}
¿Cómo quitar elementos de una pila?
Al igual que al introducir datos usaremos 5 sencillos pasos.
- Crear una función con sus respectivos parámetros
1
2
3
void sacandoNodos(nodo *&pila, int n){
}
- Crear una variable auxiliar puntero de tipo nodo
1
2
3
void sacandoNodos(nodo *&pila, int n){
nodo *axu=pila;
}
Este paso se realiza especialmente para ir eliminando memoria al finalizar cada recorrido.
- Igualamos la variable n a el campo dato
En realidad, este paso no es del todo obligatorio, pero nos servirá de mucho en caso que queramos trabajar con el dato de salida.
1
2
3
4
void sacandoNodos(nodo *&pila, int n){
nodo *axu=pila;
n=aux -> dato;
}
- Pasar al siguiente nodo
En este paso hacemos que la variable pila avance al siguiente nodo para asi no perder el resto de los nodos.
1
2
3
4
5
void sacandoNodos(nodo *&pila, int n){
nodo *axu=pila;
n=aux -> dato;
pila=aux->siguiente;
}
- Liberar memoria
En este paso finalizamos liberando la memoria del ultimo nodo que estaría guardado en la variable auxiliar
1
2
3
4
5
6
void sacandoNodos(nodo *&pila, int n){
nodo *axu=pila;
n=aux -> dato;
pila=aux->siguiente;
delete aux;
}
Observación
En la entrada de datos no se ingresa la variable n por referencia (&), al contrario de la salida, pues como se dijo anteriormente se puede guardar el valor del dato para posteriormente trabajar con el.
Extra
Como se mencionó inicialmente, las pilas o stack se usan principalmente se crean con memoria dinámica pero también podría crearse con memoria estática para familiarizarse más con el concepto, aunque se recomienda más el uso dinámico ya que su finalidad es reducir el uso de memoria durante el proceso.
Tomando en cuenta lo anterior, para crear una pila estática debería seguir teniendo las mismas reglas ya mencionadas, como principalmente, al ir agregando un elemento deben ir de forma consecutiva al anterior de la misma manera de la que vamos quitando elementos, siempre respetando su orden.
Definición Colas.
A diferencia de las pilas donde los elementos entran y salen del mismo extremo (Mediante el proceso LIFO) esto cambia en una cola, porque en este existen dos extremos llamados; parte delantera y parte trasera.
La primera parte (Delantera o Dequeue) es la que se encargara de retirar el elemento, mientras que la segunda parte (Trasera o Enqueue) se encargara de insertar los elementos, también existen otros operadores, pero por ahora nos enfocaremos en estos dos.
Enqueue
Para poder insertar elementos a una cola primero debemos crear los operadores delantera y trasera que serán los punteros que usaremos para el nodo, uno apuntara siempre al ultimo nodo o dato que se ingresara a la cola y el otro apuntara siempre a la primera parte que del nodo, pero estos siempre empezaran por apuntar en NULL, para que entiendan el funcionamiento de un nodo os daré una representación de nodos que hice en pixel art:
Explicare la primera parte, un nodo se compone de dos cosas el dato y en enlace al otro nodo que es next, pero por norma general un nodo siempre inicializa de forma vacía (NULL) ya que no tiene un dirección fija a la hora de compilación y esta dirección solo se emplea a los elementos que se irán agregando a la hora de ejecución, por ejemplo: 1 se enlaza con 2 y luego con 3, porque se van agregando su direcciones de memoria mientras se ejecuta hasta llegar a next. El puntero next o “siguiente” también es igual a NULL.
Estructura del Nodo y Cola:
1
2
3
4
5
6
7
8
9
typedef char Tipo_Dato;
struct nodo {
Tipo_Dato data;
nodo *next;
}
struct cola {
nodo *Dequeue;
nodo *Enqueue;
}
Como dijo mi compañero antes existen muchas formas de hacer ya queda en ti cual es la mejor según la necesidad del programa o de ti, aunque depende mas por el tipo de lista que quieras hacer. Normalmente se usa bastantee las pilas y colas en clases que ya vendrían siendo lenguajes como C++,.
Ya que tenemos la estructura nodo y cola podemos realizar la primera parte de nuestra función insertar:
1
2
3
4
5
6
7
8
9
10
11
void insertar(struct cola &p, int valor){
struct cola *nuevo nodo = inew(struct nodo);
nuevo_nodo -> data = valor;
nuevo_nodo -> next = NULL;
if(p.Dequeue == NULL)
p.Dequeue = nuevo_nodo;
else
(p.Dequeue) -> next = nuevo_nodo;
p.Euqueue = nuevo__nodo;
}
Ya que tenemos la estructura nodo y cola podemos realizar la primera parte de nuestra función retirar:
1
2
3
4
5
6
7
8
9
void retirar(struct cola &p){
Dato_Tipo valor
valor = nuevo_nodo -> data;
nuevo_nodo = p.Dequeue;
p.Dequeue = (p.Dequeue) -> next;
if (Dequeue) delete Dequeue;
}
Bueno para no hacer mas largo esto explicare de manera simplificada la operación que nos hace falta y este es empty(parámetro), prácticamente este operador nos dice si la lista esta vacía (Esto lo aplicaremos en la función la cual elimina los elementos) y si lo esta cuando operamos la función retirar entonces esta va a parar el programa para esto solo ocupamos hacer una función boleana que retorne 1 si esta vacía o 0 sino lo esta, luego agregaremos una condición if(empty) return -1 si la cola esta vacía para que podamos aplicar correctamente la función retirar ya que esta solo debe ser usada si la lista esta vacía,
Si se pregunta ¿Por qué usaste términos en ingles? es para que se ¿Familiaricen? a futuro con las librerías Stack y Queue, las cuales poseen estos términos.
**¡Me alegra saber que leiste todo el blog! y gracias a Z por ayudarme a escribir el blog, TSK. **