JavaScript Data Structures: Queue: Intro

Intro

After we finished the small series about the Stack, we start with the Queue.

What is a Queue?

• uses the "First In, First Out"-Principle
• Examples: a queue of people in front of a store, a printer queue
• there are multiple ways to implement a Queue: Array, Singly Linked List, Doubly Linked List

Big O of Queue

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

Example

We will use a Singly Linked List to build our Queue.

A (start) ==> B (end)

• we can enqueue (= add) to the end (e.g. a new person will be the last person in the queue)
• we can dequeue (= remove) from the start (e.g. a person at the start gets served next)
• A is the next node in line
• A has a pointer (next) to the next node (B)
• B is the last node we enqueued (= added) to the Queue
• if we dequeue (= remove) A, the next node in line should be B

Setup

We need the following parts to build our Queue:

• a Node with a value and a pointer to the next item in the Queue
• a Queue with a length, a pointer to the start of the queue, a pointer to the end of the queue

// a Node has a value (`value`) and a pointer to the next node (`next`)
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// a Queue has a length (`length`), a start (`start`), an end (`end`)
class Queue {
  constructor() {
    this.length = 0;
    this.start = null;
    this.end = null;
  }
}

Thoughts

We set up our Queue. Now we need at least two methods within the Queue:

• a method that adds a new node to the end of the Queue: enqueue
• a method that removes a node from the start of the Queue: dequeue

Next Part

We will implement our first method for the Queue.

Don't miss interesting stuff, subscribe!

Questions

• We could also use an Array to build a Queue. How could we do this? Any pros or cons?