Queue Implementation in Different Languages

A queue enforces FIFO ordering by exposing only two mutation points — insert at the tail, remove from the head — and every language's "built-in queue" is really the same underlying mechanism (a resizable circular buffer, or a doubly linked list) wrapped behind that narrow interface so both operations stay O(1) instead of degrading into O(n) array shifting.

Recognize the pattern

• Problem talks about processing items in the order they arrived — scheduling, BFS frontier, task buffering, rate limiting, producer/consumer.
• You need fast insert-at-one-end / remove-at-other-end, and you do NOT need random access to the middle.
• You're tempted to reach for a plain array/list and call remove(0) or pop(0) repeatedly — that's the tell you need a real queue, not an array.

Brute force vs optimal

Brute force: a plain dynamic array (Python list, Java ArrayList) where dequeue = remove(0). Every removal must shift all remaining elements left by one slot to keep the array contiguous, costing O(n) per dequeue and O(n²) for n operations.

Optimal: a circular buffer (ring buffer) with head/tail indices that wrap modulo capacity, or a doubly linked list with head/tail references. Both give O(1) enqueue and O(1) dequeue because no shifting is ever needed — pointers move instead of elements.

Complexity, derived

Array-shift queue: dequeuing the front element touches every one of the remaining k elements to slide them down, so n sequential dequeues do 0+1+2+…+(n-1) = n(n-1)/2 element moves → O(n²) total, O(1) space beyond the array.

Circular buffer: enqueue writes to buf[tail] then does tail = (tail+1) % capacity — a fixed number of arithmetic ops regardless of how full the buffer is. Dequeue reads buf[head] then head = (head+1) % capacity. Both are O(1) time, and when the buffer fills it doubles (amortized O(1) per op, same argument as dynamic-array growth: total copy work across n inserts is n+n/2+n/4+… < 2n). Space is O(n) for n stored elements, with occasional O(n) transient copy during a resize.

Linked-list queue: O(1) time per op (pure pointer relinking), O(n) space plus one extra pointer per node overhead — no resize ever needed, but worse cache locality than the array version.

Language cheat-sheet

Note the source table's claim that Java's queue API is java.util.Queue and Python's is queue.Queue is misleading for algorithm work: Queue is an interface (use ArrayDeque as the implementation), and queue.Queue is a thread-safe, lock-based queue meant for cross-thread producer/consumer pipelines — for plain single-threaded FIFO use collections.deque, which is what interview code should use.

Worked example: circular buffer trace

Capacity 4 buffer, enqueue 10, 20, 30, dequeue, enqueue 40, 50 (triggers growth). This trace picks one concrete resolution of the full-vs-empty ambiguity flagged in Pitfalls below: it always leaves one slot empty, defining full as size == capacity − 1 (size = count of live elements). That guarantees head == tail can only ever mean empty, never full, so no separate counter is needed — the trade-off is one wasted slot per buffer.

Step 5 is the one to check by hand: tail was 3 going in, so 40 is written to index 3 — not index 0. Index 0 only becomes the write target after tail wraps; it stays empty until the next enqueue lands there (which step 6's resize preempts).

Java (ArrayDeque as Queue)

import java.util.ArrayDeque;
import java.util.Queue;

Queue<Integer> q = new ArrayDeque<>();
q.offer(10);
q.offer(20);
int front = q.poll();   // 10, removes it
int peek = q.peek();    // 20, does not remove
boolean empty = q.isEmpty();

Python (collections.deque)

from collections import deque
q = deque()
q.append(10)
q.append(20)
front = q.popleft()   # 10
peek = q[0]           # 20
empty = len(q) == 0

Pitfalls

• Using java.util.LinkedList as a queue works but has worse cache locality and more allocation than ArrayDeque; prefer ArrayDeque unless you specifically need a List too.
• In JavaScript, array.shift() and in Python plain-list list.pop(0) are O(n) — silently turning an intended O(1) queue op into O(n) and an algorithm's overall complexity from O(n) to O(n²) — a BFS over V vertices degrades to Θ(V²) from queue shifts alone, since each of the V pops can move O(V) elements.
• In Go, popping the front of a slice via s = s[1:] leaks the underlying backing array (memory never freed) unless you periodically reslice/copy; for hot paths use container/list or a manual ring buffer.
• Confusing Python's queue.Queue (thread-safe, blocking, for concurrency) with collections.deque (plain FIFO) — using the former in single-threaded code pays needless locking overhead.
• Forgetting that a fixed-capacity circular buffer must distinguish "empty" from "full" when head==tail — typically solved either by tracking a separate size counter (allows the buffer to fill completely) or by never letting the buffer fill completely (the convention used in the worked example above: full = size == capacity−1). Pick one and apply it consistently — mixing the two is a classic off-by-one source.

When to use / when not

Use a queue when order-of-arrival processing matters and you never need to touch the middle: BFS traversal frontiers, task scheduling, sliding-window algorithms, producer-consumer buffers. Trade-off vs a Deque (double-ended queue): a deque is a strict superset — it supports push/pop at both ends in O(1), so most languages' "queue" is literally a deque used one-ended; reach for the plain queue interface only when you want to statically forbid front-insertion/back-removal for code clarity. Trade-off vs a Stack (LIFO): pick a stack instead when the most-recently-added item should be processed first (DFS, backtracking, expression evaluation) — same O(1) operations, opposite ordering guarantee, and swapping one for the other is a common bug source when translating BFS↔DFS code.

Takeaways

• A queue is an interface contract (FIFO, insert-tail/remove-head); circular buffer and linked list are the two mechanisms that deliver O(1) enqueue/dequeue.
• Array-with-shift is the brute-force trap: O(n) per dequeue, O(n²) overall — avoid shift()/pop(0) in hot loops.
• A circular buffer's wrapped write always lands at the pre-increment tail index, not the post-increment one — trace buf[tail] then tail=(tail+1)%capacity in that order, and pick one full-vs-empty convention (size counter, or reserve one slot) and state it, since head==tail is ambiguous otherwise.
• Prefer language-specific real queue types: Java ArrayDeque, Python collections.deque, C++ std::queue/std::deque — not raw arrays, and not Python's thread-safe queue.Queue for single-threaded code.

Recall

Why does removing from the front of a plain dynamic array cost O(n), and what single change (structure or index scheme) brings it down to O(1)?

Compiled from standard queue ADT theory (CLRS, Ch. 10) and language documentation (java.util.ArrayDeque, Python collections.deque, C++ std::queue) — not from the source page's language-comparison table alone.