Queues and deques

First in, first out

A queue adds items at the back and removes them from the front: first in, first out, or FIFO. The two main operations are enqueue (join at the back) and dequeue (leave from the front). Queues model fair waiting: print jobs, support chats, orders waiting for a kitchen, and the order in which breadth-first search visits a graph (Module 9).

Why list.pop(0) is slow

A Python list keeps its items side by side. Removing the first item means every other item shifts one place left, which is O(n). A loop that dequeues n items this way costs O(n²) in total. JavaScript's arr.shift() moves the remaining items in the same way, so treat it as O(n) too.

collections.deque

deque (said "deck", short for double-ended queue) is built for both ends. append and appendleft, pop and popleft are all O(1). In CPython it is a doubly linked list of fixed-size blocks, so it never shifts items. Reading q[0] or q[-1] is O(1), but indexing in the middle is O(n). deque(maxlen=k) keeps only the newest k items and drops the oldest automatically.

from collections import deque

q = deque()
q.append("token 1")
q.append("token 2")
q.append("token 3")
print(q.popleft())    # Output: token 1
print(q)              # Output: deque(['token 2', 'token 3'])
q.appendleft("urgent")
print(q[0], len(q))   # Output: urgent 3

recent = deque(maxlen=3)
for x in range(1, 6):
    recent.append(x)
print(recent)         # Output: deque([3, 4, 5], maxlen=3)

A circular queue on a fixed array

Some systems cannot grow their memory: a device driver, a game's input buffer, or a logger that keeps the last 1,000 events. A circular queue, also called a ring buffer, uses one array of fixed capacity and two numbers: head, the index of the front item, and count, how many items it holds. The next free slot at the back is (head + count) % capacity. The % makes indexes wrap past the end back to 0, so slots freed at the front are reused. Every operation is O(1), and the space is O(capacity).

Keeping count, and not only head and tail indexes, makes "empty" (count == 0) and "full" (count == capacity) easy to tell apart; with two indexes alone, both cases can look like head == tail.

Where a double-ended queue helps

• Sliding window maximum: a deque of indexes that you trim from both ends (Topic 3).
• Keeping only the latest k items with deque(maxlen=k): recent searches, or recent request times in a rate limiter.
• Checking a palindrome by removing one item from each end and comparing.
• Breadth-first search, where popleft() takes the next node to visit (Module 9).

A note for JavaScript

JavaScript has no built-in queue type. arr.shift() removes the first item but is O(n) in general. Two simple fixes: keep a head index into the array and move it forward instead of shifting (and now and then drop the used part with slice so memory is freed), or build a small linked list with head and tail references (Topic 4). The task below uses the index idea.

Common mistakes

• Using list.pop(0) or arr.shift() in a loop over n items: O(n²). Fix: deque.popleft() in Python, a head index in JavaScript.
• Indexing a deque in the middle inside a loop, which is O(n) each time. Fix: use a list when you need random access.
• Forgetting % capacity in a circular queue, so the index runs off the end. Fix: compute every slot index modulo capacity.
• Mixing up empty and full when head equals tail. Fix: keep a count (or leave one slot always unused).
• Using queue.Queue in algorithm code. It is made for passing work between threads and adds locking. Fix: use collections.deque.