Stack

Posted by Dustin Boston in Data Structures.

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. Elements are added and removed from the same end, called the top. Common operations include push (add an element), pop (remove the top element), and peek (view the top element without removing it). Stacks are used in various applications like function call management, expression evaluation, and backtracking.

Time complexity for access and search is Linear, i.e. O(n)
Time complexity for insertion and deletion is Constant, i.e. O(1)
Space complexity is Linear

Source Code Listing

code.ts

/**
 * @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.`);
})();

code_test.ts

import {describe, test, expect} from "bun:test";
import {Stack} from "./code";

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

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

  const value = stack.pop();
  expect(value).toBe(4);
});

test("testUnderflow", () => {
  const array: number[] = Array.from({length: 6});
  const stack = new Stack<number>(array);
  expect(() => stack.pop()).toThrow();
});

test("testStackEmpty", () => {
  const array: number[] = Array.from({length: 6});
  const stack = new Stack<number>(array);
  expect(stack.stackEmpty()).toBe(true);
});

Tags: