Stacks & Queues

Stacks and Queues are just about the first data structures people learn about in a traditional Computer Science undergrad environment. Not that I would know this first hand or anything, being a History major and all. But look! CLRS starts off its Data Structures section with Stacks and Queues, so now you know that what I’m saying here has some merit.

Anyways, we’re using JavaScript here, which is a strange language to be studying DS&A in to begin with, and so it might not be apparent as to why Web Developers even need to cover Stacks and Queues at all – we all know that abusing Arrays is the way to go!

You should hear me out anyways, because a more formalized look into Stacks and Queues is worthwhile. Here classes written for each data structure:

Stack Class


const Stack = function() {
  let items = []
  this.push = element => {
    items.push(element)
  }
  this.pop = () => {
    return items.pop()
  }
  this.peek = () => {
    return items[items.length -1]
  }
  this.size = () => {
    return items.length
  }
  this.isEmpty = () => {
    return items.length === 0
  }
  this.toString = () => {
    return items.toString()
  }
  this.clear = () => {
    items = []
  }
}

Queue Class


const Queue = function() {
  let items = []
  this.enqueue = element => {
    items.push(element)
  }
  this.dequeue = () => {
    return items.shift()
  }
  this.front = () => {
    return items[0]
  }
  this.size = () => {
    return items.length
  }
  this.isEmpty = () => {
    return items.length === 0
  }
  this.toString = () => {
    return items.toString()
  }
  this.clear = () => {
    items = []
  }
}

See, I told you that JavaScript developers abuse Arrays in order to implement Stacks and Queues. What the two classes above essentially do is create an interface around a private items variable.

Stacks and Queues are pretty similar. The differences lie in how they prioritize their input/output methods (push/pop vs enqueue/dequeue). Stacks follow the LIFO principle, which stands for Last In First Out. Queues follow the FIFO principle, which stands for First In First Out.

These principles are meant to be self-explanatory. A Stacks pop() method will return the most recent/last element placed into the Stack (hence LIFO) and a Queue will return the first element placed into the Queue (hence FIFO).

Stacks and Queues are found in everyday life. For example, a Stack is identical to a Pringles can — in order to get out the last chip in the can, all others must come out first. Queues meanwhile represent what the British call, well, queues, and what Americans like me call lines. If you’re the first one in line at a restaurant, then you should be the first one out of it to place your order.

The truth is though, you can probably get through an entire Web Development career ever implementing either of these classes. Indeed, unless you really need to enforce FIFO or LIFO and you can’t risk allowing an Arrays ability to randomly access values at any index, then you will be just fine popping and pushing and shifting on top of the JavaScripts native Array data structure.

But now, when someone talks about “the stack” vs “the heap” or refers to “popping up the stack”, you know that they’re talking about a LIFO set of operations. When you think about Breadth First Search vs Depth First Search algorithms you can realize that the “Breadth First” part of BFS is made possible by means of a Queue. Likewise, the “Depth First” part of DFS is accomplished through recursively building up calls on “the stack”, or you iteratively implement a Stack (or at least an Array that adheres to LIFO). All of these things start to add up to make a more well-rounded developer. And this is only Stacks and Queues, the tip of the iceberg so to speak.