La Estructura de Datos Pila

COMPARTIR EN REDES SOCIALES

En esta entrada vamos a revisar la estructura de datos Pila. Realizaremos diferentes implementaciones de la misma, explicaremos sus principales métodos y realizaremos diferentes pruebas de rendimiento.

Concretamente realizaremos lo siguiente:

  1. Explicaremos qué es una pila.
  2. Explicaremos sus principales métodos.
  3. Realizaremos una implementación para números enteros.
  4. Realizaremos una implementación genérica utilizando una clase «Nodo».
  5. Realizaremos una implementación genérica utilizando un ArrayList.
  6. Utilizaremos la que Java proporciona en su API.

Vamos al lio!

¿ Qué es una pila ?

Una pila es una estructura de datos de tipo LIFO «Last IN First OUT», es decir, una estructura de datos donde los elementos que se introducen se van apilando y siempre se obtiene el último elemento introducido. Veamos un ejemplo gráfico:

Esquematización de las operaciones sobre una Pila
Esquematización de las operaciones sobre una Pila

En el esquema anterior podemos ver como empezamos con la pila vacía, en el segundo paso introducimos un «1», después un «2» y posteriormente un «3», finalmente a la hora de obtener los elementos siempre salen los que están en la cima de la pila, es decir, aquel que ha sido el último en introducirse, en este caso sería el «3», porque solo ejecutamos una función «pop», pero si hiciésemos 2 operaciones «pop» más obtendríamos el «2» y después el «1».

Las pilas tienen diferentes aplicaciones, siendo las más importantes la construcción de compiladores y la llamada a las funciones desde nuestros programas.

¿ Cuáles son los principales métodos de la Pila ?

Los principales métodos que tiene una pila son «apilar» y «desapilar» o «push» y «pop» en inglés respectivamente:

  1. Mediante el método «apilar» apilamos un elemento por encima del último elemento que haya en la pila.
  2. El método «desapilar» nos devuelve el elemento que está en la cima, es decir, el elemento superior de la pila. Después de devolvernos el elemento lo elimina de la pila.

Realmente una Pila es una estructura de datos muy sencilla, vamos a ver las diferentes implementaciones.

La Pila de Integers utilizando Nodos

Antes de ver la implementación de la Pila en sí, tenemos que ver nuestra clase «Nodo»:

public class Nodo {
	private Integer value;
	private Nodo next;
	
	public Nodo(Integer value, Nodo next) {
		super();
		this.value = value;
		this.next = next;
	}
	
	public Integer getValue() {
		return value;
	}
	
	public void setValue(Integer value) {
		this.value = value;
	}
	
	public Nodo getNext() {
		return next;
	}
	
	public void setNext(Nodo next) {
		this.next = next;
	}
}

Esta clase contiene 2 atributos:

  1. Un «Integer» con el valor que apilaremos u obtendremos.
  2. Un objeto de la misma clase que nos servirá para enlazar unos elementos con otros.

Ahora ya podemos ver la implementación de nuestra pila de enteros:


public class Pila {

	private Nodo cima;
	private int numElementos;
	
	public Pila() {
		cima = null;
		numElementos = 0;
	}
	
	public void apilar(Integer value) {
		Nodo nuevoNodo = new Nodo(value, null);
		
		if (cima == null) {
			cima = nuevoNodo;
		}else {
			nuevoNodo.setNext(cima);
			cima = nuevoNodo;
		}
		
		numElementos++;
	}
	
	public Integer desapilar() {
		Integer value = cima.getValue();
		cima = cima.getNext();
		numElementos--;
		return value;
	}
	
	public int size() {
		return this.numElementos;
	}
	
	public boolean hasNext() {
		return (cima != null);
	}
	
	public void clear() {
		cima = null;
	}
}

Nuestra clase «Pila» tiene 2 atributos de clase:

  1. El atributo «cima» de tipo «Nodo» que siempre apuntará a la cima de la pila, es decir, al último elemento introducido.
  2. Un entero «numElementos» que nos servirá para contabilizar los elementos que tiene la pila.

Veamos los métodos más importantes.

El método apilar

public void apilar(Integer value) {
	Nodo nuevoNodo = new Nodo(value, null);
		
	if (cima == null) {
		cima = nuevoNodo;
	}else {
		nuevoNodo.setNext(cima);
		cima = nuevoNodo;
	}
		
	numElementos++;
}

El método «apilar» siempre crea un nuevo nodo con el valor que le llega por parámetro y luego su lógica se bifurca de la siguiente manera:

  1. Si la pila está vacía, es decir, si «cima == null», la cima será nuestro nuevo nodo.
  2. Si la pila no está vacía, el elemento siguiente de nuestro nuevo nodo será la cima actual, y posteriormente la cima cambiará a nuestro nuevo nodo.

Por último incrementaremos en 1 en numero de elementos para contabilizarlos.

Vamos a realizar una traza teórica insertando 2 elementos, el «13» y el «45»:

  1. Se llama a apilar con el número «13». Se crea el nodo y como nuestra pila está vacía, nuestra cima es el nuevo nodo.
  2. Se llama a apilar con el número «45», como nuestra pila no está vacía, el elemento siguiente de nuestro nuevo nodo que contiene el «45» será la cima actual, es decir, el «13» y posteriormente la cima pasará a apuntar al «45».

El método desapilar

public Integer desapilar() {
	Integer value = cima.getValue();
	cima = cima.getNext();
	numElementos--;
	return value;
}

El método «desapilar»:

  1. Obtiene el valor de la cima actual y lo almacena en la variable «value».
  2. Decrementa el puntero de la cima para que apunte al siguiente elemento
  3. Decrementa el número de elementos en 1.
  4. Devuelve el valor de la variable «value»

Pruebas de nuestra pila de enteros

Vamos a apilar algunos elementos y posteriormente los desapilaremos:

//Creamos la pila
Pila pila = new Pila();

//Apilamos algunos elementos		
pila.apilar(1);
pila.apilar(2);
pila.apilar(3);

//Desapilamos todos los elementos
while (pila.hasNext()) {
	System.out.println(pila.desapilar());
}

La salida de nuestro programa

3
2
1

Los elementos se obtienen en orden inverso de inserción.

La Pila Genérica utilizando Nodos

Para poder crear una una pila genérica con nodos será necesario utilizar «Generics» tanto en los nodos como en las operaciones de la pila, veamos la clase «Nodo» genérica:

La clase NodoGenerico

public class NodoGenerico<V> {
	private V value;
	private NodoGenerico<V> next;
	
	public NodoGenerico(V value, NodoGenerico<V> next) {
		this.value = value;
		this.next = next;
	}

	public V getValue() {
		return value;
	}

	public void setValue(V value) {
		this.value = value;
	}

	public NodoGenerico<V> getNext() {
		return next;
	}

	public void setNext(NodoGenerico<V> next) {
		this.next = next;
	}
}

Si tenéis dudas acerca de los genéricos visitar nuestra entrada sobre genéricos.

La clase PilaGenerica

public class PilaGenerica<V> {

	private NodoGenerico<V> cima;
	private int numElementos;
	
	public PilaGenerica() {
		cima = null;
		numElementos = 0;
	}
	
	public void apilar(V value) {
		NodoGenerico<V> nuevoNodo = new NodoGenerico<V>(value, null);
		
		if (cima == null) {
			cima = nuevoNodo;
		}else {
			nuevoNodo.setNext(cima);
			cima = nuevoNodo;
		}
		
		numElementos++;
	}
	
	public V desapilar() {
		V value = cima.getValue();
		cima = cima.getNext();
		numElementos--;
		return value;
	}
	
	public int size() {
		return this.numElementos;
	}
	
	public boolean hasNext() {
		return (cima != null);
	}
	
	public void clear() {
		cima = null;
	}
}

El funcionamiento es el mismo que la pila de «Integer» que hemos visto en la sección anterior, pero en este caso utilizando los genéricos.

Insertaremos para las pruebas productos:

La clase Producto

public class Producto {
	private int id;
	private String nombre;

	public Producto(int id, String nombre) {
		this.id = id;
		this.nombre = nombre;
	}

	public int getId() {
		return id;
	}

	public void setId(int id) {
		this.id = id;
	}

	public String getNombre() {
		return nombre;
	}

	public void setNombre(String nombre) {
		this.nombre = nombre;
	}
}

Pruebas sobre nuestra clase Pila Genérica con Nodos

PilaGenerica<Producto> pila = new PilaGenerica<>();
		
pila.apilar(new Producto(1, "Tuerca"));
pila.apilar(new Producto(2, "Tornillo"));
pila.apilar(new Producto(3, "Destornillador"));
		
while (pila.hasNext()) {
	System.out.println(pila.desapilar().getNombre());
}

La salida de nuestro programa

Destornillador
Tornillo
Tuerca

Con en el ejemplo anterior obtenemos los elementos en orden inverso de inserción.

La implementación de la Pila utilizando un ArrayList

Esta implementación no utiliza nodos, por lo que solo tenemos una única clase para componer la pila:

import java.util.ArrayList;

public class PilaGenericaArrayList<V> {
	private int cima = -1;
	private ArrayList<V> elementos = null;
	private int numElementos = 0;
	
	public PilaGenericaArrayList() {
		elementos = new ArrayList<V>();
	}
	
	public void apilar(V value)
	{
		cima++;
		numElementos++;
		elementos.add(value);
	}
	
	public V desapilar() {
		V aux = this.elementos.get(cima);
		this.elementos.remove(cima);
		cima--;
		numElementos--;
		return aux;
	}
	
	public boolean hasNext() {
		if (numElementos > 0) {
			return true;
		}else {
			return false;
		}
	}
}

Esta implementación utiliza un «ArrayList» de elementos genéricos para formar la Pila, y el funcionamiento se lo da la variable cima que apuntará al índice del «ArrayList» que es la cima.

Veamos sus métodos

El método apilar

public void apilar(V value)
{
	cima++;
	numElementos++;
	elementos.add(value);
}
  1. Incrementamos la cima en una unidad.
  2. Incrementamos el número de elementos en una unidad.
  3. Añadimos el valor en la última posición del ArrayList.

El método desapilar

public V desapilar() {
	V aux = this.elementos.get(cima);
	this.elementos.remove(cima);
	cima--;
	numElementos--;
	return aux;
}
  1. Creamos una variable auxiliar «aux» y asignamos el valor de la cima.
  2. Eliminamos el valor de la cima.
  3. Decrementamos el valor de cima.
  4. Decrementamos el número de elementos.
  5. Devolvemos el valor del elemento «aux», la cima antes del decremento.

Pruebas sobre nuestra Pila Genérica construida con un ArrayList

PilaGenericaArrayList<Producto> pila = new PilaGenericaArrayList<>();
		
pila.apilar(new Producto(1, "Tuerca"));
pila.apilar(new Producto(2, "Tornillo"));
pila.apilar(new Producto(3, "Destornillador"));
		
while (pila.hasNext()) {
	System.out.println(pila.desapilar().getNombre());
}

La salida de nuestro programa

Destornillador
Tornillo
Tuerca

La Pila estándar de Java

La pila estándar de Java es la clase Stack y también utiliza genéricos, veamos como se utiliza:

Stack<Producto> pila = new Stack<>();
		
pila.push(new Producto(1, "Tuerca"));
pila.push(new Producto(2, "Tornillo"));
pila.push(new Producto(3, "Destornillador"));
				
Iterator<Producto> it = pila.iterator();
		
while (it.hasNext()) {
		System.out.println(it.next().getNombre());
}

La salida de nuestro programa

Tuerca
Tornillo
Destornillador

Pruebas de rendimiento de las implementaciones

En esta sección vamos a realizar pruebas de rendimiento de las diferentes implementaciones para ver cuál es la más eficiente. Para ello apilaremos 20 millones de elementos y los desapilaremos, repetiremos el mismo proceso 10 veces y luego sacaremos la media de tiempo. Realizaremos este proceso para cada implementación:

//Para la pila estándar de Java
long iniTime = System.currentTimeMillis();
for (int i = 0; i < 10; i++) {
	Stack<Producto> pila = new Stack<>();
	
	for (int j = 0; j < 20000000; j++) {
		pila.push(new Producto(j, "Tuerca"));
	}
	
	Iterator<Producto> it = pila.iterator();
	
	while (it.hasNext()) {
		it.next();
	}
}

long finTime = System.currentTimeMillis();
System.out.println("La implementación de la pila estándar de Java tarda: " + (((finTime - iniTime) / 1000.0) / 10));

//Para la pila de de Nodos Genérica
iniTime = System.currentTimeMillis();
for (int i = 0; i < 10; i++) {
	PilaGenerica<Producto> pila = new PilaGenerica<>();
	
	for (int j = 0; j < 20000000; j++) {
		pila.apilar(new Producto(j, "Tuerca"));
	}
	
	while (pila.hasNext()) {
		pila.desapilar();
	}
}

finTime = System.currentTimeMillis();
System.out.println("La implementación de la pila genérica artesana de Nodos tarda: " + (((finTime - iniTime) / 1000.0) / 10));

//Para la pila genérica con ArrayList
iniTime = System.currentTimeMillis();
for (int i = 0; i < 10; i++) {
	PilaGenericaArrayList<Producto> pila = new PilaGenericaArrayList<>();
	
	for (int j = 0; j < 20000000; j++) {
		pila.apilar(new Producto(j, "Tuerca"));
	}
	
	while (pila.hasNext()) {
		pila.desapilar();
	}
}

finTime = System.currentTimeMillis();
System.out.println("La implementación de la pila genérica con ArrayList tarda: " + (((finTime - iniTime) / 1000.0) / 10));

La salida de nuestro programa

La implementación de la pila estándar de Java tarda: 0.503
La implementación de la pila genérica artesana de Nodos tarda: 2.0080999999999998
La implementación de la pila genérica con ArrayList tarda: 0.3594

Pues como podéis apreciar nuestra implementación de la pila con el «ArrayList» gana a todas las demás implementaciones. Seguidamente está la implementación de Java estándar y en último lugar la nuestra con «Nodos». Chúpate esa Java!!!

Os dejo la documentación oficial sobre la clase Stack de Java.

Si os ha gustado la entrada de Pilas en Java compartirla en redes sociales y dejad un comentario para mostrar vuestro apoyo y que podamos seguir creando entrada y compartiendo conocimiento.


COMPARTIR EN REDES SOCIALES

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *