Data Structure: Stack

Summary

Data Structure Name	Stack
Type	Linear Data Structure
Tagline	LIFO – Last In First Out
Operations	Push Pop
Use cases

Definition

Stack is a data structure that has only one end for performing operations. All operations can be performed at the head, be it adding(pushing) elements or removing(popping) elements.

Stack follows the LIFO – Last In First Out principle, so the item that is inserted at the last, is removed(popped) first.

NOTE

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

Stack Details

Use Cases

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.

Implementation

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”.

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.

JavaScript

TypeScript

// 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.

JavaScript
TypeScript

// 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-

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.

JavaScript
TypeScript

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.

JavaScript
TypeScript

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.

JavaScript
TypeScript

// 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-

JavaScript
TypeScript

// 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.

JavaScript
TypeScript

// 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-

Operation	Complexity
Push	O(1)
Pop	O(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”.

JavaScript
TypeScript

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.

JavaScript

TypeScript

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.

JavaScript
TypeScript

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-

JavaScript
TypeScript

// 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-

JavaScript
TypeScript

// 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-

JavaScript
TypeScript

// 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-

Source Code of	Programming Language	Implementation Code	Demo Code	Test Code
Stack using Linked List	JavaScript Implementation	GitHub	GitHub	GitHub
Stack using Linked List	TypeScript Implementation	GitHub	GitHub	GitHub
Stack using Array	JavaScript Implementation	GitHub	GitHub	GitHub
Stack using Array	TypeScript Implementation	GitHub	GitHub	GitHub

Related Data Structures

Command	Details
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-

Summary

Definition

Use Cases

Implementation

Implementation #1: Stack using Linked List

Step #1: Node(Stack item) Class

Step #2: Stack Class

Step #3: Push

Step #4: Pop

Full Implementation Code

Demo

Output

Tests

Time Complexity

Implementation #2: Stack using Array

Step #1: Initialize

Step #2: Push

Step #3: Pop

Full Source Code

Demo

Output

Tests

Source Code

Related Data Structures

Other Code Implementations

Leave a Comment Cancel reply