Queues and Deques

A print shop has one printer and a line of jobs. The rule is simple and fair: whoever sent their job first gets printed first. A new job joins at the back of the line. The printer always takes the job at the front.

That line is a queue. It is the mirror image of a stack: a stack serves the newest item first, a queue serves the oldest.

#The idea: in at the back, out at the front

A queue has two ends with two different jobs. You enqueue at the back and dequeue from the front. The first item in is the first item out, so a queue is called first in, first out (FIFO). Like a stack, it also lets you peek at the front without removing it.

Queues appear whenever work must be handled in arrival order: requests to a web server, messages between programs, keystrokes waiting to be processed. In algorithms, the big one is breadth-first search, which explores a graph level by level by keeping the places to visit in a queue.

#A queue in action: taking turns

Here is a fair way to share one processor between jobs of different lengths. Each job gets one unit of work, then goes to the back of the line if it still has work left. Short jobs finish early, and no long job can hog the processor. This is called round robin.

Three jobs arrive: A needs 3 units, B needs 1, C needs 2. Step through the turns and watch the front of the queue.

while queue is not empty:  job = dequeue()  run job for 1 unit, time += 1  if job has work left: enqueue(job)  else: record (job, time)

#Making dequeue O(1)

The obvious way to build a queue is an array: push to enqueue and shift to dequeue (append and pop(0) in Python). It gives the right answers, but as you saw in Arrays, removing the first item can shift every other item one slot left. Python's pop(0) always does. JavaScript engines sometimes avoid it for shift, but you cannot count on it, and on large arrays they do shift. Then each dequeue is O(n), and a loop that empties a queue of n items is O(n²).

There are three standard fixes:

• Keep a head index. Do not remove anything. Keep an index head that marks the front and add 1 to dequeue. Simple and fast; the cost is that used slots are never freed.
• Use a linked list with a tail pointer. Dequeue removes the head, enqueue attaches after the tail. Both are O(1), as in Linked Lists.
• Use the library's deque. Python's collections.deque is built for this. JavaScript has no built-in queue, so the head-index trick is the usual choice there.

Here is the round robin from the tracer. The JavaScript version uses a head index; the Python version uses deque.

// jobs: list of [name, units of work]. Each turn gets 1 unit.
function roundRobin(jobs) {
  const queue = jobs.map(([name, left]) => ({ name, left }));
  let head = 0; // index of the front of the queue
  let time = 0;
  const finished = [];
  while (head < queue.length) {
    const job = queue[head];
    head++;                 // dequeue: O(1), nothing shifts
    job.left--;
    time++;
    if (job.left > 0) queue.push(job); // not done: back of the line
    else finished.push([job.name, time]);
  }
  return finished;
}
 
roundRobin([["A", 3], ["B", 1], ["C", 2]]);
// [["B", 2], ["C", 5], ["A", 6]]

from collections import deque
 
# jobs: list of (name, units of work). Each turn gets 1 unit.
def round_robin(jobs):
    queue = deque([name, left] for name, left in jobs)
    time = 0
    finished = []
    while queue:
        job = queue.popleft()  # dequeue: O(1)
        job[1] -= 1
        time += 1
        if job[1] > 0:
            queue.append(job)  # not done: back of the line
        else:
            finished.append((job[0], time))
    return finished
 
round_robin([("A", 3), ("B", 1), ("C", 2)])
# [('B', 2), ('C', 5), ('A', 6)]

#Deques: both ends open

Sometimes you need more than one door. A deque (say "deck", short for double-ended queue) lets you add and remove at both ends, all in O(1). A stack and a queue are each a deque with some doors locked.

The head-index array covers every operation except push front, and most algorithms never need that one. For a full deque in JavaScript, use a ring buffer (a fixed array whose front and back indexes wrap around) or a doubly linked list.

Picture a list of visited pages capped at 50. A new page is pushed at the back. The back button pops from the back, like a stack. When the list grows past 50, the oldest page is popped from the front, like a queue. Python has this cap built in: deque(maxlen=50) drops from the front automatically.

#Common mistakes

#Check yourself

#What to practise next

Try Two-Spike Order Rail, which builds a queue out of two stacks. Queues drive Breadth-First Search, so you will use the head-index trick again there. Before that, Monotonic Stack shows how a stack, and then a deque, can keep its items in sorted order to answer "next bigger" and "biggest in this window" questions in O(n).