Wanna see something cool? Check out Angular Spotify 🎧
All Articles

TypeScript data structure: Stack

Stack

In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations:

  • push, which adds an element to the collection, and
  • pop, which removes the most recently added element that was not yet removed.

The order in which elements come off a stack gives rise to its alternative name, LIFO (last in, first out). Additionally, a peek operation may give access to the top without modifying the stack. The name “stack” for this type of structure comes from the analogy to a set of physical items stacked on top of each other, which makes it easy to take an item off the top of the stack, while getting to an item deeper in the stack may require taking off multiple other items first.

Simple representation of a stack runtime with push and pop operations.

Stack

Implementation

Implement using built-in object as a map, with tail pointer. I came up with this approach to make sure the Big O notation for the pop operation.

Operation Description Big O
push(value) adds an element to the collection O(1)
pop() removes the most recently added element O(1)
peek() returns the most recently added element without modifying the stack O(1)
clear() removes all the element in the stack O(1)
isEmpty checks if the stack is empty O(1)
size checks the size of the stack O(1)

Completed Source code

You can find the source code in my TS data structure repo

trungk18/typescript-data-structures/tree/master/data-structures/stack

import { ObjectType } from '../model/objectType';

export class Stack<T> {
  private _stack: ObjectType<T>;
  private _count: number;

  constructor() {
    this._stack = {};
    this._count = 0;
  }

  get isEmpty(): boolean {
    return this.size === 0;
  }

  get size(): number {
    return this._count;
  }

  push(value: T) {
    this._stack[this._count] = value;
    this._count++;
  }

  pop(): T {
    if (this.isEmpty) {
      return undefined;
    }
    this._count--;
    const value = this._stack[this._count];
    delete this._stack[this._count];
    return value;
  }

  peek(): T {
    if (this.isEmpty) {
      return undefined;
    }
    return this._stack[this._count - 1];
  }

  clear(): void {
    this._stack = {};
    this._count = 0;
  }

  print(): string {
    if (this.isEmpty) {
      return '';
    }
    let values = [];
    for (let i = 0; i < this._count; i++) {
      values.unshift((this._stack[i] as any).toString());
    }
    return values.join(' -> ');
  }
}

Alternative Implementation

  1. Trivial implementation using Array - Using arr.splice() for pop, could take O(n). That will not meet the requirement of O(1) for pop operation.
  2. Stack

References

Published 19 Jun 2021

Recent Posts

Difference between: function Person(){}, var person = Person(), and var person = new Person()?

Have you seen this question before?

TypeScript data structure: Queue

My implementation for Queue using TypeScript


Follow @tuantrungvo on Twitter for more!