Implementing Stack Data Structure in Javascript

Implementing Stack Data Structure in Javascript

·

4 min read

A stack is a linear data structure that follows the Last In First Out (LIFO) or the First In Last Out (FILO) principle. This means that the last element added to the stack will be the first one to be removed. Stacks are used in a variety of applications, including but not limited to memory management, expression evaluation, and web page history navigation. In this article, we will be discussing the implementation of stacks in JavaScript.

Basics of a Stack

The stack data structure is similar to a real-life stack. For instance, think of a stack as a tall tower of plates. When you want to add a plate, you put it on top of the tower. When you want to take a plate, you only take the one that is on the top.

When we add something to a stack, we call it "pushing" the item into the stack. When we take something from the stack, we call it "popping" the item out of the stack. When we want to check what is the top most (last) item in the stack, we call it "peeking" into the stack.

Array Implementation

JavaScript has built-in support for stacks through the Array object. Arrays in JavaScript have a conveniently named push() method which allows us to add elements to the end of the array, and a pop() method which allows us to remove the last element from the array. While there is no peek() method built in, we can use our understanding of javascript arrays to access the last element through the length property.

For example, let's consider the following code:

let stack = [];
//push
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack); // Output: [1, 2, 3]
//pop
stack.pop();
console.log(stack); // Output: [1, 2]
//peek
stack[stack.length-1]
console.log(stack[stack.length-1]) //2

As you can see, we have implemented a basic stack using an array and its push() and pop() methods. Following the LIFO principle, we push 1, 2 and 3 into the array and then pop out the last value. Here is a quick illustration to visualize this:

"A visual representation of JavaScript code demonstrating the use of a stack data structure. The code shows how to push elements onto the stack, pop elements off the stack, and retrieve the top element using the peek operation.

Class-Based Implementation

In addition to using arrays, stacks can also be implemented as classes in JavaScript. A class-based implementation provides a more object-oriented approach and can be used to encapsulate the data and behavior of a stack. This can be especially useful in larger projects where you want to maintain a clear separation between different components.

Here's an example of how you can implement a stack as a class in JavaScript:

class Stack {
    constructor() {
        this.items = [];
    }
    push(element) {
        this.items.push(element);
    }
    pop() {
        return this.items.pop();
    }
    peek() {
        return this.items[this.items.length - 1];
    }
}

In this example, we've defined a Stack class with a constructor that initializes an empty array for storing elements. We've also added push(), pop(), and peek() methods to the class, allowing us to perform basic stack operations. This implementation gives us the flexibility to create multiple instances of the Stack class, each with its own separate data and behavior.

By using classes, we can also add additional functionality to our stacks as needed, such as methods for printing the contents of the stack or checking the size of the stack. Additionally, we can create subclasses that inherit from our Stack class and extend its behavior in new and interesting ways.

Class-based Implementation with Objects

In JavaScript, we can also have a class-based implementation of a stack using objects to store values instead of an array.

Here is an example of creating a class-based stack data structure using object data type for storage:

class Stack{
  constructor(){
    this.storage = {}
    this.size = 0
  }

  push(element){
    this.size++
    this.storage[this.size] = element
  }

  pop(){
    const returnVal = this.storage[this.size]
    delete this.storage[this.size]
    this.size--
    return returnVal
  }

  peek(){
    return this.storage[this.size]
  }
} 

const fruitStack = new Stack
fruitStack.push("Orange") //{ '1': 'Orange' }
fruitStack.push("Grapes") //{ '1': 'Orange', '2': 'Grapes' }
fruitStack.push("Apple") //{ '1': 'Orange', '2': 'Grapes', '3': 'Apple' }
fruitStack.pop() //Apple
fruitStack.pop() //Grapes
fruitStack.push("Apple") //{ '1': 'Orange', '2': 'Apple' }
fruitStack.peek() //Apple

Use Cases

Stacks are commonly used in web development, particularly in the context of web page navigation. Whenever you click a link on a web page, your browser pushes the URL of the new page onto the stack. When you press the back button, your browser pops the last URL from the stack and navigates back to the previous page. This is just one example of how stacks can simplify your code by allowing you to manage a list of elements in a straightforward way.

Conclusion

A stack is a powerful and versatile data structure that can simplify your code in a variety of applications. It provides an elegant solution that is easy to implement and understand. If you haven't already, give it a try in your next JavaScript project and see how it can simplify your code.