Queue Collection Frameworks

Why Built-In Queue Implementations?

Every major language ships a production-quality queue in its standard library. These implementations are tested, optimised, and immediately available — in interviews and production code, always reach for the built-in first.

Understanding which built-in to choose — and the exact API — separates engineers who know the language from those who guess.

Language    Recommended Queue             Thread-Safe Alternative
──────────────────────────────────────────────────────────────────────
Java        Queue<E> via ArrayDeque<E>    BlockingQueue (LinkedBlockingQueue)
Python      collections.deque             queue.Queue / queue.SimpleQueue
C++         std::queue<T>                 (manual mutex or concurrent library)
JavaScript  Array (approximation)         No standard built-in thread-safe queue

Java: The Queue<E> Interface

Java's queue is an interface — you choose the implementation that backs it. The Queue<E> interface defines the full contract; the implementation choice determines the internal structure and performance.

Java Queue Implementations (all implement Queue<E>):

ArrayDeque<E>        — array-backed, O(1) both ends, NOT thread-safe
                       RECOMMENDED for most use cases

LinkedList<E>        — linked-list-backed, O(1) both ends, NOT thread-safe
                       Use when also needing List operations

PriorityQueue<E>     — heap-backed, dequeue returns smallest element
                       NOT FIFO — orders by priority, not arrival

LinkedBlockingQueue<E> — linked-list, BOUNDED optional, THREAD-SAFE
                         For producer-consumer concurrent patterns

ArrayBlockingQueue<E>  — circular array, BOUNDED, THREAD-SAFE
                         Bounded concurrent queue with backpressure

Declaration and Initialization

Output (Java):
ArrayDeque:   0
From list:    [A, B, C]
From list peek: A

Java Queue API — Full Reference

Output (Java):
After enqueues: [10, 20, 30]
peek():    10
element(): 10
poll():    10
remove():  20
After dequeues: [30]
isEmpty(): false
poll() on empty:   null
peek() on empty:   null
remove() on empty: throws NoSuchElementException
Drain: 1 2 3 4 5

Java: ArrayDeque vs LinkedList as Queue

Both implement the Queue<E> interface with identical method signatures. The choice is a performance and memory trade-off.

ArrayDeque<E>:
  Internal storage: resizable circular array
  Memory per element: object reference only (~8 bytes)
  Cache performance: excellent — contiguous array, prefetch-friendly
  Resizing: amortized O(1) per enqueue — doubles when full
  Null elements: NOT allowed — throws NullPointerException
  Use when: general FIFO queue, most algorithm problems

LinkedList<E>:
  Internal storage: doubly linked list
  Memory per element: ~48 bytes (prev ptr, next ptr, data ptr, object header)
  Cache performance: poor — nodes scattered across heap
  Resizing: never needed — each node allocated individually
  Null elements: allowed
  Use when: also need mid-queue insertion/deletion with iterators,
            or need both Queue and List operations simultaneously

Performance comparison (n = 10 million operations):
  ArrayDeque enqueue+dequeue: ~0.8s
  LinkedList enqueue+dequeue: ~2.5s
  ArrayDeque is ~3x faster in practice.

Python: queue.Queue — Thread-Safe Queue

collections.deque is not thread-safe for concurrent producers and consumers. Python's queue module provides thread-safe options.

Output (Python thread-safe):
Non-blocking get: 10
Blocking get: 20
Timed get: 30
task_done + join: all processed
  Consumed: 0
  Consumed: 10
  ...
All produced items consumed.

C++: std::queue vs std::deque

std::queue is a container adapter that restricts access. std::deque is the full underlying container with additional capabilities.

std::queue<T>:
  Wraps a container (deque by default) and exposes ONLY:
    push(val)   — enqueue to back
    pop()       — dequeue from front (RETURNS VOID)
    front()     — peek front
    back()      — peek back
    empty()     — isEmpty check
    size()      — element count
  No random access, no iterators, no clear()

std::deque<T> (underlying container):
  Full double-ended container:
    push_back / push_front    — O(1) both ends
    pop_back / pop_front      — O(1) both ends
    operator[]                — O(1) random access
    begin/end                 — full iterator support
    clear()                   — O(n) erase all
    insert / erase            — O(n) mid-sequence

When to prefer std::deque over std::queue:
  Need iterators or range-based for loops
  Need clear()
  Need random access by index
  Building a sliding window algorithm
  Need to inspect non-front elements

Complete API Comparison Table

When to Use Each

Java:
  Queue<E> via ArrayDeque<E>  → standard FIFO, algorithm problems
  Queue<E> via LinkedList<E>  → only if also needing List operations
  Deque<E> via ArrayDeque<E>  → sliding window, monotonic deque
  BlockingQueue               → producer-consumer, concurrent patterns

Python:
  collections.deque           → all algorithm problems, BFS
  queue.Queue                 → multi-threaded producer-consumer
  queue.SimpleQueue           → multi-threaded, no task_done needed
  list (pop(0))               → NEVER for queues — O(n) dequeue

C++:
  std::queue<T>               → pure FIFO, simplest API
  std::queue<T, list<T>>      → guaranteed O(1), no amortized
  std::deque<T>               → need iterators, clear(), random access
  Custom ThreadSafeQueue      → concurrent producer-consumer

JavaScript:
  Map-based Queue             → O(1) both ends, algorithm problems
  Array + shift()             → only for tiny n where O(n) is acceptable
  Array + two-pointer         → simulate queue with read/write index

Common Mistakes Across All Languages

Java: Using remove() instead of poll() in BFS. remove() throws NoSuchElementException when the queue is empty. In BFS, the queue naturally empties — this causes a crash at the algorithm's end if remove() is used. Always use poll() (returns null) in BFS and algorithm code.

Python: Using list.pop(0) as dequeue. pop(0) is O(n) — it shifts every remaining element. In BFS over n nodes, this is O(n²) total. Always use collections.deque.popleft() which is O(1).

C++: Calling front() or pop() on an empty std::queue. Both are undefined behavior — no exception, the program may crash or silently corrupt memory. Always check empty() first. Unlike Java and Python, C++ has no safe null-returning alternative.

C++: Expecting queue::pop() to return the removed value. It returns void. Read front() then call pop() — two separate steps. Many developers expect pop() to return the element (like Java/Python) and introduce a silent bug.

Python: Using queue.Queue when collections.deque is intended. queue.Queue has blocking behaviour and task tracking (task_done/join) — unnecessary overhead for single-threaded algorithm work. Use collections.deque for algorithmic problems; queue.Queue only for multithreaded scenarios.

JavaScript: Not accounting for Array.shift() O(n) complexity. It looks like a simple dequeue but is O(n). For interview problems with n > 1000 or performance benchmarks, use the Map-based Queue or a similar O(1) implementation.

Interview Questions

Q: What is the difference between offer() and add() in Java's Queue interface?

Both enqueue an element to the back. add() throws IllegalStateException if the queue is at capacity — relevant for bounded queues. offer() returns false instead of throwing. For ArrayDeque (unbounded), both always succeed and behave identically. In algorithm code, offer/poll/peek are always preferred over add/remove/element — the former trio never throws when empty or full, making BFS and similar algorithms cleaner and safer.

Q: Why is collections.deque preferred over list for queue operations in Python?

deque.popleft() is O(1) — it updates an internal block pointer without moving any elements. list.pop(0) is O(n) — it shifts every remaining element one position left to fill the gap. For a BFS traversal over n nodes, list.pop(0) gives O(n²) total while deque.popleft() gives O(n). The API is equally simple; the performance difference is dramatic at scale.

Q: In C++, what is the difference between std::queue and std::deque?

std::queue is a container adapter — it wraps std::deque (by default) and exposes only FIFO operations: push, pop (void), front, back, empty, size. No iterators, no clear(), no random access. std::deque is the full container that std::queue wraps — it has push_back/push_front, pop_back/pop_front, operator[], full iterators, and clear(). Use std::queue when you want the interface to enforce FIFO discipline. Use std::deque when you need the full double-ended capability or iterators.

Quick Quiz

Question 1: In Java, queue.poll() vs queue.remove() on an empty ArrayDeque:

• ›A) Both return null
• ›B) Both throw NoSuchElementException
• ›C) poll() returns null; remove() throws NoSuchElementException
• ›D) poll() throws; remove() returns null

Answer: C) poll() returns null; remove() throws. This is the safe vs throwing API distinction. In BFS and other algorithm code, always use poll() to avoid crashes when the queue empties normally.

Question 2: Python list.pop(0) in a BFS over n nodes gives what total complexity?

• ›A) O(n) — same as deque.popleft()
• ›B) O(n log n) — binary search involved
• ›C) O(n²) — each pop(0) is O(n), called n times
• ›D) O(1) — Python optimises index-0 removal

Answer: C) O(n²). list.pop(0) shifts all remaining elements left — O(n). Called n times in BFS: O(n) × n = O(n²). Use collections.deque.popleft() for O(1) dequeue and O(n) total BFS.

Question 3: In C++, std::queue<int> q; q.push(5); int val = q.pop(); — what is wrong?

• ›A) push should be enqueue
• ›B) q.pop() returns void — cannot assign to val
• ›C) std::queue does not exist
• ›D) int val should be auto val

Answer: B) q.pop() returns void. In C++, std::queue::pop() removes the front element and returns nothing. The correct pattern is: int val = q.front(); q.pop(); — read then remove, two separate calls.

Question 4: Which Python option should you use for a multi-threaded producer-consumer pattern?

• ›A) collections.deque — fastest O(1) operations
• ›B) list — simplest API
• ›C) queue.Queue — thread-safe with blocking and task tracking
• ›D) queue.SimpleQueue — fastest thread-safe option

Answer: C) queue.Queue. collections.deque operations are atomic for single appends/pops but the deque itself is not thread-safe for combined check-then-act patterns. queue.Queue provides thread-safe put/get with optional blocking, timeout, and task_done/join for producer-consumer synchronisation. queue.SimpleQueue is lighter-weight but lacks maxsize and task_done.

Summary

Every major language provides a production-quality queue through its standard library. The choice within each language matters for correctness, performance, and thread safety.

Key decisions to carry forward:

• ›Java — always use Queue<E> with ArrayDeque<E> via offer/poll/peek; use LinkedList only if also needing List operations; use BlockingQueue for concurrent patterns
• ›Python — use collections.deque with append/popleft/[0] for all algorithm problems; never use list.pop(0) (O(n)); use queue.Queue for multithreaded producer-consumer
• ›C++ — std::queue<T> for pure FIFO; std::deque<T> when iterators, clear(), or random access are needed; pop() returns void — always read front() first
• ›JavaScript — no built-in O(1) queue; use a Map-based queue for correct O(1); Array.shift() is O(n) — acceptable only for small n in simple interview problems
• ›contains() / x in q is O(n) on all implementations — queues are not designed for membership testing
• ›Thread-safe queues: Java BlockingQueue, Python queue.Queue — collections.deque and ArrayDeque are NOT thread-safe
• ›C++ std::queue::pop() is the most common cross-language mistake — returns void, not the value

In the next topic, you will explore the Circular Queue — the fixed-size ring buffer that underlies all circular array queue implementations, with full modulo arithmetic and its real-world applications.