Implementing a queue in Java for a technical interview

Question

This code is based off the Queue 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.

public class Queue {
    Node first;
    Node last;


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

    public void enqueue(int data) {
        if( first == null ) {
            last = new Node(data);
            first = last;
        } else {
            last.next = new Node(data);
            last = last.next;
        }
    }

    public int dequeue() {
        if (first != null) {
            int item = first.data;
            first = first.next;
            return item;
        }
        else {
            return -1;
        }
    }

    public static void main(String[] args) {
        Queue queue = new Queue(new Node(2), new Node(3));
        queue.enqueue(4);
        queue.enqueue(5);

        System.out.println(queue.dequeue() == 2);
        System.out.println(queue.dequeue() == 3);
    }

    public static class Node {
        int data;
        Node next;

        public Node(int d) {
            data = d;
        }
    }
}

Answer 1

You don't have a parameterless constructor which forces each queue to be instantiated with 2 elements. This isn't userfriendly since I might very wel want to construct it first and then add 5 bazillion elements to it.

Your code already allows it though: technically first can never be null as it is, yet you check for it. You can add a constructor without a problem.

---

Right now you only accept integers; perhaps you could make it generic to allow for each type?

---

Node is public; I'd change that to private since the outside world should never use it anyway.

---

Your code doesn't work; executing it will return 2 and -1, not 3. This happens because you don't set the next property of the nodes that are passed in to the Queue(Node, Node) constructor.

Answer 2

There is a fundamental flaw with you code that definitely needs to be changed. You misunderstand the reasoning for the Node inner class.

public static class Node {
    int data;
    Node next;

    public Node(int d) {
        data = d;
    }
}

As another answer mentioned, this class is meant to private. You do this, because the implementation of the underlying linked list that keeps track of the user's data should be abstracted from the user. In other words, the only thing the user should be concerned with is adding their data to the queue, and not setting up the nodes for the queue to actually work. The beauty of modern languages is creating classes that people can use by just knowing that it works and not HOW it works. As such, your constructor:

public Queue(Node f, Node l)

needs to be changed. As my above description recommends, a user of your code should only have to pass your queue his/her data rather than the nodes the queue needs to work. Also, this constructor is very weird. It is unlikely that the user has two pieces of data to add to your queue at the construction stage. It would be more useful to create an empty queue. Then the user will have the queue available to fill as they want. I'm sure there are other useful constructors, but an empty queue constructor would be the most useful.

There is also a very slight and almost negligible memory leak. During the dequeue(), you iterate your first variable, however not your last. In the case that there is only one element in your queue and you dequeue(), first will become NULL. However, last will still point to the node. It won't cause problems as your code stands, however, the garbage collector will not pick up that last node because last points to it. It is unnecessary usage of memory. Again, this isn't as big deal, but you should be aware of it.

Other than that, the queue seems to have its basic functionality and work with the user giving ints rather than nodes (of course except in the constructor). If you are looking to expand the workings, I would recommend applying Generics to the queue. Generics are pretty simple to implement, but they are immensely useful.

Answer 3

I was looking into your Stack question, and noticed you were missing boolean isEmpty() method, and I see you are missing it here, too.

Checking if a queue is empty is a fundamental method of any object oriented queue. And you should always check if a queue is empty before calling pop on it, in other words you should never call pop on an empty queue.

See here for example the canonical use case of queues, a breadth-first search, from wikipedia:

1  procedure BFS(G,v) is
2      create a queue Q
3      create a vector set V
4      enqueue v onto Q
5      add v to V
6      while Q is not empty loop
7         t ← Q.dequeue()
8         if t is what we are looking for then
9            return t
10        end if
11        for all edges e in G.adjacentEdges(t) loop
12           u ← G.adjacentVertex(t,e)
13           if u is not in V then
14               add u to V
15               enqueue u onto Q
16           end if
17        end loop
18     end loop
19     return none
20 end BFS