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

Queue


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, 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?