Tracing the LinkedQueue

Let’s trace a sequence of operations and see how head, tail, and the nodes change. We will use the same values we used when tracing the stacks. In each diagram below, head points at the leftmost node, and tail is marked under the node it points at.

We start with new LinkedQueue<>(). An empty queue is just two null references:

          (empty queue — head and tail are null)

enqueue(4) hits the empty case: head and tail both point at the new node:

          ┌───┐
head ───▶ │ 4 │ ──▶ null
          └───┘
            ▲
            │
          tail

enqueue(9) is the general case: link the new node after the current tail, then move tail to it. head does not move:

          ┌───┐      ┌───┐
head ───▶ │ 4 │ ──▶  │ 9 │ ──▶ null
          └───┘      └───┘
                       ▲
                       │
                     tail

enqueue(6) does the same:

          ┌───┐      ┌───┐      ┌───┐
head ───▶ │ 4 │ ──▶  │ 9 │ ──▶  │ 6 │ ──▶ null
          └───┘      └───┘      └───┘
                                  ▲
                                  │
                                tail

Now front() returns 4 and changes nothing. When we traced the stacks on the same input, top() at this point returned 6. The stack gives back the newest item, and the queue gives back the oldest.

Then dequeue() runs head = head.next. The head advances to the node holding 9, and the node holding 4 is no longer reachable from the queue:

          ┌───┐      ┌───┐
head ───▶ │ 9 │ ──▶  │ 6 │ ──▶ null
          └───┘      └───┘
                       ▲
                       │
                     tail

          ┌───┐
          │ 4 │   (no longer reachable)
          └───┘

A second dequeue() advances head to the node holding 6. One item is left, and head and tail point at the same node again:

          ┌───┐
head ───▶ │ 6 │ ──▶ null
          └───┘
            ▲
            │
          tail

enqueue(2) links a new node after the tail and moves tail to it:

          ┌───┐      ┌───┐
head ───▶ │ 6 │ ──▶  │ 2 │ ──▶ null
          └───┘      └───┘
                       ▲
                       │
                     tail

A final front() returns 6.

Notice that only dequeue moves head, and only enqueue moves tail.