Data Structures with Javascript - Stack

Data structures are a way of storing, organising, and accessing data in different ways to suit a specific purpose. In this article, we'll take a look at the stack data structure and how we can implement it with javascript.

How does a stack work?

A stack is a way to store and retrieve data based on a last in first out bases FIFO. When we add items to the stack, they are placed on top, and similarly, when we remove items, they are removed from the top. You can think of it as a pile of plates or books.

Uses of stacks

As stacks work on a FIFO basis they can be used for anything where we need to access the last piece of data that has been added to our data structure. Browser history can be built using stacks as when a user visits a page the last page is placed on top of the stack and when a user clicks the back button we can then access this last page from the top. Similarly, an undo option in an editor can be implemented using a stack.

Implementing a stack with javascript

To implement a stack in javascript we can declare a stack class and use an array to store our data and a variable top to keep track of the stack length. To define a class we use the class keyword and add a constructor function to set up our array. We use the this keyword when defining the data to show we are referring to the current object.

class Stack {
  constructor() {
    this.data = [];
    this.top = 0;
  }
}

To use our stack we can create a new instance of the class using the new keyword

const stack = new Stack();

Right now our stack doesn't do much so we need to define some methods to make it functional.

We'll define the following methods

• push() - Adds an item to the top of the stack.
• pop() - Removes an item from the top of the stack.
• peek() - Shows the last element but doesn't remove it.
• length() - Returns the length of the stack.
• isEmpty() - Returns true of the stack is empty.
• print() - Prints the items in the stack.

push()

class Stack {
  constructor() {
    this.data = [];
    this.top = 0;
  }
  push(element) {
    this.data[this.top] = element;
    this.top++;
  }
}

To use push we can call the method on the stack instance

// adds 1 to the top of the stack
stack.push(1); 

pop()

  pop() {
    this.top--;
    /* we can use the javascript array pop method to remove the last
       item and return it.*/
    return this.data.pop();
  }

To use pop we can call the method on our instance and store the item in a variable

let lastItem = stack.pop()

peek()

peek() {
    return this.data[this.top - 1];
  }

To use peek we can call the method on our instance and store the item in a variable the item will not be removed from the stack.

let lastItem = stack.peek();

length()

  length() {
    return this.top;
  }

isEmpty()

 isEmpty() {
    return this.top === 0;
  }

print()

We will print the items from the end to the start. The top - 1 is the last element in the array and we loop from here back to 0 and console.log each item.

  print() {
    let i = this.top - 1;
    while (i >= 0) {
      console.log(this.data[i]);
      i--;
    }
  }

Our full class now looks like this

class Stack {
  constructor() {
    this.data = [];
    this.top = 0;
  }
  push(element) {
    this.data[this.top] = element;
    this.top++;
  }
  pop() {
    this.top--;
    return this.data.pop();
  }
  peek() {
    return this.data[this.top - 1];
  }
  length() {
    return this.top;
  }
  isEmpty() {
    return this.top === 0;
  }
  print() {
    let i = this.top - 1;
    while (i >= 0) {
      console.log(this.data[i]);
      i--;
    }
  }
}

Our stack is now ready to use and store data

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);

// logs 3, 2, 1
stack.print();

const length = stack.length();
// Logs 3
console.log(length);

const peek = stack.peek();
// Logs 3
console.log(peek);

const lastItem = stack.pop();
// Logs 3
console.log(lastItem);

const isEmpty = stack.isEmpty();
// logs false
console.log(isEmpty);

// logs 2, 1
stack.print();