Queues and lunch lines

This post is the sixth of a series adapted from my conference talk, Fun, Friendly Computer Science.

My office has lunch catered every Thursday after our company stand up. During stand up, we’re all in a circle and each gives a quick status update. But on Thursday our circle is a little lop-sided as people bunch up on the side nearest the food so they can be the first to get in line. Human behavior doesn’t change much as we grow up. We did the same thing in elementary school, trying to be among the first to be in the lunch line.

Waiting in a line—or as the British call it, “queueing”—is a literal visualization of a queue data structure. The first person in line is the first person who gets whatever they’re waiting for and leaves the line. And new folks joining the line (should) always join at the back of the line.

A queue data structure behaves the same way. Queues are characterized by first-in, first-out (FIFO) data access. When implemented as a linked list, adding and removing from the queue are O(1) (see this post if you are unfamiliar with big O notation).

Let’s look at some code samples to make it easier (extended code samples can be found on my Github in Javascript, Ruby, and Python).

Adding to a queue

Just like how we use different words for adding to and removing from a stack, computer scientists have chosen different words for adding to and removing from a queue. When adding to a queue, you “enqueue” a new item into the queue.

Enqueueing is the same as adding to a vanilla linked list as we outlined in our previous post on linked lists.
When adding the first node, when nothing exists in the list yet, we add the node as both the head and the tail of the list.

If nodes already exist in the list, we only worry about the tail node. When adding additional nodes, we set the next pointer of the current tail node to the new tail node. And then we update the list’s tail pointer to be the new tail node. This sets up the first part of first-in, first-out data access that defines a queue.

enqueue(data) {
  const newNode = new LinkedListNode(data);
  if (this._head === null) {
    this._head = newNode;
  } else {
    this._tail.next = newNode;
  }
  this._tail = newNode;
  return newNode;
}

Removing from a queue

Removing from a queue, or “dequeuing,” always returns the current head and replaces the head with the next node in the list. This sets up the final part of first-in, first-out data access. This is also the same behavior as popping from a stack.

dequeue() {
  const dequeued = this._head;
  this._head = this._head.next;
  return dequeued;
}

Queue uses

Whenever you want to enforce first-in, first-out data access you’ll use a queue. A common software engineering problem that is solved with queues is when a user takes an action to initiate a long-running task like generating a PDF, running complex data analysis, or other CPU heavy operations and we don’t want to block the user’s interface while that executes.

For example, if you’re developing a web application that generates a PDF when a user clicks a button, you don’t want the user to see a loading screen for the 3 minutes it takes for the PDF to generate. Instead of blocking the browser with a long-running request, you could add the request to a queue when the user clicks the button. Then, use a background job of some kind to process requests from the queue. This ensures that user requests are processed in the correct order (first-come, first-served) but that they can continue to interact with your web application while your server generates their document.