Implement a Queue in JavaScript

Data Structures
September 21, 2016

This is the second of a series of articles on implementing data structures in JavaScript. If you’re new to data structures, be sure to read this introduction (link to come) to data structures first. Already know about queues? Let’s get started on some more advanced data structures like the binary search tree!

A queue is like a line at a restaurant. It’s “first in, first out” (FIFO), which means that the item that was put in the queue longest ago is the first item that comes out. “First come, first served.”

Most use-cases for a queue are involved with building or utilizing other data structures. One example could be in breadth-first traversal of a tree.

Queues have two main methods:

  1. enqueue() : Adds a node (value)
  2. dequeue() : Removes and returns the next node in the queue

They can also include other utility methods:

  1. peek() : Returns the node at the front of the queue (without removing)
  2. isEmpty() : Returns True if the queue is empty, otherwise returns false

Pseudo Code

Create Queue constructor Define storage, count, and lowest count Create enqueue method (value) Add value to queue Increment count Create dequeue method Save node to delete in var Delete node Increment lowest count Return saved node Create size method Return count minus lowest count

Time complexity

If you don’t know much about time complexity, you’ll be lost until you read this short article on time complexity in JavaScript. For each method on the queue, the worst-case time complexity is constant — O(1). This means that as the stack grows to n size, each method completes its job in the same amount of time.

  • enqueue: Constant — O(1)
  • dequeue: Constant — O(1)

Code

  • peek: Constant — O(1)
  • isEmpty: Constant — O(1)
// This Stack is written using the pseudoclassical pattern // Creates the queue var Queue = function() { this.storage = {}; this.count = 0; this.lowestCount = 0; } // Adds a value to the end of the chain Queue.prototype.enqueue = function(value) { // Check to see if value is defined if (value) { this.storage[this.count] = value; this.count++; } } // Removes a value from the beginning of the chain Queue.prototype.dequeue = function() { // Check to see if queue is empty if (this.count - this.lowestCount === 0) { return undefined; } var result = this.storage[this.lowestCount]; delete this.storage[this.lowestCount]; this.lowestCount++; return result; } // Returns the length of the queue Queue.prototype.size = function() { return this.count - this.lowestCount; }

Are you ready to take on some more advanced data structures? Next up is the binary search tree!

Having worked across sites raking in over 50 billion website visits annually, Michael Mitrakos can help your business to crush the web game with an award winning website.

I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!

More Blog Posts