# 3.20 Queue via List

A queue is a first-in, first-out structure. The first value inserted is the first value removed. A singly linked list implements a queue efficiently when the structure keeps both a head pointer and a tail pointer.

The head points to the next node to remove. The tail points to the last node inserted.

```text id="f4m8p2"
Queue {
  head : Node | null
  tail : Node | null
}
```

## Structure

Each node stores a value and a pointer to the next node.

```text id="k7q1v5"
Node {
  value
  next : Node | null
}
```

The queue invariant is:

```text id="n6r3x9"
if head == null, then tail == null
if head != null, then tail != null
tail.next == null
```

An empty queue has both pointers set to `null`.

## Enqueue

To enqueue, append a node at the tail.

```text id="h8v2c4"
enqueue(queue, value):
  node = Node(value)
  node.next = null

  if queue.tail == null:
    queue.head = node
    queue.tail = node
  else:
    queue.tail.next = node
    queue.tail = node
```

The empty case is special because there is no old tail. After inserting the first node, both `head` and `tail` must point to that node.

## Dequeue

To dequeue, remove the head node.

```text id="p1x9d6"
dequeue(queue):
  if queue.head == null:
    error

  node = queue.head
  queue.head = node.next

  if queue.head == null:
    queue.tail = null

  node.next = null
  return node.value
```

The important edge case is removing the only node. After removal, `head` becomes `null`, so `tail` must also become `null`.

## Peek

Return the front value without removing it.

```text id="c9m7q2"
peek(queue):
  if queue.head == null:
    error
  return queue.head.value
```

## Empty Check

```text id="v3b8k1"
is_empty(queue):
  return queue.head == null
```

Because the invariant requires `head` and `tail` to be null together, checking `head` is enough.

## Execution Trace

Start with an empty queue.

```text id="u6n4r8"
head = null
tail = null
```

After enqueueing `1`, `2`, and `3`:

```text id="z5k2h7"
head
 |
 v
1 -> 2 -> 3 -> null
          ^
          |
         tail
```

After one dequeue:

```text id="q4t9m2"
head
 |
 v
2 -> 3 -> null
     ^
     |
    tail
```

The removed node `1` is detached from the list.

## Why the Tail Pointer Matters

Without a tail pointer, enqueue requires walking to the end of the list.

```text id="w8p3s5"
cur = head
while cur.next != null:
  cur = cur.next
cur.next = node
```

That makes enqueue O(n). With a tail pointer, enqueue is O(1).

## Complexity

| Operation | Time | Space |
| --------- | ---: | ----: |
| Enqueue   | O(1) |  O(1) |
| Dequeue   | O(1) |  O(1) |
| Peek      | O(1) |  O(1) |
| is_empty  | O(1) |  O(1) |

The queue stores one node per element, so total storage is O(n).

## Ownership Considerations

In a manual-memory language, dequeue should either return the node to the caller or free it after extracting the value.

```text id="r2x6c9"
node = queue.head
queue.head = node.next
node.next = null
free(node)
```

In a garbage-collected language, detaching the node is usually enough.

## Queue with Dummy Head

A dummy head can simplify dequeue logic, but the queue still needs a tail pointer for O(1) enqueue.

```text id="y7m5p2"
dummy.next = null
tail = dummy
```

Enqueue:

```text id="k8c1d4"
tail.next = node
tail = node
```

Dequeue:

```text id="s9q6v3"
if dummy.next == null:
  error

node = dummy.next
dummy.next = node.next

if dummy.next == null:
  tail = dummy

node.next = null
return node.value
```

This version has a stable node before the first real element. The empty queue condition becomes `dummy.next == null`.

## Common Failure Modes

The most common bug is forgetting to reset `tail` when the last node is removed. This leaves `tail` pointing to a detached node.

Another common bug is forgetting to set `node.next = null` before appending. If the node was previously part of another list, it may carry stale links into the queue.

A third bug is implementing enqueue without a tail pointer and accidentally making every enqueue O(n).

## Key Insight

A linked-list queue needs two endpoints. The head supports O(1) removal from the front, and the tail supports O(1) insertion at the back. Correctness depends on keeping both endpoints consistent, especially when the queue changes between empty and non-empty states.