[Java] Stack with IntNode, two-stack reverse trick

Let's try implementing a Stack in Java using IntNode.

 

The structure of IntNode looks like this: 

private static class IntNode() {
    int val;
    IntNode next;
    
    IntNode(int val, IntNode next) {
    	this.val = val;
        this.next = next;
    }
}

 

We're going to put this private static IntNode class into the Stack class. 

We call it nested classes, and there are times when we should declare it as a static or non-static. 

 

---

Static vs. Non-Static

Static variables in Java is a variable that is shared across all objects of a same class. 

Similarly, static method is a method shared among all objects, and are expected to approach via the Class name. (e.g. Car.getFaster(car1, car2) rather than Ford.getFaster(Tesla, Toyota))

 

However, static class is a little different. 

We declare an inner class static when the inner class has an independent meaning, and non-static otherwise. 

If the nexted inner class NEVER uses any instance variables or methods of the outer class, declare it static. 

 

One analogy is a Car class. 

There are distinct car parts for each car objects, such as wheel, window, engine, etc. 

Those are parts of a car, unliked IntNodes in a Stack. 

 

IntNode, which carry its integer value and pointer to next IntNode, has an independent meaning regardless of Stack. 

IntNode is just a data container, it has no reason to be a part of a specific Stack instance (it's just one element.)

In contrast, whell, window, etc are a PART of a car. 

 

Understanding this, we can continue implementing Stack class with static inner IntNode class.

 

 

---

public class Stack {
    // Stack is Last In First Out
    private static class IntNode {
        int val;
        IntNode next;

        IntNode(int val, IntNode next) {
            this.val = val;
            this.next = next;
        }
    }

    private int size;
    // sentinel.next will work as the 'real' head node
    private IntNode sentinel;

    // Constructor with no value
    public Stack() {
        sentinel = new IntNode(0, null);
        size = 0;
    }

    // Constructor with 1 value
    public Stack(int val) {
        sentinel = new IntNode(0, null);
        sentinel.next = new IntNode(val, null);
        size = 1;
    }

    /**
     * Puts x on top of the stack.
     * Constant runtime.
     */
    public void push(int x) {
        sentinel.next = new IntNode(x, sentinel.next);
        size += 1;
    }

    /**
     * Removes and returns the top item of the stack.
     * Constant runtime.
     */
    public int pop() {
        int returnVal = sentinel.next.val;
        sentinel.next = sentinel.next.next;
        size -= 1;

        return returnVal;
    }

    /**
     * Returns the number of items on the stack.
     * Constant runtime.
     */
    public int size() {
        return size;
    }

    /**
     * Compute the sum of the numbers of the stack.
     * No runtime restrictions.
     */
    public int sum() {
        IntNode currentNode = sentinel.next;
        int result = 0;

        while (currentNode != null) {
            result += currentNode.val;
            currentNode = currentNode.next;
        }

        return result;
    }
}

 

We're using sentinel private class variable as the head node. 

So the 'real' head node is at sentinel.next. 

 

Now, say we want to implement a function that takes a single Stack, returning a reversed Stack, but in a different package. Since we declared all of the instance variables as private, we must use public methods to implement it. 

 

public class StackClient {
    /**
     * Approach:
     * Repeatedly .pop values from s, put into new Stack and return it until size is 0.
     */
    public static Stack flipped(Stack s) {
        Stack newStack = new Stack();

        while (s.size() != 0) {
            int val = s.pop();
            newStack.push(val);
        }

        return newStack;
    }
}

 

It works as intended, but it destroys the original stack by repeatedly calling s.pop().

If we could approach IntNode.next, we could make it non-destructive..

 

But we could fix the code slightly in order to keep the original Stack AND return the new one. 

public class StackClient {
    /**
     * Approach:
     * Repeatedly pop values from s, put into new Stack and return it until size is 0.
     */
    public static Stack flipped(Stack s) {
        Stack newStack = new Stack();
        Stack temp = new Stack();

        // 1. Make two reversed Stack, newStack and temp
        // s becomes empty stack after this
        while (s.size() != 0) {
            int val = s.pop();
            newStack.push(val);
            temp.push(val);
        }

        // 2. Reverse the temp Stack, and save to s
        while (temp.size() != 0) {
            int val = temp.pop();
            s.push(val);
        }
        
        return newStack;
    }
}

 

With this implementation, we could maintain the structure of the original Stack AND return the new reversed Stack.