Алгоритмы. Стек.

stack.md

Stack implementation using TypeScript

A stack is an abstract data type that stores a collection of elements, with two principal operations:

• push: adds an element to the collection
• pop: removes the most recently added element that was not yet removed. The order in which elements are poped is Last In First Out aka. LIFO. In this lesson we discuss how to implement it using JavaScript / TypeScript.

A stack is a Last in First out (LIFO) with key operations having a time complexity of O(1).

The objective is to implement these push and pop operations such that they operate in O(1) time. Fortunately in JavaScript implementations, array function that do not require any changes to the index of current items, have an average runtime of O(1).

/**
 * Last in First out (LIFO) with O(1) key operations
 */
export class Stack<T> {
  private data: T[] = [];

  /** Adds the item in O(1) */
  push(item: T): void {
    this.data.push(item);
  }

  /**
   * Pops the last inserted item in O(1)
   * If there are no more items it returns `undefined`
   */
  pop(): T | undefined {
    return this.data.pop();
  }
  
  /**
   * Additional operation. Returns the number of elements in the stack in O(1)
   */
  size(): number {
    return this.data.length;
  }
}