JavaScript Data Structures: Queue: Recap

Intro

Last time, we added the dequeue method.

I hope you learned something about the concept of a Queue and tried your best to implement it on your own.

Thoughts about the Queue 💭

We implemented the Queue using a Singly Linked List.

The Queue data structure is a very important concept, because we use it all the time.

The Queue is based on the "First In, First Out"-Principle, meaning the first node that goes into the queue will later be the first node, that goes out of the queue.

Examples in real life: people who want to pay in a store, the tasks of a printer.

• Access: O(N)
• Search: O(N)
• Insert: O(1)
• Remove: O(1)

Final Implementation 📝

Our Queue has these methods:

• enqueue, to add a node to the end of the queue
• dequeue, to remove a node from the start of the queue

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

class Queue {
  constructor() {
    this.length = 0;
    this.start = null;
    this.end = null;
  }

  enqueue(value) {
    const newNode = new Node(value);

    if (!this.length) {
      this.start = newNode;
      this.end = newNode;
    } else {
      this.end.next = newNode;
      this.end = newNode;
    }

    this.length += 1;
    return newNode;
  }

  dequeue() {
    if (!this.length) {
      return null;
    } else {
      const nodeToRemove = this.start;
      this.start = this.start.next;
      nodeToRemove.next = null;

      if (this.length === 1) {
        this.end = null;
      }

      this.length -= 1;
      return nodeToRemove;
    }
  }
}

Further Reading 📖

• Wikipedia: Queue
• Wikibooks: Queue
• Wikipedia: FIFO

Questions ❔

• Can you implement a new method peek, that returns the start node, without removing it?

Next Part ➡️

We will compare the Data Structures we've built so far.

Don't miss interesting stuff, subscribe!