Stack and Queue in JavaScript

Stacks and Queues are linear data structures, meaning they have data elements in sequential order. Both Stacks and Queues have a worst-case of O(1) for insert and delete. How the data is added and retrieved is very important for both a Stack and a Queue. It's not necessary, but I'd recommend reading our article regarding algorithm analysis if you are not familiar with Big O notation.

1. What is a Stack?

A stack is a list that follows LIFO (Last in First Out) and FILO (First in Last Out), which simply means that the latest item added is also the first to get out of the stack.

A classic example is a pile of newly washed plates. The first plate you put down will be used last, while the last you put down is the first you’ll use.

With Stacks, we therefore only insert and delete at one end of the list, which we refer to as the top. An insert is known as a push while delete is known as a pop.

Stack operations

The common methods for a stack are:

• Push: add/insert an element to the top of the stack.
• Pop: remove an element from the top of the stack.
• Peek: return the element of the top without removing it.
• Clear: removes all elements so you get a clear stack.
• Size: the number of elements in the stack.
• isEmpty: return true or false regarding if the stack is empty.
• isFull: return true or false regarding if the stack is full.

Implement a Stack in Javascript

It is worth noting that an array in Javascript already has a push and pop method. The push and pop method provided by the array object is often sufficient if you just want to have the core functionality of a Stack. An array does not have its peek method, but you could simply just arrayStack[arrayStack.length-1].

You can implement a Stack in Javascript in different ways, but since push and pop already has an O(1) runtime, I just re-used them for clean and readable code like:

function Stack() {
    this.elements = [];
}

/**
 * Add the element on top
 */
Stack.prototype.push = function(element) {
    this.elements.push(element)
}

/**
 * Remove the top element
 */
Stack.prototype.pop = function() {
    return this.elements.pop()
}
/**
 * Return the top element without removing it
 */
Stack.prototype.peek = function() {
    return this.element[this.length - 1];
}

/**
 * Return the size
 */
Stack.prototype.getSize = function() {
    return this.elements.length;
}

As already mentioned, you could also just do the following:

let stack = []

stack.push(2) // [2]
stack.push(5) // [2, 5]
stack.pop()   // [2]

2. What is a Queue?

A queue is a list that follows FIFO (First in First Out) and LILO (Last in Last Out), which means that the first item added will also be the first to get out.

Imagine that three people named, Carl, Kajsa, and Erik are all lined up waiting, for a bus. Carl was at the bus stop first, so he gets to enter the bus first. Kajsa is second in line, which means she will enter the bus after Carl. Erik arrived last and will, therefore, enter the bus last.

With Queues, we insert at the end of the list, which we refer to as the rear. We delete an element at the start of the list, which we refer to as the front. An insert is known as an enqueue while delete is known as a dequeue.

Queue operations

The common methods for a queue are:

• Enqueue: add/insert an element at the rear (end of queue).
• Dequeue: delete an element at the front of the queue.
• Peek: return the element from the front without removing it.
• Clear: removes all elements so you get a clear queue.
• Size: the number of elements in the queue.
• isEmpty: return true or false regarding if the queue is empty.
• isFull: return true or false regarding if the queue is full.

Implement a Queue in Javascript

An Array in Javascript already has a push and shift method, which achieves what we want to achieve with an enqueue and dequeue, so creating your own Queue might seem to be unnecessary.

Sadly shift takes O(n) running time, and we want our dequeue to be O(1), so it might be a good idea to implement your own queue if you'll have a big input.

You may have seen implementations that look like this online:

function Queue() {
   this.elements = [];
}

/**
* Add/insert an element at the rear (end of queue).
*/
Queue.prototype.enqueue = function(element) {
   this.elements.push(element)
}


/**
*  Delete an element at the front of the queue in O(n) running time
*/
Queue.prototype.dequeue = function() {
   return this.elements.shift()
}

Which is decent, but as we now know, shift has an O(n) runtime. Why? Well after removing the element at index 0 it moves all the elements one step back, re-indexing all the elements in the entire array.

One of the solutions we can use to achieve an O(1) runtime is to keep track of the rear and front index:

function Queue() {
   this.elements = {};
   this.rear = 0; // or head or end
   this.front = 0; // or tail or beginning
}

/**
* Add/insert an element at the rear (end of queue).
*/
Queue.prototype.enqueue = function(element) {
   this.elements[this.rear++] = element;
}


/**
* Delete an element at the front of the queue in O(1) running time
*/
Queue.prototype.dequeue = function() {
   if (this.rear === this.front)
       return undefined

   var element = this.elements[this.front];
   delete this.elements[this.front++];
   return element;
}

Thanks for reading. All the code can be found here.