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

# Implement a Queue

## Course launching November 17, 2020

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
Stacks
Next
Implement a Stack