Implementing a Stack in Java for 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;
        }
    }
}

Can you quote the problem, especially the constraints? Are you not to use generics? Can you use any standard collections at all? Do you have to use linked lists?... — abuzittin gillifirca, Jun 6 at 7:20
You should use generic types. Using objects is outdated and bad practice for these types of situations. — Anubian Noob, Jun 6 at 8:51
I think an interview, the biggest question after seeing this code, would be "Why no generics?" and it's immediately what struck my eye. Generics greatly improve the usability of collections. Nobody likes excessive casting — Cruncher, Jun 6 at 15:58
No private, no final modifiers? Not the first thing to catch my eye, but certainly the second after the missing generics. — Voo, Jun 6 at 20:02
I added the pseudocode (which doesn't use generics and does use a linked list) and fixed obvious issues with my code to make it more in line with the pseudocode. — mathonsunday, Jun 6 at 21:27

stiemannkj1 · Accepted Answer · 2014-06-06 14:15:13Z

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;
}

public Stack(Node node) is impossible because class Node is private. I'd just construct an empty stack. — vnp, Jun 6 at 1:38
" and will probably throw a NullPointerException" No, it won't. — abuzittin gillifirca, Jun 6 at 6:24
@abuzittingillifirca actually, I just tested the code, and it does throw a NullPointerException. — stiemannkj1, Jun 6 at 14:13
There shouldn't be any answer to this question that doesn't at least mention the use of generics. — BobbyDigital, Jun 6 at 16:12

vnp · Answer 2 · 2014-06-06 01:43:53Z

up vote 13 down vote

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.

edited Jun 6 at 1:43

answered Jun 6 at 1:33

vnp
2,998219

7

Throwing an exception is not simply a viable option, it's the correct one on a pop. Popping an empty stack is an invalid operation - specifically, a stack underflow. With peek you could maybe be a bit more lenient, but better to be consistent. – Aaronaught Jun 6 at 2:37

Aaronnaught, "correct" statement is an absolute statement, but throwing an exception is not always the correct option. I would consider taking a queue from the Java Deque interface on this one. – corsiKa Jun 6 at 2:54

Depending on your design goals, it might be ok to store null values in the Stack Then you need Exceptions. If you would even need magical values like -1, at least use a public constant for it. – RobAu Jun 6 at 6:39

2

Any value that could be misinterpreted as a valid entry in the stack (like -1) is not a useful error code. If i can't easily tell the difference between legitimately popping a value and underflowing the stack, that's a design error. null isn't currently an option either, since the stack allows it to be pushed. (It could be, though, if push(null) threw an IllegalArgumentException or something. But then you're already throwing exceptions; might as well throw a "stack underflow" exception as well.) – cHao Jun 6 at 7:05

@corsiKa taking a queue from the deque ;) – grkvlt Jun 7 at 14:26

add comment

cHao · Answer 3 · 2014-06-06 07:21:53Z

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.

abuzittin gillifirca · Answer 4 · 2014-06-06 07:10:34Z

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.)

Cristian Ciupitu · Answer 5 · 2014-06-07 19:23:32Z

up vote 5 down vote

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

empty is a Stack<T>
push(T, Stack<T>) is a Stack<T>
isEmpty(empty) -> true
isEmpty(push(t, s)) -> false
top(empty) -> error
top(push(t, s)) -> t
pop(empty) -> error
pop(push(t, s)) -> s

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

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

    Stack<T> push(T value);
    boolean isEmpty();
    Stack<T> pop();
    T top();
}

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

    @Override
    public Stack<T> push(T value) { return new Push<>(value, this); }

    @Override
    public boolean isEmpty() { return true; }

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

    @Override
    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;
    }

    @Override
    public Stack<T> push(T value) { return new Push<>(value, this); }

    @Override
    public boolean isEmpty() { return false; }

    @Override
    public Stack<T> pop() { return pop; }

    @Override
    public T top() { return top; }
}

edited Jun 7 at 19:23

Cristian Ciupitu
1484

answered Jun 6 at 21:37

jon-hanson
1511

How do you start a stack? There's no accessible constructors and the EMPTY is package-private? – Kenzie Togami Jun 8 at 2:31

Stack<Integer> intStack = Stack.EMPTY.push(7).push(10); – jon-hanson Jun 10 at 7:06

But Stack.EMPTY is package-private, is this not supposed to be public? – Kenzie Togami Jun 10 at 14:33

Stack is an interface, so all members are implicitly public, including the EMPTY field. – jon-hanson Jun 11 at 6:22

Oh, I'm still not used to that, even though I've known about it for months. Sorry! – Kenzie Togami Jun 11 at 14:53

add comment

Malvolio · Answer 6 · 2014-06-06 11:05:23Z

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.

asked	1 month ago
viewed	1946 times
active	28 days ago

current community

your communities

more stack exchange communities

Implementing a Stack in Java for Technical Interview

6 Answers

Your Answer

Not the answer you're looking for? Browse other questions tagged java interview-questions linked-list stack or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

Implementing a Stack in Java for Technical Interview

6 Answers

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged java interview-questions linked-list stack or ask your own question.

Related

Hot Network Questions