#12 JS Data Structures: Stacks

7 min readMar 29, 2019

This article belongs to the JS Data Structures series, which contains these articles:

Arrays
Stacks
Queues
Linked List (soon)
Sets (soon)
Dictionaries/maps (soon)
Hashes tables (soon)
Trees: Binary Search Tree (BST) (soon)
Trees: AVL Tree (soon)
Trees: Red-black Tree (soon)
Trees: Binary Heap / Heapsort (soon)
Graphs (soon)

Stacks are a collection of elements where is possible to add items only in the top, we have several practical examples of stacks like the browser history, undo operations, recursion and many others.

The order to get elements from a Stack is known as LIFO (Last in, first out), the main idea is this:

This article will cover the following content:

Basic structure
Stack methods
Stacks algorithms examples
- Decimal to binary
- Reverse a string using a stack
- Next Greater Element
Time and space complexity

Basic structure

Let’s create a closure function that will allow us to output only the public Stacks methods and prevents changes in internal attributes like the item list:

function Stack(){    let items = []    class PublicStack(){
      ...the stack methods will be here    }    return new PublicStack()}

With this approach, the only public methods will be the methods included in PublicStack class, if you want to know more about closures this article is really useful:

What is a Closure?

“Master the JavaScript Interview” is a series of posts designed to prepare candidates for common questions they are…

medium.com

If you decide to implement this Stack without using the Javascript native functions — for educational/training purposes — like push, pop and length, your basic structure will be:

function Stack(){ 
  let top = null
  let size = 0  class Node {
    ...the node methods
  }  class PublicStack {
      ...the stack methods will be here  }  return new PublicStack()
};

Without the native JS methods, you’ll need to create a Node to store your data sequentially, this node will contain the data itself and an attribute called previous that will refer to the node added before the current node.

class Node {
  constructor(data){      
    this.data = data
    this.previous = null
  }
}

Stack methods

After we created the basic structure we are ready to implement the required stack methods:

size
isEmpty
push
pop
peek
clear

Size

This method returns how many items there are inside a stack, using JS methods you could use the length to return this value:

size(){
  return items.length
}

Without the JS native methods, you’ll need simply return the size variable:

size(){
  return size
}

isEmpty

This method returns if the stack contains or not contains items inside, to implement this with JS native function you’ll use the size stack attribute is equal to zero:

isEmpty(){
  return this.size() === 0
}

The implementation is the same when you aren’t using JS native methods.

Push

This method allows us to add a new item in the top of a stack, using the native JS methods this implementation is very simple

push(data){
  items.push(data)
}

Without the JS natives methods you need:

1. Create a new node
2. Put the current node stored in the top variable as the next node of the new node
3. Increment the size variable

push(data){
   const node = new Node(data)
   node.previous = top
   top = node   size++
}

Pop

This method allows us to remove the element in the top of a stack, using the JS native methods the implementation is:

pop(){
  if(this.isEmpty()) throw new Error('This stack is empty')  const lastItemIndex = items.length - 1
  const currentLastItem = items[lastItemIndex]  items.pop()  return currentLastItem}

Without the JS native methods, you’ll need:

1. Store the top node in a temporary variable
2. Put the previous node as the new top node
3. Decrement the size variable
4. return the old top node;

pop() {
  if(this.isEmpty()) throw new Error('This stack is empty')  const tempTop = Object.assign({}, top)
  const nextElement = tempTop.previous
  top = nextElement
  size--  return tempTop.data}

Peek

This method returns the element in the top of the stack, using JS native methods the implementation is:

peek(){
  if(this.isEmpty()) throw new Error('This stack is empty')  const lastItemIndex = items.length - 1
  return items[lastItemIndex]}

Without JS native methods you simply return the top.data:

peek(){
  if(this.isEmpty()) throw new Error('This stack is empty')  return top.data
}

Clear

This method allows us to delete all data inside a stack, to do that using the JS native functions you need to redefine the items array to [].

clear(){
  items = []
}

Without JS native methods you’ll need to redefine the top var as null and the size to 0.

clear(){
  top = null
  size = 0
}

Putting all together

If you decide to use the JS native method this will be your final stack implementation:

Using the nodes approach without JS native functions this will be the result:

If you want to check out other Javascript Data Structures examples take a look in this GitHub repository:

rxluz/js-data-structures

A list of different JS data structures. Contribute to rxluz/js-data-structures development by creating an account on…

github.com

Stacks algorithms applications

Decimal to binary

A binary number is represented by 0 and 1, when we want to transform a number to binary data we need to divide this number by 2 until the result will be zero, to each division we store the remainder in a stack

From https://www.geeksforgeeks.org/program-decimal-binary-conversion/

In the end, we get all the remainders stored in our stack and create a string with these values, this could be reached using this algorithm:

Reverse a string using a stack

The approach to solving this problem is:

Add all letters from a string in a stack
Extract the letters from the top of a stack and add them in a new string

Note: This algorithm is only to study purposes, the same result could be archived with some lines of code using a simple array:

const reverseString = currentString => 
  currentString
   .split('')
   .reverse()
   .join('');

Next Greater Element

The idea is to return the next element greater after this element in a list than the given element to check, for example:

const numbers = [10, 2, 3, 4, 5, 50, 100]nextGreaterElement(numbers, 10); //will return 50
nextGreaterElement(numbers, 5); //will return 50
nextGreaterElement(numbers, 3); // will return 4

The approach to solving this problem is:

Add all items that are in the right of the checked element in a stack
Remove elements from this stack until found the closer element greater than the checked element

Time and space complexity

Time complexity defines how faster is your algorithm, and space complexity defines how much memory your algorithm needs to run, this is also called Big-O notation.

Let’s analyse the methods inside our stack to find out this:

size: We have O(1) to time and O(1) to space, once the time and memory that we need to run this operation remains the same regardless of the number of items inside our queue.
isEmpty: Same thing here, O(1) to time and O(1) to space.
push: When we push an item we do it at the top of the queue, it means that we don’t need to change the position of the other items, thus this operation run exactly at the same time regardless of the stack size, also we don’t need any recursive function here or store something that increases according to the size of stack, it means that the memory that we need is always the same, so is O(1) to time and O(1) to space.
pop: Pop time complexity will be the same using JS native methods or creating your own implementation using nodes, once you don’t need to move the position of other elements the complexity and space will be always the same regardless of the size, thus O(1) to time and O(1) to space.
peek: To peek an item you always will need the same time and space once you don’t need to analyse the full queue, so space/time complexity will be O(1).
clear: You need to go through all items and join all them in a string to print, so space and time complexity will be O(1) once you need more memory and time according to the stack size.

If you want to know more about Big O Notation and how to calculate this I wrote this article that will help you:

#9 Big O in JS: The basic that you need to know

There are many ways to analyse how good is a code that you have written, some people believe that a beautiful code is…