JavaScript Data Structures Stack

Learn about the stack data structure. We will also code a stack from scratch using JavaScript.

Table of Contents 📖

• What is a Stack?
• Stack Constructor
• Adding to the Stack
• Removing From the Stack
• Observing the Element on the Top of the Stack
• Running the Code

What is a Stack?

A stack is a data structure that follows the Last In First Out (LIFO) principle. This means that elements are added and removed from the top of the stack only. In other words, elements can't be added or removed from anywhere except for the top of the stack. For example, in the image below, every time a new element is pushed onto the stack it is pushed on top and every time an element is popped from the stack it is removed from the top.

This means that if we wanted to remove the bottom element from a stack, every element on top of it would have to be removed first. A real life example of a stack can be a stack of plates. Plates are added and removed from the top of the stack. A computer science related example is the call stack of a program. The JavaScript interpreter uses a stack to keep track of the program it is executing in the web browser. Specifically, when a script calls a function, that function is added to the top of the call stack. Functions that are called from within that function are then added to the top of the stack and so on. When the function is finished, it is removed from the top of the stack.

function firstFunction() {
  console.log('Pushing first');
  secondFunction();
  console.log('Popping first');
}

function secondFunction() {
  console.log('Pushing second');
  thirdFunction();
  console.log('Popping second');
}

function thirdFunction() {
  console.log('Pushing third');
  console.log('Popping third');
}

firstFunction();

The code above would give the following output.

Pushing first
Pushing second
Pushing third
Popping third
Popping second
Popping first

Stack Constructor

Now lets start coding our Stack with JavaScript. To start, lets create our Stack constructor. This will consist of 3 properties: top, bottom, and size.

class Stack {
  constructor() {
    this.top = null;
    this.bottom = null;
    this.size = 0;
  }
}

• top - The top element in the stack
• bottom - The bottom element in the stack
• size - The number of elements in the stack

Lets also create an object to represent an element inside the stack which we will call StackElement.

class StackElement {
  constructor(value) {
    this.value = value;
    this.below = null;
  }
}

• value - The value of the StackElement
• below - The StackElement that is below the element

Whenever we work with removing or adding to our stack, it will involve a StackElement object.

Adding to the Stack

Now lets write the code to add to a stack. This will be done inside a method called push.

push(val) {
  const newStackElement = new StackElement(val);
  if (!this.top) {
    this.top = newStackElement;
    this.bottom = newStackElement;
  } else {
    const prevTop = this.top;
    this.top = newStackElement;
    this.top.below = prevTop;
  }
  this.size = this.size + 1;
  return this.size;
}

• Create a new StackElement using the supplied value
• If the stack is empty, set top and bottom to the new StackElement
• If the stack is not empty, set the new StackElement to the top StackElement in the stack and set its below property to the current top StackElement. Note that to do this we need a temporary variable to hold the current top element of the stack
• Increase the size of the stack and return the new size

As an element added to a Stack is always added to the top, the time complexity for the insertion of an element is always O(1), or constant time.

Removing From the Stack

Now lets write the code to remove from a stack. This will be done inside a method called pop.

pop() {
  if (!this.top) {
    return null;
  }
  const prevTop = this.top;
  if (this.top === this.bottom) {
    this.bottom = null;
  }
  this.top = this.top.below;
  this.size = this.size - 1;
  return prevTop.value;
}

• If the stack is empty, return null. The stack is empty if the top element is null.
• Create a temporary variable to hold the top element of the stack
• If the top element is equal to the bottom element then the stack is only one element in size. Set bottom to null as there will be no more elements.
• Set the top element to the below element in the stack and decrease the size of the stack by 1. If the stack is only 1 element in size then this.top.below will be null.
• Return the element that was removed, the previous top element, held by the temporary reference.

As an element removed from a Stack is always removed from the top, the time complexity for the removal of an element is always O(1), or constant time.

Observing the Element on the Top of the Stack

Now lets create a method to observe the element that is on the top of the stack without removing it. We will do this with a method called peek.

peek() {
  if (!this.top) {
    return null;
  }
  return this.top.value;
}

• If the stack is empty, return null. The stack is empty if the top element is null.
• If the stack is not empty, return the value of the top element in the stack.

Running the Code

Now lets create an instance of our Stack class and use it.

const stack = new Stack();
stack.push(1);
console.log(stack.peek());
stack.push(2);
console.log(stack.peek());
stack.push(3);
console.log(stack.peek());
stack.push(4);
console.log(stack.peek());

stack.pop();
console.log(stack.peek());
stack.pop();
console.log(stack.peek());
console.log(stack);

We can then run the code to get the following output.

1
2
3
4
3
2
Stack {
  top: StackElement { value: 2, below: StackElement { value: 1, below: null } },
  bottom: StackElement { value: 1, below: null },
  size: 2
}