Dustin Boston

/**
 * @file Stack
 * @author Dustin Boston
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 *   Introduction to Algorithms. (2nd ed). The MIT Press.
 */

/** Implements a basic stack data structure with push and pop operations. */
export class Stack<T> {
  private stack: T[];
  private top: number;

  /**
   * Constructs a stack instance.
   *
   * @param array - An array to initialize the stack with.
   */
  constructor(array: T[] = []) {
    this.stack = array;
    this.top = -1;
  }

  /**
   * Checks if the stack is empty. O(1) time.
   *
   * @returns True if the stack is empty, false otherwise.
   */
  stackEmpty(): boolean {
    return this.top === -1;
  }

  /**
   * Adds an element to the top of the stack. O(1) time.
   *
   * @param element - The element to push onto the stack.
   */
  push(element: T): void {
    this.top += 1;
    this.stack[this.top] = element;
  }

  /**
   * Removes and returns the element at the top of the stack in O(1) time.
   *
   * @returns The element removed from the top of the stack.
   * @throws If the stack is empty (underflow).
   */
  pop(): T {
    if (!this.stackEmpty()) {
      this.top -= 1;
      return this.stack[this.top + 1];
    }

    throw new Error("Cannot pop from an empty stack.");
  }
}

(() => {
  const array = Array.from({length: 6}, () => 0);
  const stack = new Stack<number>(array);
  stack.push(4);
  if (array[0] !== 4) {
    throw new Error(`Expected 4 but got ${array[0]}`);
  }

  console.log(`Pushed 4 to the stack.`);

  const value = stack.pop();
  if (value !== 4) {
    throw new Error(`Expected value of 4 but got ${array[0]}`);
  }

  console.log(`Popped ${value} from the stack.`);
})();

import {Stack} from "../../../../data/algorithms/src/stack.ts";
import {assertEquals, assertThrows} from "$assert";

test(function testPush() {
  const array = Array.from({length: 6});
  const stack = new Stack<number>(array);
  stack.push(4);
  assertEquals(array[0], 4);
});

test(function testPop() {
  const array = Array.from({length: 6});
  const stack = new Stack<number>(array);
  stack.push(4);

  const value = stack.pop();
  assertEquals(value, 4);
});

test(function testUnderflow() {
  const array = Array.from({length: 6});
  const stack = new Stack<number>(array);
  assertThrows(() => {
    stack.pop();
  });
});

test(function testStackEmpty() {
  const array = Array.from({length: 6});
  const stack = new Stack<number>(array);
  assertEquals(stack.stackEmpty(), true);
});