Implementación de una pila en Java con nodos enlazados

Paso 1: diseño de la implementación de la pila con nodos enlazados

El diseño que se ha seguido para poder aconseguir una implementación de una pila en Java con nodos enlazados es el explicado a continuación. Primero de todo, deberemos definir cómo serán nuestros nodos. Se ha optado por usar nodos que guarden un elemento y que tengan un apuntador a su nodo inferior. Entonces, el apuntador del primer nodo será null ya que no tendrá previo. La clase pila deberá tener acceso al nodo top ya que nos será de gran ayuda para eliminar o añadir nodos. Para ello tendremos una variable que siempre apunte al nodo top o a null si la pila está vacía. Además, también guardaremos una variable size con el número de nodos en la pila. Más adelante verás su utilidad.

Paso 2: definir la interfície Stack<E>

En esta interfície están los métodos fundamentales que debe tener una pila.

public interface Stack<E> {

    /**
     * Añade un elemento a la pila
     *
     * @param element
     */
    void push(E element);

    /**
     * Elimina el elemento del top de la pila
     *
     * @return elemento del top de la pila
     * @throws java.util.NoSuchElementException si la pila está vacia
     */
    E pop();

    /**
     * Permite consultar el elemento del top de la pila
     *
     * @return elemento del top de la pila
     * @throws java.util.NoSuchElementException si la pila está vacia
     */
    E peek();

    /**
     * Permite consultar cuantos elementos tiene la pila
     *
     * @return elementos en la pila
     */
    int size();
}

Paso 3: desarrollar la clase LinkedStack<E> en Java

El código de la Implementación de una pila en Java con nodos enlazados es el siguiente:

import java.util.NoSuchElementException;

public class LinkedStack<E> implements Stack<E> {

    private Node<E> top;
    private int size;

    LinkedStack() {
        top = null;
        size = 0;
    }

    private static class Node<E> {
        private E element;
        private Node<E> previous;

        Node(E e, Node<E> prev) {
            element = e;
            previous = prev;
        }
    }

    @Override
    public void push(E element) {
        var newNode = new Node<>(element, top);
        top = newNode;
        size += 1;
    }

    @Override
    public E pop() {
        if (size == 0)
            throw new NoSuchElementException("Pop on empty stack");

        var oldTop = top;
        var newTop = top.previous;
        top.previous = null;
        top = newTop;
        size -= 1;

        return oldTop.element;
    }

    @Override
    public E peek() {
        if (size == 0)
            throw new NoSuchElementException("Pop on empty stack");

        return top.element;
    }

    @Override
    public int size() {
        return size;
    }
}

Déjame que te explique paso paso cómo se ha programado todo. En primer lugar, hemos definido las variables de instancia de la clase LinkedStack<E>. Siguiendo el diseño que hemos planteado, necesitábamos un apuntador al nodo top y un entero size. En el constructor de la clase se inicializa top = null y size = 0. Este hecho implica que solo se pueden crear pilas vacías.

Hemos definido la clase Node<E> como interna, privada y estática. Para poder instanciar estos nodos dentro de la clase LinkedStack, es decir, crear objetos, deberemos usar su constructor. Este recibe dos parámetros: el elemento del nodo y su predecesor.

Veamos ahora como se han desarrollado los métodos de la interfície Stack:

• void push(E element): En este método debemos crear el nuevo nodo con el elemento y su predecesor, en este caso, el antiguo top de la pila. Finalmente, se reasigna el apuntador top de la pila como el nuevo nodo y se incrementa el tamaño de la pila.
• E pop(): Aquí, primero de todo, tenemos que comprobar que la pila no esté vacía. En tal caso, lanzamos una NoSuchElementException. Hecha la comprobación, hay que eliminar el nodo top haciendo que su apuntador sea null. Después, reasignamos el nodo top como el predecesor del nodo eliminado, decrementamos en uno el tamaño de la pila y retornamos el elemento del nodo eliminado.

• E peek(): En esta función solo debemos retornar el elemento del nodo al cual apunta top, siempre que la pila no esté vacía (NoSuchElementException).
• int size(): retornamos el valor de la variable de instancia con dicho nombre.