Implement a Queue Coding Interview Question | Skilled.dev
Interview Question

Implement a Queue

Course launching September 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓

With a queue, we need fast operations at both ends because we will enqueue the last item at the back and dequeue first item from the front. This makes a linked list the perfect data structure to implement a queue because we can achieve operations at the ends in O(1) time.

Unlike stacks, queues cannot be implemented using a dynamic array because adding an item at the front of the array would require O(n) time for re-indexing.

Our linked list will be built using Node objects that store data and points to the prev node in the queue.

We will implement a peek, enqueue, and dequeue methods which operate in O(1) time because our queue maintains a that references the first and last item.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
  }

  peek() {
    // get the first item of the list
  }
  enqueue(item) {
    // add an item to the end of the list
  }
  dequeue() {
    // remove the first item from the list
  }
}

peek()

Peek allows us to view the first item that is at the front of the queue. We just return the value in our first pointer.

peek() {
  return this.first;
}

enqueue(item)

This method adds an item to the back of the queue. The item that was previously at the end sets its prev pointer to reference the new item on the end. We also update the last pointer of the queue object to point at this new node.

enqueue(item) {
  const newLastNode = new Node(item);
  const isEmptyList = !this.first && !this.last;

  if (isEmptyList) {
    this.first = newLastNode;
    this.last = newLastNode;
  } else {
    this.last.prev = newNode;
    this.last = newNode;
  }

  return newLastNode;
}

dequeue()

We remove the first item in the list. The queue's first pointer is now set to the item after the one that was removed.

If we only have one item remaining in the queue (the first and last are equal), we also need to make sure that we set the last pointer to null to empty out the queue. In the case of an empty queue, the first pointer will be set to null automatically because removedItem.prev is null.

dequeue() {
  const removedItem = this.first;

  if (!removedItem) {
    return null;
  }

  if (this.first === this.last) {
    this.last = null;
  }

  this.first = removedItem.prev;

  return removedItem;
}

Complete Queue Implementation

Putting it all together, we have the following class implementation. If you want to see it in action, you can use it in this REPL.

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
  }

  // Get the first item
  peek() {
    return this.first;
  }

  // Add a new last item
  enqueue(item) {
    const newLastNode = new Node(item);
    const isEmptyList = !this.first && !this.last;

    if (isEmptyList) {
      this.first = newLastNode;
      this.last = newLastNode;
    } else {
      this.last.prev = newNode;
      this.last = newNode;
    }

    return newLastNode;
  }

  // Remove the first item
  dequeue() {
    const removedItem = this.first;

    if (!removedItem) {
      return null;
    }

    if (this.first === this.last) {
      this.last = null;
    }

    this.first = removedItem.prev;

    return removedItem;
  }
}
Prev
Queues
Next
Stacks

Table of Contents