MV's blog

Stacks

A stack is a data structure that stores a collection of values T. It has LIFO mechanics, i.e the last item that was added is the first item to be returned(removed).

A stack implements the following API:

interface IStack<T> {
  /**
   * Pushes an item on top of the stack, i.e at the beginning
   * @param  {T} value
   */
  push(value: T): void;

  /**
   * Removes and returns the item on top of the stack, i.e
   * from the beginning
   * @returns T
   */
  pop(): T;

  /**
   * Returns the number of items in the stack
   * @returns number
   */
  size(): number;

  /**
   * Returns whether the stack is empty
   * @returns boolean
   */
  isEmpty(): boolean;
}

Sample typescript implementation that uses a linked list for storing the values. For linked lists refer here.

export class Stack<T> implements IStack<T> {
  private first: ListNode<T> = null;
  private count: number = 0;

  public push(value: T): void {
    if (value == null) throw new Error('Invalid value');

    const node = new ListNode<T>();
    node.next = this.first;
    node.value = value;
    this.count++;
  }

  public pop(): T {
    if (this.isEmpty()) throw new Error('Invalid operation');

    const value = this.first.value;
    this.first = this.first.next;
    this.count--;

    return value;
  }

  public size(): number {
    return this.count;
  }

  public isEmpty(): boolean {
    return this.count === 0;
  }
}

Alternatively it can be implemented with an array, either a predefined one or with resizing; depending on the use case.

The time cost for the push() and pop() operations is O(1).

Image taken from: https://www.coursera.org/learn/algorithms-part1/