Queue and deque

Why it costs this much

A deque supports adding and removing at both ends without moving the other items.

Code

from collections import deque
q = deque()
q.append(x)     # enqueue: O(1)
q.popleft()     # dequeue: O(1)
# lst.pop(0)    # O(n): shifts everything left

Python is the baseline example used across the site.

Common pitfalls

list.pop(0) shifts every element, so it costs O(n) per dequeue. Indexing into the middle of a Python deque is also O(n).

Operation by operation

Queue enqueue and dequeue. Backed by a deque, circular buffer, or linked list. Python list.pop(0) and JavaScript Array.shift can be O(n). Use collections.deque in Python.