MaiDeveloper

Introduction to stack data structure in JavaScript

What is stack data structure?

A stack is an abstract data type that stores an ordered collection of items which follow first in last out (FILO) or last in first out (LIFO) principle; with two principal operations: push, which adds an item to the stack, and pop, which removes the most recently added item.

Requirements

The stack data strucuture should contain the following methods:

  • push: add an item
  • pop: remove the most recently added item
  • peek: get the most recently added item
  • size: get the total number of items
  • isEmpty: return a boolean whether or not it is empty
  • clear: remove all the items

The data flow in and out from the stack should follow the first in last out (FILO) or last in first out (LIFO) principle. Think of this as a pile of books on your desk; the first book you put on the desk, is the last book you pick up. It is because when you pick up a book, you have to pick up the book that is on the top.

How to store the data?

There are two ways of storing the data in stack data structure; one is an array, the other is object. We will implement both of them.

Stack Data Structure Using Array

class Stack {
  constructor() {
    // AN ARRAY TO STORED AN ORDERED COLLECTION OF ITEMS
    this._items = [];
  }

  /**
   * Add an item
   * @param {*} item
   * @time complexity: O(1)
   * @space complexity: O(N)
   */
  push(item) {
    this._items.push(item);
  }

  /**
   * Remove the most recently added item
   * @return {*}
   * @time complexity: O(1)
   * @space complexity: O(1)
   */
  pop() {
    return this._items.pop();
  }

  /**
   * Get the most recently added item
   * @return {*}
   * @time complexity: O(1)
   * @space complexity: O(1)
   */
  peek() {
    return this._items[this._items.length - 1];
  }

  /**
   * Check whether it contains no items
   * @return {boolean}
   * @time complexity: O(1)
   * @space complexity: O(1)
   */
  isEmpty() {
    return this._items.length === 0;
  }

  /**
   * Get the total number of items
   * @return {number}
   * @time complexity: O(1)
   * @space complexity: O(1)
   */
  size() {
    return this._items.length;
  }

  /**
   * Remove all items
   * @time complexity: O(1)
   * @space complexity: O(1)
   */
  clear() {
    this._items = [];
  }
}

Stack Data Structure Using Object

class Stack {
  constructor() {
    // STORED ITEMS
    this._items = {};
    // TOTAL NUMBER OF ITEMS
    // ALSO USED AS A KEY TO KEEP ITEMS IN ORDER
    this._count = 0;
  }

  /**
   * Add an item
   * @param {*} item
   * @time complexity: O(1)
   * @space complexity: O(N)
   */
  push(item) {
    this._items[this._count] = item;
    this._count++;
  }

  /**
   * Remove the most recently added item
   * @return {*}
   * @time complexity: O(1)
   * @space complexity: O(1)
   */
  pop() {
    if (this.isEmpty()) {
      return undefined;
    }

    this._count--;
    const result = this._items[this._count];
    delete this._items[this._count];

    return result;
  }

  /**
   * Get the most recently added item
   * @return {*}
   * @time complexity: O(1)
   * @space complexity: O(1)
   */
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }

    return this._items[this._count - 1];
  }

  /**
   * Check whether it contains no items
   * @return {boolean}
   * @time complexity: O(1)
   * @space complexity: O(1)
   */
  isEmpty() {
    return this._count === 0;
  }
  
  /**
   * Get the total number of items
   * @return {number}
   * @time complexity: O(1)
   * @space complexity: O(1)
   */
  size() {
    return this._count;
  }

  /**
   * Remove all items
   * @time complexity: O(1)
   * @space complexity: O(1)
   */
  clear() {
    this._items = {};
    this._count = 0;
  }
}

Protecting the internal data

So far both implementation works, but are not protecting the data. What I mean is that, you or someone else still can access and modify the data directly without calling the functions. This is bad, because they might break the FILO or LIFO principle.

For this reason, we as developers prefer to use underscore ( _ ) naming convention to mark an attribute as private in javascript. But that doesn't prevent other people to modify it.

In order to protect the data, we have to use WeakMap. The following implementation uses WeakMap to store the data.

Stack Data Structure Using Object With WeakMap

const items = new WeakMap();
const count = new WeakMap();

class Stack {
  constructor() {
    // STORED ITEMS
    items.set(this, {});

    // TOTAL NUMBER OF ITEMS
    // ALSO USED AS A KEY TO KEEP ITEMS IN ORDER
    count.set(this, 0);
  }

  /**
   * Add an item
   * @param {*} item
   * @time complexity: O(1)
   * @space complexity: O(N)
   */
  push(item) {
    items.get(this)[count.get(this)] = item;
    count.set(this, count.get(this) + 1);
  }

  /**
   * Remove the most recently added item
   * @return {*}
   * @time complexity: O(1)
   * @space complexity: O(1)
   */
  pop() {
    if (this.isEmpty()) {
      return undefined;
    }

    count.set(this, count.get(this) - 1);

    const item = items.get(this)[count.get(this)];

    delete items.get(this)[count.get(this)];

    return item;
  }

  /**
   * Get the most recently added item
   * @return {*}
   * @time complexity: O(1)
   * @space complexity: O(1)
   */
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }

    return items.get(this)[count.get(this) - 1];
  }

  /**
   * Check whether it contains no items
   * @return {boolean}
   * @time complexity: O(1)
   * @space complexity: O(1)
   */
  isEmpty() {
    return count.get(this) === 0;
  }

  /**
   * Get the total number of items
   * @return {number}
   * @time complexity: O(1)
   * @space complexity: O(1)
   */
  size() {
    return count.get(this);
  }

  /**
   * Remove all items
   * @time complexity: O(1)
   * @space complexity: O(1)
   */
  clear() {
    items.set(this, {});
    count.set(this, 0);
  }
}

Test with Jest

describe('Stack Data Structure', () => {

  let stack;

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

  describe('push', () => {
    test('should be a function', () => {
      expect(typeof stack.push).toEqual('function');
    });
  });

  describe('pop', () => {
    test('should be a function', () => {
      expect(typeof stack.pop).toEqual('function');
    });
  });

  describe('push and pop', () => {
    test('should add an item and remove an item', () => {
      stack.push(1);
      stack.pop();
      expect(stack.size()).toEqual(0);
    });

    test('should implement FILO (First In Last Out) principle', () => {
      stack.push(1);
      stack.push(2);
      stack.push(3);
      expect(stack.pop()).toEqual(3);
      expect(stack.pop()).toEqual(2);
      expect(stack.pop()).toEqual(1);
    });

  });

  describe('size', () => {
    test('should be a function', () => {
      expect(typeof stack.size).toEqual('function');
    });

    test('should return 0 at the beginning', () => {
      expect(stack.size()).toEqual(0);
    });
    
    test('should return the total number of items', () => {
      stack.push(1);
      expect(stack.size()).toEqual(1);
      stack.push(2);
      expect(stack.size()).toEqual(2);
      stack.push(3);
      stack.push(4);
      stack.push(5);
      expect(stack.size()).toEqual(5);
    });
  });

  describe('isEmpty', () => {
    test('should be a function', () => {
      expect(typeof stack.isEmpty).toEqual('function');
    });

    test('should return true if there is no item', () => {
      expect(stack.isEmpty()).toEqual(true);
    });

    test('should return false if there is at least one item', () => {
      stack.push(1);
      expect(stack.isEmpty()).toEqual(false);
    });
  });

  describe('peek', () => {
    test('should be a function', () => {
      expect(typeof stack.peek).toEqual('function');
    });

    test('should return undefined if there is no item', () => {
      expect(stack.peek()).toEqual(undefined);
    });

    test('should return the last item', () => {
      stack.push(1);
      stack.push(2);
      expect(stack.peek()).toEqual(2);
    });

    test('should not delete the item', () => {
      stack.push(1);
      stack.push(2);
      stack.push(3);
      expect(stack.peek()).toEqual(3);
      expect(stack.peek()).toEqual(3);
    });

  });

  describe('clear', () => {
    test('should be a function', () => {
      expect(typeof stack.clear).toEqual('function');
    });

    test('should delete all the items', () => {
      stack.push(1);
      stack.push(2);
      stack.clear();
      expect(stack.size()).toEqual(0);
    });
  });

});
  Stack Data Structure
    push
      ✓ should be a function (2 ms)
    pop
      ✓ should be a function (1 ms)
    push and pop
      ✓ should add an item and remove an item
      ✓ should implement FILO (First In Last Out) principle
    size
      ✓ should be a function
      ✓ should return 0 at the beginning (1 ms)
      ✓ should return the total number of items
    isEmpty
      ✓ should be a function
      ✓ should return true if there is no item
      ✓ should return false if there is at least one item (1 ms)
    peek
      ✓ should be a function
      ✓ should return undefined if there is no item
      ✓ should return the last item
      ✓ should not delete the item
    clear
      ✓ should be a function (1 ms)
      ✓ should delete all the items


Mike Mai
Mike Mai   Brooklyn, New York
I am full-stack web developer, passionate about building world class web applications. Knowledge in designing, coding, testing, and debugging. I love to solve problems.