Stack and Queue in JavaScript

2019-02-19 19:05 +09:00

Stacks and queues are frequently used data structures, and many languages provide them as standard library. JavaScript, well known for its minimal stdlib (actually none), doesn’t have native stack or queue. In this post, I’d like to look into possible implementations of stack and queue in JS and check which one is the best.

I don’t explain about the data structures and implementations themselves in this post. There are plenty of resources online, so please google them if you’re interested. Also, implementations in this post are quite basic and not really to be used in production.

Stack

Stack has methods such as push(), pop(), peek(), etc, but I’d like to focus on the very basic methods, push() and pop().

ArrayStack

As many already know, JavaScript Array has native push() and pop() methods and we can just use it.

class ArrayStack {
  constructor() {
    this.arr = [];
  }

  push(val) {
    this.arr.push(val);
  }

  pop() {
    return this.arr.pop();
  }
}

LinkedListStack

We can also implement stack with a linked list. As JS has no native linked list (again), let’s implement it first.

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

A stack can be implemented by pushing to or popping from a head of a list.

class LinkedListStack {
  constructor() {
    this.list = null;
  }

  push(val) {
    const node = new ListNode(val);
    node.next = this.list;
    this.list = node;
  }

  pop() {
    if (!this.list) throw new Error('Empty stack');

    const val = this.list.val;
    this.list = this.list.next;
    return val;
  }
}

Queue

In the same manner as stack, I only focus on enqueue() and dequeue().

ArrayQueue

JS Array actually can be a queue with native methods push() and shift() (or it can be unshift() and pop() for the other way around).

For static arrays, shifting an array usually costs O(n). However, it can be done in O(1) with dynamic arrays by just shifting the head pointer. I’ve heard that many JS engines optimize shift() and it’s actually O(1).

class ArrayQueue {
  constructor() {
    this.arr = [];
  }

  enqueue(val) {
    this.arr.push(val);
  }

  dequeue() {
    return this.arr.shift();
  }
}

LinkedListQueue

Surely, we can implement a queue with a list too, by keeping front and rear pointers.

class LinkedListQueue {
  constructor() {
    this.front = null;
    this.rear = null;
  }

  enqueue(val) {
    const node = new ListNode(val);
    if (this.rear) {
      this.rear.next = node;
    }
    this.rear = node;
    if (!this.front) {
      this.front = this.rear;
    }
  }

  dequeue() {
    if (!this.front) throw new Error('Empty queue');

    const val = this.front.val;
    this.front = this.front.next;
    if (!this.front) {
      this.rear = null;
    }
    return val;
  }
}

CircularQueue

Lastly, a circular queue with predefined array size can be implemented with an array.

class CircularQueue {
  constructor(arrSize) {
    this.arrSize = arrSize;
    this.arr = new Array(this.arrSize);
    this.front = 0;
    this.rear = 0;
  }

  enqueue(val) {
    this.arr[this.rear] = val;
    this.rear = (this.rear + 1) % this.arrSize;
  }

  dequeue() {
    if (this.front === this.rear) throw new Error('Empty queue');

    const val = this.arr[this.front];
    this.front = (this.front + 1) % this.arrSize;
    return val;
  }
}

Performance

I’ve tested the implementations with the following test code:

const ITER_COUNT = 10000;

t0 = performance.now();
for (let i = 0; i < ITER_COUNT; i++) {
  for (let j = i; j >= 0; j--) {
    stack.push(i); // for queue, queue.enqueue
  }
  for (let j = i; j >= 0; j--) {
    stack.pop(); // for queue, queue.dequeue
  }
}
t1 = performance.now();

My machine is MPR 2018 with 2.2GHz Core i7.

Chrome (72)

====== STACK ======
ArrayStack finished in 230.70499999994354ms
LinkedListStack finished in 2547.070000000531ms

====== QUEUE ======
ArrayQueue finished in 3100.115000000187ms
LinkedListQueue finished in 2516.2350000000515ms
CircularQueue with size 10000 finished in 868.1299999998373ms
CircularQueue with size 1000000 finished in 871.0699999992357ms

Firefox (65)

====== STACK ======
ArrayStack finished in 181ms
LinkedListStack finished in 899ms

====== QUEUE ======
ArrayQueue finished in 1144ms
LinkedListQueue finished in 783ms
CircularQueue with size 10000 finished in 813ms
CircularQueue with size 1000000 finished in 823ms

Safari (12)

====== STACK ======
ArrayStack finished in 226ms
LinkedListStack finished in 426ms

====== QUEUE ======
ArrayQueue finished in 2480.0000000000005ms
LinkedListQueue finished in 437.99999999999955ms
CircularQueue with size 10000 finished in 959ms
CircularQueue with size 1000000 finished in 949ms

Conclusion

Stack

Use Array.

Queue

It seems like true that shift() is optimized to work in O(1), though it’s slower than other implementations. Linked list one is generally fast, especially in Safari.

If you’re lazy, use Array. Use linked list if you feel like.

FYI, shift() optimization in v8.

read other posts