Stack Hack

public class LinkedList<T> {
    private T data;
    private LinkedList<T> prevNode, nextNode;

    /**
     *  Constructs a new element
     *
     * @param  data, data of object
     * @param  node, previous node
     */
    public LinkedList(T data, LinkedList<T> node)
    {
        this.setData(data);
        this.setPrevNode(node);
        this.setNextNode(null);
    }

    /**
     *  Clone an object,
     *
     * @param  node  object to clone
     */
    public LinkedList(LinkedList<T> node)
    {
        this.setData(node.data);
        this.setPrevNode(node.prevNode);
        this.setNextNode(node.nextNode);
    }

    /**
     *  Setter for T data in DoubleLinkedNode object
     *
     * @param  data, update data of object
     */
    public void setData(T data)
    {
        this.data = data;
    }

    /**
     *  Returns T data for this element
     *
     * @return  data associated with object
     */
    public T getData()
    {
        return this.data;
    }

    /**
     *  Setter for prevNode in DoubleLinkedNode object
     *
     * @param node, prevNode to current Object
     */
    public void setPrevNode(LinkedList<T> node)
    {
        this.prevNode = node;
    }

    /**
     *  Setter for nextNode in DoubleLinkedNode object
     *
     * @param node, nextNode to current Object
     */
    public void setNextNode(LinkedList<T> node)
    {
        this.nextNode = node;
    }


    /**
     *  Returns reference to previous object in list
     *
     * @return  the previous object in the list
     */
    public LinkedList<T> getPrevious()
    {
        return this.prevNode;
    }

    /**
     *  Returns reference to next object in list
     *
     * @return  the next object in the list
     */
    public LinkedList<T> getNext()
    {
        return this.nextNode;
    }

}

public class Stack<T> {

    private LinkedList<T> upper;
    private int size;

    // constructor initiates null LinkedList<T> object + set size to 0
    public Stack() {
        this.upper = null;
        this.size = 0;
    }

    // push method for a new element to the upper value
    public void push(T data) {
        LinkedList<T> newNode = new LinkedList<T>(data, this.upper);
        this.upper = newNode;
        this.size++;
    }

    // peek method, return upper
    public T peek() {
        // try/catch to either return upper or print message if upper doesn't exist
        try {
            return this.upper.getData();
        } catch (NullPointerException e) {
            System.out.println("No upper element, empty stack!");
            return null;
        }
    }

    // pop method, return upper and remove 
    public T pop() {
        // try/catch to either return + pop upper or print message if upper doesn't exist
        try {
            T data = this.upper.getData();
            this.upper = this.upper.getPrevious();
            this.size--;
            return data;
        } catch (NullPointerException e) {
            System.out.println("No upper element, empty stack!");
            return null;
        }
    }

    // get size method
    public int size() {
        return this.size;
    }

    // isEmpty method, compare size to 0
    public boolean isEmpty() {
        return this.size == 0;
    }

    // toString method, from top to bottom
    public String toString() {
        String s = "[ ";
        LinkedList<T> currentNode = upper;
        // gets upper node, then keeps going down to previous until previous is null
        while (currentNode != null) {
            s += currentNode.getData();
            currentNode = currentNode.getPrevious();
            if (currentNode != null) {
                s += ", ";
            }
        }
        s += " ]";
        return s;
    }

}

public class StackSort {
    public static void main(String[] args) {
        
        Stack<Integer> s1 = new Stack<Integer>();
        Stack<Integer> s2 = new Stack<Integer>();
        s1.push(3);
        s1.push(5);
        s1.push(1);
        s2.push(4);
        s2.push(2);
        sortStacks(s1, s2);
        System.out.println(s1.toString()); // should print "[1, 2, 3, 4, 5]"
    
        Stack<Integer> sorted = new Stack<Integer>();
        
        // Merge s1 and s2 into sorted in ascending order
        while (!s1.isEmpty() && !s2.isEmpty()) {
            if (s1.peek() <= s2.peek()) {
                sorted.push(s1.pop());
            } else {
                sorted.push(s2.pop());
            }
        }
        while (!s1.isEmpty()) {
            sorted.push(s1.pop());
        }
        while (!s2.isEmpty()) {
            sorted.push(s2.pop());
        }
        
        // Copy sorted back into s1 and s2 in reverse order
        while (!sorted.isEmpty()) {
            int val = sorted.pop();
            if (s1.isEmpty() || val <= s1.peek()) {
                s1.push(val);
            } else {
                while (!s1.isEmpty() && val > s1.peek()) {
                    s2.push(s1.pop());
                }
                s1.push(val);
                while (!s2.isEmpty()) {
                    s1.push(s2.pop());
                }
            }
        }
    
        
    }
}

StackSort.main(null);

[ 1, 2, 3, 4, 5 ]