Stack in JavaScript (Data Structures)

A stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).

Implementing stack using arrays:

Using the push/pop method (last in first out)

 let stack = [];

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

 // stack ==> [1, 2, 3]

 stack.pop() // 3
 stack.pop() // 2

Using the shift/unshift method

 let stack = [];
 stack.unshift(1);
 stack.unshift(2);
 stack.unshift(3);

 // stack ==> [1, 2, 3]

 stack.shift() // 3
 stack.shift() // 2

Note: Out of these two methods, shift/unshift is highly inefficient because adding/removing elements from the beginning of an array is very costly.

Creating a stack using a linked list:

Todos:

push and pop
peek

Creating a node: It contains a value and a pointer.

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

Stack class: it contains the first value, last value, and length.

class Stack {
    constructor() {
        this.first = null;
        this.last = null;
        this.length = 0;
    }
}

Push: add a value to the top of the stack. (technically unshifting in a linked list)

The function should accept a value.
Create a new node using that value.
If there are no nodes in the stack, set the first and last property of the stack to be the newly created node.
If there is at least one node, create a variable that stores the current first property on the stack.
Reset the first property to be the newly created node.
Set the next property on the node to be the previously created variable.

Increment the length of the stack by one.

 // push
     push(val) {
         var 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.length;
     }

Pop: remove from the beginning/top of the stack (Technically shift in the linked list)

If there are no nodes in the stack, return null.
Create a temporary variable to store the first property in the stack.
If there is only one node, set the first and last property to be null.
If there is more than one node, set the first property to be the next property on the current first.
Decrement the size by one.

Return the value of the node removed.

 // pop
     pop() {
         if(!this.first) return null;
         let temp = this.first;
         if(this.first === this.last) {
             this.first = null;
             this.last = null;
         }
         this.first = this.first.next;
         this.length--;
         return temp.val;
     }

Peek: returns the topmost value in the stack

// peek
    peek() {
        if(!this.first) return null;
        return this.first.val;
    }

Time Complexity of a Stack:

Access: O(n)
Search: O(n)
Insertion: O(1)
Removal: O(1)

Summary:

The Stack data structure is based on the LIFO (Last In First Out) principle. The element in the last can be accessed first.

Nilesh Saini's Blog

Nilesh Saini's Blog

Stack in JavaScript (Data Structures)

Short and Precise Js code to create a stack.

Table of contents

No headings in the article.