Queue Operations

Operations Overview

A queue exposes a minimal, well-defined set of operations. In interviews, every queue-based algorithm calls only these — knowing them precisely removes all ambiguity from implementation.

Core operations (must know):
  enqueue(value) / offer(value)  → add to back              O(1)
  dequeue()      / poll()        → remove and return front   O(1)
  peek()         / front()       → read front without remove O(1)
  isEmpty()                      → true if no elements       O(1)

Supporting operations:
  size()    → number of elements           O(1)
  clear()   → remove all elements          O(n) or O(1)

All core operations are O(1). The queue never needs to search, compare, or shift elements during these operations — it only ever touches the front or the back.

Implementation 1: Array-Backed Queue

An array-backed queue uses a dynamic array as underlying storage. The front is always array[0] and the back is always array[size - 1]. The critical warning: never use plain array index 0 removal — it is O(n). Use a circular array or dynamic language's built-in.

For clarity in this section, the implementations use the dynamic array built-ins that handle this correctly.

Output:
Queue (front→back): [10, 20, 30]
Peek:    10
Size:    3
Dequeue: 10
Dequeue: 20
Queue (front→back): [30]
isEmpty: false
After clear isEmpty: true

Implementation 2: Linked-List-Backed Queue

A linked-list-backed queue maintains both a head (front) and a tail (back) pointer. Enqueue attaches a new node to the tail — O(1). Dequeue removes the head node — O(1). Both operations are true O(1) with no amortized cost.

Linked-list queue state:

  head → [10] → [20] → [30] ← tail
  front                       back

  Enqueue 40: new node(40), tail.next = node(40), tail = node(40)
  head → [10] → [20] → [30] → [40] ← tail

  Dequeue: value = head.data = 10, head = head.next = node(20)
  head → [20] → [30] → [40] ← tail   returns 10

Output:
Queue (front→back): [A, B, C]
Peek:    A
Size:    3
Dequeue: A
Dequeue: B
Queue (front→back): [C]
After clear: Queue: [] (empty)

Dry Run: Enqueue and Dequeue Sequence

Tracing every pointer change in the linked-list queue:

LinkedQueue, head=null, tail=null, size=0

enqueue("A"):
  newNode = Node("A")
  tail == null → head = node(A), tail = node(A)
  size = 1
  State: head → [A] ← tail

enqueue("B"):
  newNode = Node("B")
  tail.next = node(B)       → [A] → [B]
  tail      = node(B)
  size = 2
  State: head → [A] → [B] ← tail

enqueue("C"):
  newNode = Node("C")
  tail.next = node(C)       → [A] → [B] → [C]
  tail      = node(C)
  size = 3
  State: head → [A] → [B] → [C] ← tail

peek():
  return head.data = "A"   ← head unchanged

dequeue():
  value = head.data = "A"
  head  = head.next = node(B)
  head ≠ null → tail unchanged
  size = 2
  returns "A"
  State: head → [B] → [C] ← tail

dequeue():
  value = head.data = "B"
  head  = head.next = node(C)
  size = 1
  returns "B"
  State: head → [C] ← tail

dequeue():
  value = head.data = "C"
  head  = head.next = null
  head == null → tail = null   ← MUST clear tail when queue empties
  size = 0
  returns "C"
  State: head=null, tail=null

Operation 1: Enqueue — Deep Dive

Enqueue places a new element at the back. Both array-backed and linked-list-backed give O(1).

Linked-list enqueue — three cases:

Case 1: Empty queue (head == null, tail == null)
  New node becomes both head AND tail.
  head = newNode; tail = newNode;
  Critical: forgetting to set head causes a broken queue where
  the tail is set but peek/dequeue crash on null head.

Case 2: Non-empty queue (standard)
  tail.next = newNode;   // old tail points forward to new node
  tail      = newNode;   // new node becomes the new tail
  head is unchanged.

Array-backed enqueue:
  data.add(value);       // append to end — O(1) amortized
  No index tracking needed — the array manages its own size.

Operation 2: Dequeue — Deep Dive

Dequeue removes and returns the front element. The most critical edge case is dequeuing from an empty queue.

Linked-list dequeue — two cases:

Case 1: Queue becomes empty after dequeue (head.next == null)
  value = head.data
  head  = head.next  → head = null
  MUST also set tail = null   ← forgetting this is the #1 linked queue bug
  If tail still points to the deleted node, the next enqueue will
  corrupt the list (tail.next = newNode on a deleted node).

Case 2: Queue still has elements (head.next != null)
  value = head.data
  head  = head.next
  tail is unchanged.

Safe vs throwing dequeue (Java):
  poll()    → returns null if empty — safe
  remove()  → throws NoSuchElementException if empty — throwing

Output (Java):
remove():    10
removeFirst(): 20
poll():      30
pollFirst(): null
remove() on empty throws: NoSuchElementException
Safe dequeue: 42

Operation 3: Peek — Reading Without Consuming

Peek reads the front element without removing it. It is O(1) and does not change the queue's state.

Why peek matters in queue algorithms:

  BFS example:
    Before processing the front node, check if it is the target.
    If yes, return — no need to dequeue unnecessarily.
    But: in most BFS implementations, you dequeue then check —
    peek is less commonly needed than in stack algorithms.

  Where peek IS essential:
    Sliding window maximum (monotonic deque):
      Peek the front to check if it has expired (outside the window).
      Only dequeue it if it is outside. Peek avoids unconsuming.

    Two-queue median or priority simulations:
      Peek both queue fronts to decide which is smaller before dequeuing.

Method Variant Comparison (Java)

Java's Queue/Deque interface provides two variants for each operation: one that throws on failure and one that returns a sentinel value. Always use the sentinel-returning variant (offer/poll/peek) in algorithm code.

Rule of thumb:
  Use offer/poll/peek in interview code — they never throw.
  State "I'll use poll() which returns null on empty" and move on.
  This shows you know the API and avoids unnecessary try-catch.

Operation Complexity Summary

Common Mistakes Beginners Make

Not clearing tail when the queue becomes empty after dequeue. In linked-list implementation, after the last dequeue, head becomes null — but tail still points to the deleted node. The next enqueue sets tail.next = newNode on a dangling pointer, silently corrupting the list. Always check if (head == null) tail = null immediately after moving head.

Using list.pop(0) or array.shift() as dequeue. Both are O(n) — they shift every element one position. In a BFS over n nodes, this turns O(n) BFS into O(n²). Always use collections.deque.popleft() in Python and a circular array or linked-list implementation in JavaScript.

Calling queue.remove() or queue.element() instead of queue.poll() / queue.peek() in Java. The throwing variants crash if the queue is empty. In BFS and most algorithm code, the queue empties as a normal part of execution — use poll() which returns null, and check with isEmpty() before loops.

Forgetting to handle the single-element queue case in linked implementation. When a queue has one element and you dequeue it, both head and tail become null. But if only head is set to null without clearing tail, the queue appears empty to isEmpty() (which checks head == null) but tail still points to stale memory. The next enqueue then sets tail.next = newNode on garbage.

Calling front() or pop() on an empty std::queue in C++. Unlike Java or Python, C++ does not throw an exception — it is undefined behavior. The program may crash, return garbage, or silently corrupt memory. Always call empty() before front() or pop() in C++.

Interview Questions

Q: What is the time complexity of dequeue and why does implementation choice matter?

For a linked-list-backed queue, dequeue is O(1) — move the head pointer forward, return the old head's data. For a circular-array-backed queue, dequeue is also O(1) — increment the front index and return the old value. For a plain (non-circular) array, dequeue is O(n) — every element shifts left to fill the gap at index 0. The implementation choice is critical: using a plain array for a queue turns every O(n) BFS into O(n²) because each dequeue during the traversal costs O(n).

Q: In Java, what is the difference between poll() and remove() on a Queue?

Both dequeue from the front. remove() throws NoSuchElementException when the queue is empty. poll() returns null when the queue is empty — it never throws. For algorithm and interview code, poll() is always preferred because an empty queue is a normal terminal state in BFS and other queue-based algorithms, not an exceptional condition. Similarly, peek() returns null while element() throws, and offer() returns false while add() throws.

Q: Why must tail be set to null when the last element is dequeued from a linked-list queue?

After the last dequeue, head becomes null — correctly signalling an empty queue. But if tail still points to the just-deleted node, the pointer is dangling. The next call to enqueue() enters the non-empty branch (because tail != null) and sets tail.next = newNode on the deleted memory. This corrupts the queue — the new node is attached to a stale, possibly freed node. Setting tail = null whenever head becomes null prevents this.

FAQs

In C++, why does queue::pop() return void?

The same reason as stack::pop() — exception safety. If pop() returned a value by copy and the copy constructor threw, the element would be removed without being successfully returned — data lost. The two-step front() + pop() separates read from remove: if the copy in front() throws, the element is still in the queue. This is deliberate C++ API design. In C++17 and later, std::optional<T> could return the value safely, but the API remains void for backward compatibility.

Should I use ArrayDeque or LinkedList as a Queue in Java?

ArrayDeque for almost everything. It is array-backed with automatic resizing — better cache locality, no per-node allocation overhead (no pointer per element), and 2-3x faster in benchmarks than LinkedList. Use LinkedList only when you also need mid-list operations or need both List and Queue operations simultaneously on the same object. The Java docs explicitly recommend ArrayDeque over LinkedList for stack and queue use.

Can I use queue.size() to check emptiness instead of queue.isEmpty()?

Yes, but isEmpty() is clearer and is O(1) for all implementations. size() == 0 is also O(1) for standard implementations. Use isEmpty() — it directly expresses intent and avoids any ambiguity about zero-size vs null.

Quick Quiz

Question 1: For a linked-list queue, which pointer must be updated during enqueue?

• ›A) Only head
• ›B) Only tail
• ›C) Both head and tail when empty; only tail when non-empty
• ›D) Always both head and tail

Answer: C) Both when empty, only tail when non-empty. If the queue is empty, the new node becomes both head and tail — both must be set. If the queue is non-empty, the new node is appended by setting tail.next = newNode and then tail = newNode. The head is never changed during enqueue (it still points to the original front element).

Question 2: queue.poll() is called on an empty Java ArrayDeque. What is returned?

• ›A) 0
• ›B) Throws NoSuchElementException
• ›C) null
• ›D) Throws EmptyQueueException

Answer: C) null. poll() is the safe variant — it returns null when the queue is empty instead of throwing. Use remove() if you want the exception. In interview code, always use poll() to avoid crashes when the queue empties.

Question 3: What is wrong with using list.pop(0) as dequeue in Python inside a BFS loop over n nodes?

• ›A) It removes the wrong element — should use list.pop(-1)
• ›B) Each pop(0) is O(n) due to element shifting; n calls = O(n²) total
• ›C) Python lists cannot be used with BFS
• ›D) pop(0) throws IndexError when the list is empty

Answer: B) O(n²) total. list.pop(0) removes the first element by shifting all remaining elements left — O(n). Called n times in a BFS over n nodes, total cost is O(n²). Use collections.deque.popleft() which is O(1) — BFS stays O(V + E).

Question 4: In the linked-list queue, after dequeuing the LAST element, what must happen to tail?

• ›A) tail should remain pointing to the last dequeued node for reference
• ›B) tail should be set to head (which is now null)
• ›C) tail must be set to null — otherwise the next enqueue corrupts the list
• ›D) tail is automatically cleared when head becomes null

Answer: C) tail must be explicitly set to null. When head = head.next results in head == null, the queue is empty. But tail still holds a pointer to the just-removed node. The next enqueue() call enters the non-empty branch (because tail != null) and sets tail.next = newNode on the deleted memory — undefined behavior in C++, dangling reference in Java/Python, silent corruption. Setting tail = null whenever head becomes null is mandatory.

Summary

Queue operations are O(1) for enqueue, dequeue, and peek — but only if the underlying implementation is correct. The plain array is the hidden O(n) trap.

The complete operation reference:

• ›enqueue(value) — O(1) amortized (array) or O(1) (linked list) — always at the back
• ›dequeue() — O(1) circular array or linked list, O(n) plain array — removes and returns front
• ›peek() — O(1) — reads front without consuming — use peek()/poll() in Java, not throwing variants
• ›isEmpty() — O(1) — essential guard before every dequeue/peek
• ›size() — O(1) — stored as a field
• ›clear() — O(1) GC languages / O(n) C++ (must free each node)

Linked-list queue: maintain both head (front) and tail (back) — update tail on enqueue, update head on dequeue, clear tail when queue becomes empty.

Array-backed queue: use collections.deque (Python), ArrayDeque (Java), std::queue (C++), or implement circular array — never use plain array index-0 removal.

In Java, always use offer/poll/peek — the null-returning safe variants. Never call element() or remove() in algorithm code where empty is a normal terminal state.

In the next topic you will explore Queue Implementation — building a complete queue from scratch with both the linked-list and circular array approaches, with full edge case coverage and resize logic.