A Simple Queue With Arrays

A Queue is a particular kind of abstract data type (ADT) or collection where entities are kept in order. You can only add new entities to the end of the list (enqueue) and only remove entities from the start of the list (dequeue). This is what makes a Queue a FIFO data structure (see further down).

When are queues useful?

Queues are mainly used to provide the service of storing and holding entities which are to be processed later.

Similarities with Stacks

Stacks and Queues have a lot of things in common. Thet are both linear data structures (elements are in sequence or a linear list) that both have flexible sizes, meaning that you don't have to allocate fixed size when initiating them.

LIFO

The main difference between a Queue and a Stack comes when you remove items. A Stack is a LIFO data structure, meaning "Last In First Out", it's much like an actual stack of plates. Imagine that you're stacking a bunch of plates on a table to build a tower. The last plate you put on that stack will be the first one you remove.

FIFO

The Queue however is a FIFO data structure, meaning "First In First Out". For this example, imagine that you're at the movie theatre, waiting in line to get in. When they open the doors, they don't let in the person who just arrived, instead, they let in the very first person who arrived.

Simple Queue implementation

The simplest ways to implement a Queue in JavaScript is to use the features of the built in Array.

First, let's take a look at which methods a Queue would contain:

class SimpleQueue {
  constructor() {
    this.list = []
  }
  add() {}
  dequeue() {}
  peek() {}
  size() {}
  show() {}
}

Of course, we could also add methods such as contains(), isEmpty(), clear() etc, but let's stick to a basic implementation for now and build a more robust Queue later on.

SimpleQueue.add()

Now let's make us able to add some things to the Queue. Since we're building our Queue with the JavaScript Array, let's take full advantage of the methods already there with Array.push():

class SimpleQueue {
  constructor() {
    this.list = []
  }
  add(element) {
    return this.list.push(elem)
  }
}

const queue = new SimpleQueue()
queue.add(1) // [1]

SimpleQueue.dequeue()

Removing things from the Queue is really simple too. Since a Queue is a FIFO data structure we will only remove the first element in the queue every time, so we can use the built in Array.shift() method.

class SimpleQueue {
  constructor() {
    this.list = []
  }
  add(element) { ... }
  dequeue() {
    return this.queue.shift()
  }

}

const queue = new SimpleQueue()
queue.add(22) // [22]
queue.add(14) // [22, 14]
queue.dequeue() // [14]

SimpleQueue.peek()

Peek is the method that we will use when we want to pull out the first element in the Queue to perform an action on it. If it succeeds we can dequeue it, if our action fails the element is still in the Queue. So it should just return the first item, nothing more.

class SimpleQueue {
  constructor() {
    this.list = []
  }
  add(element) { ... }
  dequeue() { ... }
  peek() {
   return this.queue[0]
  }
}

const queue = new SimpleQueue()
queue.add(22) // [22]
queue.add(14) // [22, 14]
queue.peek() // 22

SimpleQueue.size()

Since we're not exposing the actual list array itself, it might be a good idea to expose the length of the Queue.

class SimpleQueue {
  constructor() {
    this.list = []
  }
  add(element) { ... }
  dequeue() { ... }
  peek() { ... }
  size() {
    return this.queue.length
  }
}

const queue = new SimpleQueue()
queue.add(22) // [22]
queue.add(14) // [22, 14]
queue.size() // 2

SimpleQueue.show()

Now, let's imagine that you want to loop over every item in the Queue, or that you want to perform some other operation, it can be a good idea to be able to return the actual Array.

class SimpleQueue {
  constructor() {
    this.list = []
  }
  add(element) { ... }
  dequeue() { ... }
  peek() { ... }
  size() { ... }
  show() {
    return this.list
  }
}

const queue = new SimpleQueue()
queue.add(22) // [22]
queue.add(14) // [22, 14]
queue.show() // [22, 14]

SimpleQueue is complete!

class SimpleQueue {
  constructor() {
    this.list = []
  }
  add(element) {
    this.list.push(element)
  }
  dequeue() {
    return this.list.shift()
  }
  peek() {
    return this.list[0]
  }
  size() {
    return this.list.length
  }
  show() {
    return this.list
  }
}

const queue = new SimpleQueue()

// So how would we use the queue? A simple example would be to
// fetch some users, store them in the queue and then go through the queue
// and save their names into an array.
function getUsers(url) {
  return new Promise(resolve => {
    fetch(url)
      .then(res => res.json())
      .then(data => {
        // add users to queue
        data.users.map(user => queue.add(user))
        resolve()
      })
  }) 
}

// for each user we want to store their names in an array
function storeUserNames() {
  let store = []
  while (queue.size() > 0) {
     // grab first user in queue
     const user = queue.peek()
     // store user
     store.push(user.name)
     // dequeue item
     queue.dequeue()
  }
  return store
}
getUsers(url).then(() => {
   const userNames = storeUserNames()
   console.log(userNames) // ['Lars', 'Anna', 'Jennifer', 'Max']
})

Now that we have a complete Queue, we're all set, right?

Well, we could use some of the knowledge we gained from building a Linked List to replace the JavaScript Array with a Linked List instead, combined with some general improvements, to create a Queue that could be implemented in any language with the same principles. So let's do that!