DEV Community

siva sankar
siva sankar

Posted on

Stacks

What is a stack?

A LIFO data structure

LIFO (Last in first out)

The last element added to the stack will be the first element removed from the stack.

Think about it like a pile of books. You can only add books on top, and you can only remove the book on top.

we are going to create stack that has only two methods

  1. Push() : Method to add data to the stack
  2. Pop() : Method to remove data from the stack

we can do this in different ways, In this article we are going to implement with JavaScript es6 classes.

JavaScript Stack Implementation

class Node {
    constructor(val) {
        this.val = val
        this.next = null
    }
}

class Stack {

    constructor() {

        this.first = null;
        this.last = null;
        this.size = 0

    }

    push(val) {
        let newNode = new Node(val)
        if (!this.first) {
            this.first = newNode;
            this.last = newNode;
        }
        else {
            let temp = this.first;
            this.first = newNode;
            this.first.next = temp;
        }
        return ++this.size;
    }

    pop() {
        if (!this.first) return null;

        let temp = this.first;
        if (this.size === 1) {
            this.last = null;
        }
        this.first = this.first.next
        this.size--;
        return temp.value
    }
}


const stack = new Stack()

stack.push(1)
stack.push(2)
stack.push(3)
stack.pop()
stack.pop()
stack.pop()
stack.pop()

Enter fullscreen mode Exit fullscreen mode

Where stacks are used

  • Managing function invocations
  • Undo/Redo
  • Routing (History Object)

BIG O of Stacks

Insertion - O(1)
Removal - O(1)
Searching - O(n)
Access - O(n)

Discussion (0)