Your intuition is, in fact, correct. This class does not work properly.
When you enqueue stuff, it works well - adds things at the tail, and everything works.
The trouble starts when you dequeue all the items. When you do that, sentinel.next will become null - you have removed everything from the queue - but tail will still be pointing to the last item you enqueued. So basically you have a tail that's disconnected from your sentinel.
You can enqueue stuff then, and it will be appended after the old tail, but it will no longer be reachable from sentinel. If you try to dequeue anything further, you'll get a NullPointerException.
To demonstrate this, I added the following method to your Queue class (and added the Item class since you didn't put it in your post):
@Override public String toString() { StringBuilder sb = new StringBuilder("Queue: "); for ( Item item = sentinel.next; item != null; item = item.next ) { sb.append('[').append(item.value).append(']'); } return sb.toString(); }
Now, with this main program:
public static void main(String[] args) { Queue queue = new Queue(); queue.enqueue(5); queue.enqueue(10); System.out.println(queue); queue.dequeue(); System.out.println(queue); queue.dequeue(); System.out.println(queue); queue.enqueue(15); queue.enqueue(20); System.out.println(queue); queue.dequeue(); System.out.println(queue); }
You get:
Queue: [5][10] Queue: [10] Queue: Queue: Exception in thread "main" java.lang.NullPointerException at testing.Queue.dequeue(SimpleTest.java:48) at testing.SimpleTest.main(SimpleTest.java:27)
What you should have gotten was:
Queue: [5][10] Queue: [10] Queue: Queue: [15][20] Queue: [20]
To achieve this, you have to correct the tail when you reach it when dequeuing.
public int dequeue () { int value = sentinel.next.value; if ( sentinel.next == tail ) { tail = sentinel; } sentinel.next = sentinel.next.next; return value; }
In truth, one should also protect the dequeue() method against being called when the queue is empty. Throwing a NullPointerException is not nice, a more sensible exception would be nicer. And in fact it helps create a more elegant dequeue(), where instead of correcting the tail, we simply change the sentinel - throw out the old sentinel and use the item we just dequeued as our new sentinel:
public int dequeue () { int value = sentinel.next.value; if ( sentinel.next == null ) { throw new IllegalStateException("No items to dequeue"); } sentinel = sentinel.next; return value; }
If we didn't null-check, then sentinel would become null when we attempt to dequeue, and then we'd never be able to dequeue again. By null-checking, we make sure we have an item to dequeue, and it becomes the sentinel. If it also happens to be the last item in the queue, then we have tail and sentinel pointing to the same item, as they did in the beginning, so we know we can continue adding items and they will be reachable through sentinel.
Note that method for checking whether the queue was empty before attempting to dequeue would also come in handy.
