Stacks and PEZ dispensers

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

Whenever I give my “Fun, Friendly Computer Science” talk at a conference, I always have a moment of worry that the audience isn’t going to know what a PEZ dispenser is. I haven’t seen one since I was a kid, but they are such a perfect visualization for a stack that I have to use it for my example.

A PEZ dispenser is a plastic column with a cartoon character (or some other character’s head) on top that tips back to manually dispense PEZ candies (little rectangle-shaped sugar candy). The column holds 12 PEZ candies. When you fill the dispenser, you tilt the head back and push the candy from the top down. When you eat the candy, you tilt the head back and pop a piece off the top of the literal stack of pieces one at a time.

Image courtesy of WikiHow

A stack data structure behaves the same way. Stacks are characterized by last-in, first-out (LIFO) data access. When implemented as a linked list (which they usually are), adding and removing from the stack 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 stack

Because computer scientists love to make everything sound more complicated than it is, they use different words for adding and removing from a stack than a list. When talking about a stack, you “push” when you are adding a node onto the stack.

Using a linked list as the underlying implementation of a stack, you set the new node’s next pointer to the current head node. And then replace the head of the list with the new node. This sets up the first part of last-in, first-out data access that defines a stack.

push(data) {
  const newNode = new LinkedListNode(data);
  if (this._head) {
    newNode.next = this._head;
  }
  this._head = newNode;
  return newNode;
}

Removing from a stack

Instead of “removing” from a stack, we say that we “pop” from the stack. Popping from the stack always returns the current head and replaces the head with the next node in the list. This sets up the final part of last-in, first-out data access.

Think about your PEZ dispenser, the last piece of candy that was inserted when it was filled is the first one you eat when you tilt the head back to dispense your candy.

pop() {
  const popped = this._head;
  this._head = this._head.next;
  return popped;
}

Stack uses

Whenever you want to enforce last-in, first-out data access you’ll use a stack. In everyday life, you encounter stacks when you use the browser’s back button or when you use undo and redo features in editing software. Whenever you take an action, they store a reference to it on a stack. Undo pops that action off the stack and redo places it back on the stack.

Whenever you’re asked to solve a problem checking for balanced delimiters in a string, whether its parentheses, quotes, or sometimes HTML tags, the answer they are looking for is “I’d use a stack.” This is a common interview question. Depending on how confidently you deliver your answer, sometimes you can get out of having to code the solution 😉 But don’t count on that.

Checking for balanced strings uses a stack by pushing each opening delimiter onto the stack and then popping it off when you reach a closing delimiter and checking if they match. If you get through the string with matching pairs and finish with an empty stack, then your string is balanced.