Stack data structure in JavaScript

A data structure is a way to store and use data efficiently.

Different programming languages have different data structures. It's possible to implement data structures in different ways.

In this article, I'll be walking you through how to implement the Stack data structure in JavaScript.

Stack

A Stack is a linear data structure in which the insertion and deletion of elements are done at only one end, which is known as the top of the stack.

A Stack is a temporary memory in which values are stored and retrieved in a LIFO (last in, first out) manner.

Because of the LIFO nature of the Stack, any element that's not at the top of the stack can't be accessed. To get to the last element in a stack, you have to first remove all the elements above it

Real-life examples of stacks are; a stack of books, and a stack of plates.

How is a Stack different from an Array

In an Array, any element can be accessed, either immediately, if its index number is known, or by searching through a sequence of cells until it's found.

A Stack is simply an array with restrictions: Only one element can be read or removed at a given time.

Some applications of Stack

1. Temporary storage structure for recursive operations.

2. Manage function calls.

3. UNDO and REDO function in an editor.

4. String reversal.

5. Matching parenthesis.

Stack operations

Two basic operations associated with stacks are:

1. push: Push operation is used to add new elements to the stack

2. pop: Pop operation is used to remove elements from the stack.

While performing these operations on a stack, the following tests must be carried out

1. stack is empty or not

2. stack is full or not.

In Javascript, Arrays don't have a fixed size, so test 2 can be ignored

Apart from these basic operations, there are other operations we need to define and properties we need to examine

1. peek: To view the element at the top of the stack

2. clear: Clear operation removes all the elements from a Stack

3. length: The length property holds the number of elements in a Stack.

Stack implementation

The underlying mechanism for storing our Stack elements can be an array, as I'll be using here, or it can be a linkedList.

Let us begin by declaring our Stack class, and inside the constructor method, we create and initialize our stackData array, and top variable.

class Stack{
    construntor(){
        this.stackData = [];
        this.top = 0;
    }
}

stackData is the name of the array for holding the stack elements, the top variable keeps track of the top of the stack, which is initialized to 0.

Let us define our push method. To push an element onto the stack, we increment the top value by 1.

push(element){
    this.stackData[this.top++] = element
}

Let us define our pop method. To remove an element from the top of the stack, we return the top element and decrement the top variable by 1.

But we first need to check if our stack is empty or not.

pop(){
    if(this.top == 0){
        return 'stack is underflow'
    }else{
        return this.stackData[--this.top]
    }
}

Let us define our peek method. We simply return the top element of the stack

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

Let us define our two remaining methods; length and clear respectively. The length method returns the current value of top variable, while clear sets top to 0.

length(){
    return this.top;
}

clear(){
    this.top = 0;
}

Bringing everything together

Let us add all the methods defined to the body of our Stack class.

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

    pop(){
        if (this.top == 0) {
            return 'Stack is under flow';     
        } else {
            return this.stackData[--this.top];
        }
    }
    peek(){
        return this.stackData[this.top-1];
    }
    length(){
        return this.top;
    }
    clear(){
        this.top = 0;
    }
}
// Testing our stack implementation
const stack = new Stack();
stack.push('hello');
stack.push('bonjour');

console.log(stack.peek())
console.log('length:', stack.length())
stack.pop()
console.log('removed:', stack.pop())
console.log('new length is:', stack.length())

// Expected output:
bonjour
length: 2
removed: hello
new length is: 0

Some common use of our Stack class

1. Reversing a string

We are going to write a reverse function that reverses a string. So, if the function accepts the argument "abcde", it'll return "edcba".

function reverses(str) {
  const stack = new Stack()
  let rStr= ''
  for (let i = 0; i < str.length; i++) {
    stack.push(str[i])
  }
  while (stack.length() > 0){
    rStr += stack.pop();
  }
  return rStr
}

1.Palindromes

A palindrome is a word or number that is spelled the same way forward and backward. For example "racecar" is a palindrome, and "2002" is a palindrome.

 function palindrome(word){
        let data = new Stack();
        for (let i = 0; i < word.length; i++) {
            data.push(word[i]);           
        }
        let reverseWord = '';
        while (data.length() > 0) {
            reverseWord += data.pop();
        }
        if (word == reverseWord) {
            return true;
        } else {
            return false;
        }
    }
console.log(palindrome('racecar'));

3.Factorial

function factorial(x) {
    let stack = new Stack();
    while (x > 0) {
        stack.push(x--)
    }
    let ans = 1;
    while (stack.length() > 0) {
        ans *= stack.pop();
    }
    console.log(ans)
}

factorial(5)