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)
• peek: Constant — O(1)
• isEmpty: Constant — O(1)

Code

// 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;
}