Data Structure: Stack in JavaScript and TypeScript

We use the Stack data structure to create a pile of data/information one after another and then process those from top to bottom. Items of a stack are accessed/processed on a Last-in-First-out basis. Stack support push and pop from the top.

Stack overview
Stack overview

NOTE

In this article, we are discussing in detail, the implementation of Stack in JavaScript and TypeScript.

Check the link below to check the details of Linked List and Singly Linked List-

In JavaScript we can implemen stack in 2 ways-

  • Using Linked list
  • Using JavaScript Array

Let’s check the implementation step by step-

Implementation #1: Stack using Linked List

Let’s implement the Stack data structure using Singly Linked List

  • The last inserted/added node is the “Top”.
  • To push an item we add a new to at the “Top”.
  • To pop items we remove them from “Top”.
Stack data structure using Linked List
Stack data structure using Linked List

Step #1: Node(Stack item) Class

We need a node class to store the Stack item.

Singly Linked List individual node
Stack – single node
Create a new class named “Node“.
Create “constructor” and accept “data”.
In the constructor initialize the property “next” to null. This will be used to store the next node of the list.
// Node class for storing data and reference to the next node
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
class Node<T> {
  data: T;
  next: Node<T> | null;

  constructor(data: T) {
    this.data = data;
    this.next = null;
  }
}

NOTE

For TypeScript we are using a generic and passing the type as <T>. This “T” type will be the type of data.

Step #2: Stack Class

Stack class has 2 main functionality – push and pop.

Stack using Linked List - Initial Stage
Stack using Linked List – Initial Stage
Create a class named “Stack“.
In the constructor set – top=null, size=0.
// Stack class
class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }
}
// Stack class
class Stack<T> {
  public top: Node<T> | null;
  public size: number;

  constructor() {
    this.top = null;
    this.size = 0;
  }
}

NOTE

For TypeScript we are using a generic and passing the type as <T>. We need to pass this type <T> to the “Node” item.

Step #3: Push

Add an item to top to push-

Stack data structure Push
Stack data structure Push
Create the function “push” and accept “data” as a parameter.
Create a new “Node” object from data “data“.
If there is no existing item, then set this newly created node as top.
If there is an existing item, then set the next of the new node to the current Top. and then move the Top to the new node.
Increase the size of the Stack by 1.
class Stack {
  // ...
  push(data) {
    const newNode = new Node(data);
    if (!this.top) {
      this.top = newNode;
    } else {
      newNode.next = this.top;
      this.top = newNode;
    }
    this.size++;
    return this.size;
  }
  // ...
}
class Stack<T> {
    //...


  push(data: T): number {
    const newNode = new Node(data);

    if (!this.top) {
      this.top = newNode;
    } else {
      newNode.next = this.top;
      this.top = newNode;
    }

    this.size++;

    return this.size;
  }

    //...
}

Step #4: Pop

Remove an item from the top to Pop-

Stack using Linked List - Pop
Stack using Linked List – Pop
Create a function named “pop“.
If there is no Top then return null.
Set the current Top of the stack in a variable.
Move the top of the stack, to the next node.
Decrease the size of the Stack by 1.
Return the old top that we saved in a variable.
class Stack {
  // ...
  pop() {
    if (!this.top) {
      return null; // Or return your expected empty value
    }
    const existingTop = this.top;
    this.top = this.top.next;
    this.size--;
    return existingTop.data;
  }
}
class Stack<T> {
    //...

  pop(): T|null {
    if (!this.top) {
      return null; // Or return your expected empty value
    }

    const existingTop = this.top;
    this.top = this.top.next;

    this.size--;

    return existingTop.data;
  }

    //...
}

Full Implementation Code

Here is the full implementation, with all the functionality.

// stack.js
// Implementation of stack using Linked List
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }
  push(data) {
    const newNode = new Node(data);
    if (!this.top) {
      this.top = newNode;
    } else {
      newNode.next = this.top;
      this.top = newNode;
    }
    this.size++;
    return this.size;
  }
  pop() {
    if (!this.top) {
      return null; // Or return your expected empty value
    }
    const existingTop = this.top;
    this.top = this.top.next;
    this.size--;
    return existingTop.data;
  }
}
export default Stack;
// stack.ts
// Implementation of stack using Linked List

class Node<T> {
  data: T;
  next: Node<T> | null;

  constructor(data: T) {
    this.data = data;
    this.next = null;
  }
}

class Stack<T> {
  public top: Node<T> | null;
  public size: number;

  constructor() {
    this.top = null;
    this.size = 0;
  }

  push(data: T): number {
    const newNode = new Node(data);

    if (!this.top) {
      this.top = newNode;
    } else {
      newNode.next = this.top;
      this.top = newNode;
    }

    this.size++;

    return this.size;
  }

  pop(): T|null {
    if (!this.top) {
      return null; // Or return your expected empty value
    }

    const existingTop = this.top;
    this.top = this.top.next;

    this.size--;

    return existingTop.data;
  }
}

export default Stack;

Demo

Here is the demo code for using the implemented functionality of Stack-

// demo.js
import Stack from "./stack.js";

// Create a new Stack
let bigboxStack = new Stack();

console.log("\n\n----------- Stack Push example -----------\n");

// Push items
console.log('Push - "Big" | Result: ', bigboxStack.push("Big"));
console.log('Push - "Box" | Result: ', bigboxStack.push("Box"));
console.log('Push - "Code" | Result: ', bigboxStack.push("Code"));

console.log("\n\n----------- Stack Pop example -----------\n");

// Pop items
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
// demo.ts
import Stack from "./stack";

// Create a new Stack
let bigboxStack = new Stack<string>();

console.log("\n\n----------- Stack Push example -----------\n");

// Push items
console.log('Push - "Big" | Result: ', bigboxStack.push("Big"));
console.log('Push - "Box" | Result: ', bigboxStack.push("Box"));
console.log('Push - "Code" | Result: ', bigboxStack.push("Code"));

console.log("\n\n----------- Stack Pop example -----------\n");

// Pop items
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());

Output:

Output of the demo code will look like below-

----------- Stack Push example -----------

Push - "Big" | Result:  1
Push - "Box" | Result:  2
Push - "Code" | Result:  3


----------- Stack Pop example -----------

Pop | Result:  Code
Pop | Result:  Box
Pop | Result:  Big
Pop | Result:  null

Tests

Let’s test the functionality using automated testing. Use the following code for testing.

// stack.test.js
import { describe, it, beforeEach, expect } from "vitest";
import Stack from "./stack";

describe("Stack using Linked List", () => {
  describe("Push item to Stack", () => {
    let stack;

    beforeEach(() => {
      stack = new Stack();
    });

    it("Should push items correctly", () => {
      let length = stack.push("Big");

      expect(length).toBe(1);

      length = stack.push("Box");

      expect(length).toBe(2);

      length = stack.push("Code");

      expect(length).toBe(3);
    });
  });

  describe("Pop item from Stack", () => {
    let stack;

    beforeEach(() => {
      stack = new Stack();

      // Push some items first
      stack.push("Big");
      stack.push("Box");
      stack.push("Code");
    });

    it("Should pop item correctly", () => {
      let item = stack.pop();

      expect(item).toBe("Code");

      item = stack.pop();

      expect(item).toBe("Box");

      item = stack.pop();

      expect(item).toBe("Big");

      item = stack.pop();

      expect(item).toBeNull();
    });
  });
});
// stack.test.ts
import { describe, it, beforeEach, expect } from "vitest";
import Stack from "./stack";

describe("Stack using Linked List", () => {
  describe("Push item to Stack", () => {
    let stack: Stack<string>;

    beforeEach(() => {
      stack = new Stack<string>();
    });

    it("Should push items correctly", () => {
      let length = stack.push("Big");

      expect(length).toBe(1);

      length = stack.push("Box");

      expect(length).toBe(2);

      length = stack.push("Code");

      expect(length).toBe(3);
    });
  });

  describe("Pop item from Stack", () => {
    let stack: Stack<string>;

    beforeEach(() => {
      stack = new Stack<string>();

      // Push some items first
      stack.push("Big");
      stack.push("Box");
      stack.push("Code");
    });

    it("Should pop item correctly", () => {
      let item = stack.pop();

      expect(item).toBe("Code");

      item = stack.pop();

      expect(item).toBe("Box");

      item = stack.pop();

      expect(item).toBe("Big");

      item = stack.pop();

      expect(item).toBeNull();
    });
  });
});

Time Complexity

The time complexity of operation on a Stack implementation using a linked list is as below-

OperationComplexity
PushO(1)
PopO(1)

Implementation #2: Stack using Array

Stack can be implemented using just array-

  • Push to push item to stack
  • Pop item from the stack

Step #1: Initialize

Create class “Stack”.
Define constructor.
Inside the constructor initialize array “stackItems”.
class Stack {
    constructor() {
        this.stackItems = [];
    }
}
class Stack<T> {
  private stackItems: T[];

  constructor() {
    this.stackItems = [];
  }
}

Step #2: Push

Stack using array - Push
Stack using array – Push
  • Declare method “push”.
  • Use the push() method of the array – Array.prototype.push(), to add an item at the end of the array.
class Stack {
  //....

  push(data) {
    this.stackItems.push(data);

    return this.stackItems.length;
  }
}
class Stack<T> {
  //....

  push(data: T): number {
    this.stackItems.push(data);
    return this.stackItems.length;
  }
}

Step #3: Pop

Stack using array - pop
Stack using array – pop
  • Use the pop() method to pop items from the front- Array.prototype.pop().
  • This returns the last item from an array.
class Stack {
  //...

  pop() {
    if (this.stackItems.length === 0) {
      return null; // Or return your expected empty value
    }

    return this.stackItems.pop();
  }
}
class Stack<T> {
  //...

  pop(): T | null {
    if (this.stackItems.length === 0) {
      return null; // Or return your expected empty value
    }
    return this.stackItems.pop()!;
  }
}

Full Source Code

Here is the full source code of the implementation-

// stack.js
// Implementation of stack using array

class Stack {
    constructor() {
        this.stackItems = [];
    }

    push(data) {
        this.stackItems.push(data);
        return this.stackItems.length;
    }

    pop() {
        if (this.stackItems.length === 0) {
            return null; // Or return your expected empty value
        }

        return this.stackItems.pop();
    }
}

export default Stack;
// stack.ts

class Stack<T> {
  private stackItems: T[];

  constructor() {
    this.stackItems = [];
  }

  push(data: T): number {
    this.stackItems.push(data);
    return this.stackItems.length;
  }

  pop(): T | null {
    if (this.stackItems.length === 0) {
      return null; // Or return your expected empty value
    }
    return this.stackItems.pop()!;
  }
}

export default Stack;

Demo

Use the following code check/demo the implementaiton-

// demo.js
import Stack from "./stack.js";

// Create a new Stack
let bigboxStack = new Stack();

console.log("\n\n----------- Stack Push example -----------\n");

// Push items
console.log('Push - "Big" | Result: ', bigboxStack.push("Big"));
console.log('Push - "Box" | Result: ', bigboxStack.push("Box"));
console.log('Push - "Code" | Result: ', bigboxStack.push("Code"));

console.log("\n\n----------- Stack Pop example -----------\n");

// Pop items
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
// demo.ts
import Stack from "./stack";

// Create a new Stack
let bigboxStack = new Stack<string>();

console.log("\n\n----------- Stack Push example -----------\n");

// Push items
console.log('Push - "Big" | Result: ', bigboxStack.push("Big"));
console.log('Push - "Box" | Result: ', bigboxStack.push("Box"));
console.log('Push - "Code" | Result: ', bigboxStack.push("Code"));

console.log("\n\n----------- Stack Pop example -----------\n");

// Pop items
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());

Output:

----------- Stack Push example -----------

Push - "Big" | Result:  1
Push - "Box" | Result:  2
Push - "Code" | Result:  3


----------- Stack Pop example -----------

Pop | Result:  Code
Pop | Result:  Box
Pop | Result:  Big
Pop | Result:  null

Tests

Here are the tests to check the implementation-

// stack.test.js
import { describe, it, beforeEach, expect } from "vitest";
import Stack from "./stack";

describe("Stack using array", () => {
  describe("Push item to Stack", () => {
    let stack;

    beforeEach(() => {
      stack = new Stack();
    });

    it("Should push items correctly", () => {
      let length = stack.push("Big");

      expect(length).toBe(1);

      length = stack.push("Box");

      expect(length).toBe(2);

      length = stack.push("Code");

      expect(length).toBe(3);
    });
  });

  describe("Pop item from Stack", () => {
    let stack;

    beforeEach(() => {
      stack = new Stack();

      // Push some items first
      stack.push("Big");
      stack.push("Box");
      stack.push("Code");
    });

    it("Should pop item correctly", () => {
      let item = stack.pop();

      expect(item).toBe("Code");

      item = stack.pop();

      expect(item).toBe("Box");

      item = stack.pop();

      expect(item).toBe("Big");

      item = stack.pop();

      expect(item).toBeNull();
    });
  });
});
// stack.test.ts
import { describe, it, beforeEach, expect } from "vitest";
import Stack from "./stack";

describe("Stack using array", () => {
  describe("Push item to Stack", () => {
    let stack: Stack<string>;

    beforeEach(() => {
      stack = new Stack<string>();
    });

    it("Should push items correctly", () => {
      let length = stack.push("Big");

      expect(length).toBe(1);

      length = stack.push("Box");

      expect(length).toBe(2);

      length = stack.push("Code");

      expect(length).toBe(3);
    });
  });

  describe("Pop item from Stack", () => {
    let stack: Stack<string>;

    beforeEach(() => {
      stack = new Stack<string>();

      // Push some items first
      stack.push("Big");
      stack.push("Box");
      stack.push("Code");
    });

    it("Should pop item correctly", () => {
      let item = stack.pop();

      expect(item).toBe("Code");

      item = stack.pop();

      expect(item).toBe("Box");

      item = stack.pop();

      expect(item).toBe("Big");

      item = stack.pop();

      expect(item).toBeNull();
    });
  });
});

Source Code

Use the following links to get the source code used in this article-

Related Data Structures

CommandDetails
Singly Linked List Singly Linked List Detail
Queue Queue Details

Other Code Implementations

Use the following links to check the Stack implementation in other programming languages-

Leave a Comment


The reCAPTCHA verification period has expired. Please reload the page.