Implementing a Stack in Java for a technical interview

Question

This code is based off the Stack implementation in Chapter 3 of Cracking The Coding Interview. I modified the code to make it compile and give me the correct output. I'd appreciate any feedback on code style and correctness, assuming that I write this code in a technical interview.

The pseudocode from Cracking the Coding Interview, which is implemented using a linked list:

class Stack {

    Node top;

    Object pop() {
        if (top != null) {
            Node item = top.data;
            top = top.next;
            return item;
        }
        return null;
    }

    void push(Object item) {
        Node t = new Node(item);
        t.next = top;
        top = t;
    }

    Object peek() {
        return top.data;
    }
}

My code:

public class Stack {
    Node first;
    Node last;

    public Stack(Node f, Node l) {
        first = f;
        last = l;
        first.next = last;
    }

    public Stack() {
        first.next = last;
    }

    public void push(Object data) {
        if(first == null) {
            first = new Node(data, null);
        }
        else {
            last.next = new Node(data, null);
            last = last.next;
        }

    }

    public Object pop() {
        if(first == null) {
            return -1;
        }
        else { 
            Object item = last.data;
            Node cur = first;
            while (cur.next.next != null) {
                cur = cur.next;
            }
            last = cur;
            return item;
        }
    }

    public Object peek() {
        if(first == null) {
            return -1;
        }
        Object item = last.data;
        return item;
    }

    public static void main(String[] args) {
        Stack stack = new Stack(new Node(1, null), new Node(2, null));
        stack.push(3);
        System.out.println(stack.peek() == 3);
        stack.pop();
        System.out.println(stack.peek() == 2);
    }

    private static class Node {
        Object data;
        Node next;

        private Node(Object d, Node n) {
            data = d;
            next = n;
        }
    }
}

Answer 1

A stack should not know about the first element. A stack only know about the last element that was pushed, so the Stack object itself should only have one Node called last. Because of this, the constructor should be changed as well to only take one Node ex: public Stack(Node node).

Edit: As @vnp says, Node is private, so it cannot be created outside this class. Either create a constructor which takes an Object, or don't create any constructors and always create an empty Stack.

This constructor doesn't do anything and will throw a NullPointerException:

public Stack() {
    first.next = last;
}

In pop(), you shouldn't need to do any fancy while loops. Just check if last is null and if not, get last's data and set last to last.next:

public Object pop() {
    if(last == null) {
        return -1;
    }
    else {
        Object item = last.data;
        last = last.next;
        return item;
    }   
}

In push(), you should simply set last to be the new Node, and have it point to the old last as it's next:

public void push(Object data) {
    last = new Node(data, last);
}

In peek(), you can change first to last and simply return last.data:

public Object peek() {
    if(last == null) {
        return -1;
    }
    return last.data;
}

One final point: you should not give your variables one character names like d, n, l, and f. If the variables in your constructor should have the same name as the private member variables, then give them the same name and prefix the members with this to differentiate them. For example, you can change the Node constructor to:

private Node(Object data, Node node) {
    this.data = data;
    this.next = node;
}

Answer 2

As usual, revewing a design rather than code.

• As coded, pop takes time proportional to the current stack size. It could and should take constant time. Hint: reverse the semantics of node.next (BTW, first becomes redundant).

• I don't think that pop/peek returning -1 on empty stack is a good idea. A value of -1 is a valid result of popping from a stack of integers. Why not return null? Throwing an exception is also a viable option.

• A client of this implementation cannot use a 2-argument constructor (class Node is private). Therefore it doesn't have a right to exist.

Answer 3

• I would look at this code and think you hadn't messed with Java since before 1.5. You should really be using generics, particularly for a collection-type class like a stack.

• Any value you allow to be pushed onto the stack, is useless as an error code.

  Consider the following code:

  Stack s = new Stack();
  s.push(-1);
  
  ... do lots of pushes and pops ...
  
  Object value = s.pop();
  

  Did i just get an error, or legitimately pop a -1?

  Either prevent the pushing of null and use that as an error code, or throw an exception if there's nothing to pop. The latter is usually preferable.

Answer 4

Stacks are so simple you can practically write them directly from specifications:

1. empty is a Stack<T>
2. push(T, Stack<T>) is a Stack<T>
3. isEmpty(empty) -> true
4. isEmpty(push(t, s)) -> false
5. top(empty) -> error
6. top(push(t, s)) -> t
7. pop(empty) -> error
8. pop(push(t, s)) -> s

This lends itself to the following minimal (immutable) implementation:

public interface Stack<T> {
    // Rule 1
    static final Empty EMPTY = Empty.INSTANCE; 

    // Rule 2
    public Stack<T> push(T value) { return new Push<>(value, this); }

    boolean isEmpty();

    Stack<T> pop();

    T top();
}

class Empty<T> implements Stack<T> {
    protected static final Empty INSTANCE = new Empty();

    // Rule 3
    public boolean isEmpty() { return true; }

    // Rule 7
    public Stack<T> pop() { throw new UnsupportedOperationException("Can not pop an empty stack"); }

    // Rule 5
    public T top() { throw new UnsupportedOperationException("Can not take the top of an empty stack");}
}

class Push<T> implements Stack<T> {
    private final T top;
    private final Stack<T> pop;

    Push(T top, Stack<T> pop) {
        this.top = top;
        this.pop = pop;
    }

    // Rule 4
    public boolean isEmpty() { return false; }

    // Rule 8
    public Stack<T> pop() { return pop; }

    // Rule 6
    public T top() { return top; }
}

Answer 5

In addition to the design problems mentioned by @vnp:

Any algorithm using a stack contains a while the stack is not empty somewhere, so you have to have a public boolean isEmpty() method.

Unless you disallow null values, returning null as a result code is not acceptable, even then inadvisable. You should throw some relevant RuntimeException (as suggested by @Aaronaught), preferebly from the standard libraries: e.g. NoSuchElementException or EmptyStackException etc. If you don't have Java reference documentation available, don't know the modus operandi, if it is a whiteboard interview for example, you can throw IllegalStateException. (Every Java programmer should know basic OOP exceptions: IllegalArgumentException, IllegalStateException... by heart.)

Answer 6

Most important, I won't hire someone who claims to be a Java programmer unless he knows generics and uses them properly. This is 10-year-old technology, people. Get with the program.

Second, using "-1" as an error return is just dumb. What if someone pushes -1? Use null (and forbid pushing it).

Third, why are you keeping track of the bottom of the stack? Seems like a waste of effort, unless I'm missing something.

Finally, the way you are implementing pop is just bananas. The second most common call, and it is O(n)?

A stack is a single-linked list, with only a few methods implemented. Think about that.