Skip to main content

Stack

data-structure-typed

data-structure-typed / Stack

Class: Stack<E, R>

Defined in: data-structures/stack/stack.ts:135

LIFO stack with array storage and optional record→element conversion.

Remarks​

Time O(1), Space O(1)

Examples​

// Function Call Stack
 const functionStack = new Stack<string>();
    functionStack.push('main');
    functionStack.push('foo');
    functionStack.push('bar');
    console.log(functionStack.pop()); // 'bar';
    console.log(functionStack.pop()); // 'foo';
    console.log(functionStack.pop()); // 'main';
// Balanced Parentheses or Brackets
 type ValidCharacters = ')' | '(' | ']' | '[' | '}' | '{';

    const stack = new Stack<string>();
    const input: ValidCharacters[] = '[({})]'.split('') as ValidCharacters[];
    const matches: { [key in ValidCharacters]?: ValidCharacters } = { ')': '(', ']': '[', '}': '{' };
    for (const char of input) {
      if ('([{'.includes(char)) {
        stack.push(char);
      } else if (')]}'.includes(char)) {
        if (stack.pop() !== matches[char]) {
          fail('Parentheses are not balanced');
        }
      }
    }
    console.log(stack.isEmpty()); // true;
// Expression Evaluation and Conversion
 const stack = new Stack<number>();
    const expression = [5, 3, '+']; // Equivalent to 5 + 3
    expression.forEach(token => {
      if (typeof token === 'number') {
        stack.push(token);
      } else {
        const b = stack.pop()!;
        const a = stack.pop()!;
        stack.push(token === '+' ? a + b : 0); // Only handling '+' here
      }
    });
    console.log(stack.pop()); // 8;
// Backtracking Algorithms
 const stack = new Stack<[number, number]>();
    const maze = [
      ['S', ' ', 'X'],
      ['X', ' ', 'X'],
      [' ', ' ', 'E']
    ];
    const start: [number, number] = [0, 0];
    const end = [2, 2];
    const directions = [
      [0, 1], // To the right
      [1, 0], // down
      [0, -1], // left
      [-1, 0] // up
    ];

    const visited = new Set<string>(); // Used to record visited nodes
    stack.push(start);
    const path: number[][] = [];

    while (!stack.isEmpty()) {
      const [x, y] = stack.pop()!;
      if (visited.has(`${x},${y}`)) continue; // Skip already visited nodes
      visited.add(`${x},${y}`);

      path.push([x, y]);

      if (x === end[0] && y === end[1]) {
        break; // Find the end point and exit
      }

      for (const [dx, dy] of directions) {
        const nx = x + dx;
        const ny = y + dy;
        if (
          maze[nx]?.[ny] === ' ' || // feasible path
          maze[nx]?.[ny] === 'E' // destination
        ) {
          stack.push([nx, ny]);
        }
      }
    }

    console.log(path); // contains end;
// Stock Span Problem
 const stack = new Stack<number>();
    const prices = [100, 80, 60, 70, 60, 75, 85];
    const spans: number[] = [];
    prices.forEach((price, i) => {
      while (!stack.isEmpty() && prices[stack.peek()!] <= price) {
        stack.pop();
      }
      spans.push(stack.isEmpty() ? i + 1 : i - stack.peek()!);
      stack.push(i);
    });
    console.log(spans); // [1, 1, 1, 2, 1, 4, 6];
// Simplify File Paths
 const stack = new Stack<string>();
    const path = '/a/./b/../../c';
    path.split('/').forEach(segment => {
      if (segment === '..') stack.pop();
      else if (segment && segment !== '.') stack.push(segment);
    });
    console.log(stack.elements.join('/')); // 'c';
// Convert stack to array
 const stack = new Stack<number>([1, 2, 3]);
    console.log(stack.toArray()); // [1, 2, 3];

Extends​

Type Parameters​

E​

E = any

R​

R = any

  1. Last In, First Out (LIFO): The core characteristic of a stack is its last in, first out nature, meaning the last element added to the stack will be the first to be removed.
  2. Uses: Stacks are commonly used for managing a series of tasks or elements that need to be processed in a last in, first out manner. They are widely used in various scenarios, such as in function calls in programming languages, evaluation of arithmetic expressions, and backtracking algorithms.
  3. Performance: Stack operations are typically O(1) in time complexity, meaning that regardless of the stack's size, adding, removing, and viewing the top element are very fast operations.
  4. Function Calls: In most modern programming languages, the records of function calls are managed through a stack. When a function is called, its record (including parameters, local variables, and return address) is 'pushed' into the stack. When the function returns, its record is 'popped' from the stack.
  5. Expression Evaluation: Used for the evaluation of arithmetic or logical expressions, especially when dealing with parenthesis matching and operator precedence.
  6. Backtracking Algorithms: In problems where multiple branches need to be explored but only one branch can be explored at a time, stacks can be used to save the state at each branching point.

Constructors​

Constructor​

new Stack<E, R>(elements?, options?): Stack<E, R>;

Defined in: data-structures/stack/stack.ts:146

Create a Stack and optionally bulk-push elements.

Parameters​

elements?​

Iterable<E, any, any> | Iterable<R, any, any>

Iterable of elements (or raw records if toElementFn is set).

options?​

StackOptions<E, R>

Options such as toElementFn and equality function.

Returns​

Stack<E, R>

New Stack instance.

Remarks​

Time O(N), Space O(N)

Overrides​

IterableElementBase.constructor

Properties​

elements​

Get Signature​

get elements(): E[];

Defined in: data-structures/stack/stack.ts:159

Get the backing array of elements.

Remarks​

Time O(1), Space O(1)

Returns​

E[]

Internal elements array.

size​

Get Signature​

get size(): number;

Defined in: data-structures/stack/stack.ts:205

Get the number of stored elements.

Remarks​

Time O(1), Space O(1)

Example​
// Get number of elements
 const stack = new Stack<number>([1, 2, 3]);
    console.log(stack.size); // 3;
Returns​

number

Current size.

toElementFn​

Get Signature​

get toElementFn(): ((rawElement) => E) | undefined;

Defined in: data-structures/base/iterable-element-base.ts:47

Exposes the current toElementFn, if configured.

Remarks​

Time O(1), Space O(1).

Returns​

((rawElement) => E) | undefined

The converter function or undefined when not set.

Inherited from​

IterableElementBase.toElementFn

Methods​

[iterator]()​

iterator: IterableIterator<E>;

Defined in: data-structures/base/iterable-element-base.ts:60

Returns an iterator over the structure's elements.

Parameters​

args​

...unknown[]

Optional iterator arguments forwarded to the internal iterator.

Returns​

IterableIterator<E>

An IterableIterator<E> that yields the elements in traversal order.

Remarks​

Producing the iterator is O(1); consuming the entire iterator is Time O(n) with O(1) extra space.

Inherited from​

IterableElementBase.[iterator]

clear()​

clear(): void;

Defined in: data-structures/stack/stack.ts:586

Remove all elements and reset storage.

Returns​

void

void

Remarks​

Time O(1), Space O(1)

Example​

// Remove all elements
 const stack = new Stack<number>([1, 2, 3]);
    stack.clear();
    console.log(stack.isEmpty()); // true;

Overrides​

IterableElementBase.clear

clone()​

clone(): this;

Defined in: data-structures/stack/stack.ts:635

Deep clone this stack.

Returns​

this

A new stack with the same content.

Remarks​

Time O(N), Space O(N)

Example​

// Create independent copy
 const stack = new Stack<number>([1, 2, 3]);
    const copy = stack.clone();
    copy.pop();
    console.log(stack.size); // 3;
    console.log(copy.size); // 2;

Overrides​

IterableElementBase.clone

delete()​

delete(element): boolean;

Defined in: data-structures/stack/stack.ts:508

Delete the first occurrence of a specific element.

Parameters​

element​

E

Element to remove (using the configured equality).

Returns​

boolean

True if an element was removed.

Remarks​

Time O(N), Space O(1)

Example​

// Remove element
 const stack = new Stack<number>([1, 2, 3]);
    stack.delete(2);
    console.log(stack.toArray()); // [1, 3];

deleteAt()​

deleteAt(index): boolean;

Defined in: data-structures/stack/stack.ts:520

Delete the element at an index.

Parameters​

index​

number

Zero-based index from the bottom.

Returns​

boolean

True if removed.

Remarks​

Time O(N), Space O(1)

deleteWhere()​

deleteWhere(predicate): boolean;

Defined in: data-structures/stack/stack.ts:533

Delete the first element that satisfies a predicate.

Parameters​

predicate​

(value, index, stack) => boolean

Function (value, index, stack) → boolean to decide deletion.

Returns​

boolean

True if a match was removed.

Remarks​

Time O(N), Space O(1)

every()​

every(predicate, thisArg?): boolean;

Defined in: data-structures/base/iterable-element-base.ts:86

Tests whether all elements satisfy the predicate.

Parameters​

predicate​

ElementCallback<E, R, boolean>

Function invoked for each element with signature (value, index, self).

thisArg?​

unknown

Optional this binding for the predicate.

Returns​

boolean

true if every element passes; otherwise false.

Remarks​

Time O(n) in the worst case; may exit early when the first failure is found. Space O(1).

Inherited from​

IterableElementBase.every

filter()​

filter(predicate, thisArg?): this;

Defined in: data-structures/stack/stack.ts:686

Filter elements into a new stack of the same class.

Parameters​

predicate​

ElementCallback<E, R, boolean>

Predicate (value, index, stack) → boolean to keep value.

thisArg?​

unknown

Value for this inside the predicate.

Returns​

this

A new stack with kept values.

Remarks​

Time O(N), Space O(N)

Example​

// Filter elements
 const stack = new Stack<number>([1, 2, 3, 4, 5]);
    const evens = stack.filter(x => x % 2 === 0);
    console.log(evens.toArray()); // [2, 4];

Overrides​

IterableElementBase.filter

find()​

Call Signature​

find<S>(predicate, thisArg?): S | undefined;

Defined in: data-structures/base/iterable-element-base.ts:162

Finds the first element that satisfies the predicate and returns it.

Finds the first element of type S (a subtype of E) that satisfies the predicate and returns it.

Type Parameters​
S​

S

Parameters​
predicate​

ElementCallback<E, R, S>

Type-guard predicate: (value, index, self) => value is S.

thisArg?​

unknown

Optional this binding for the predicate.

Returns​

S | undefined

The matched element typed as S, or undefined if not found.

Remarks​

Time O(n) in the worst case; may exit early on the first match. Space O(1).

Inherited from​

IterableElementBase.find

Call Signature​

find(predicate, thisArg?): E | undefined;

Defined in: data-structures/base/iterable-element-base.ts:163

Finds the first element that satisfies the predicate and returns it.

Finds the first element of type S (a subtype of E) that satisfies the predicate and returns it.

Parameters​
predicate​

ElementCallback<E, R, unknown>

Type-guard predicate: (value, index, self) => value is S.

thisArg?​

unknown

Optional this binding for the predicate.

Returns​

E | undefined

The matched element typed as S, or undefined if not found.

Remarks​

Time O(n) in the worst case; may exit early on the first match. Space O(1).

Inherited from​

IterableElementBase.find

forEach()​

forEach(callbackfn, thisArg?): void;

Defined in: data-structures/base/iterable-element-base.ts:132

Invokes a callback for each element in iteration order.

Parameters​

callbackfn​

ElementCallback<E, R, void>

Function invoked per element with signature (value, index, self).

thisArg?​

unknown

Optional this binding for the callback.

Returns​

void

void.

Remarks​

Time O(n), Space O(1).

Inherited from​

IterableElementBase.forEach

has()​

has(element): boolean;

Defined in: data-structures/base/iterable-element-base.ts:188

Checks whether a strictly-equal element exists in the structure.

Parameters​

element​

E

The element to test with === equality.

Returns​

boolean

true if an equal element is found; otherwise false.

Remarks​

Time O(n) in the worst case. Space O(1).

Inherited from​

IterableElementBase.has

isEmpty()​

isEmpty(): boolean;

Defined in: data-structures/stack/stack.ts:274

Check whether the stack is empty.

Returns​

boolean

True if size is 0.

Remarks​

Time O(1), Space O(1)

Example​

// Check if stack has elements
 const stack = new Stack<number>();
    console.log(stack.isEmpty()); // true;
    stack.push(1);
    console.log(stack.isEmpty()); // false;

Overrides​

IterableElementBase.isEmpty

map()​

map<EM, RM>(
   callback, 
   options?, 
thisArg?): Stack<EM, RM>;

Defined in: data-structures/stack/stack.ts:761

Map values into a new stack (possibly different element type).

Type Parameters​

EM​

EM

RM​

RM

Parameters​

callback​

ElementCallback<E, R, EM>

Mapping function (value, index, stack) → newElement.

options?​

IterableElementBaseOptions<EM, RM>

Options for the output stack (e.g., toElementFn).

thisArg?​

unknown

Value for this inside the callback.

Returns​

Stack<EM, RM>

A new Stack with mapped elements.

Remarks​

Time O(N), Space O(N)

Example​

// Transform elements
 const stack = new Stack<number>([1, 2, 3]);
    const doubled = stack.map(x => x * 2);
    console.log(doubled.toArray()); // [2, 4, 6];

Overrides​

IterableElementBase.map

mapSame()​

mapSame(callback, thisArg?): this;

Defined in: data-structures/stack/stack.ts:704

Map values into a new stack of the same element type.

Parameters​

callback​

ElementCallback<E, R, E>

Mapping function (value, index, stack) → newValue.

thisArg?​

unknown

Value for this inside the callback.

Returns​

this

A new stack with mapped values.

Remarks​

Time O(N), Space O(N)

Overrides​

IterableElementBase.mapSame

peek()​

peek(): E | undefined;

Defined in: data-structures/stack/stack.ts:323

Get the top element without removing it.

Returns​

E | undefined

Top element or undefined.

Remarks​

Time O(1), Space O(1)

Example​

// View the top element without removing it
 const stack = new Stack<string>(['a', 'b', 'c']);
    console.log(stack.peek()); // 'c';
    console.log(stack.size); // 3;

pop()​

pop(): E | undefined;

Defined in: data-structures/stack/stack.ts:445

Pop and return the top element.

Returns​

E | undefined

Removed element or undefined.

Remarks​

Time O(1), Space O(1)

Example​

// Stack pop operation (LIFO - Last In First Out)
 const stack = new Stack<number>([10, 20, 30, 40, 50]);

    // Peek at the top element without removing
    const top = stack.peek();
    console.log(top); // 50;

    // Pop removes from the top (LIFO order)
    const popped = stack.pop();
    console.log(popped); // 50;

    // Next pop gets the previous element
    const next = stack.pop();
    console.log(next); // 40;

    // Verify length decreased
    console.log(stack.size); // 3;

print()​

print(): void;

Defined in: data-structures/base/iterable-element-base.ts:268

Prints toVisual() to the console. Intended for quick debugging.

Returns​

void

void.

Remarks​

Time O(n) due to materialization, Space O(n) for the intermediate representation.

Inherited from​

IterableElementBase.print

push()​

push(element): boolean;

Defined in: data-structures/stack/stack.ts:382

Push one element onto the top.

Parameters​

element​

E

Element to push.

Returns​

boolean

True when pushed.

Remarks​

Time O(1), Space O(1)

Example​

// basic Stack creation and push operation
 // Create a simple Stack with initial values
    const stack = new Stack([1, 2, 3, 4, 5]);

    // Verify the stack maintains insertion order (LIFO will be shown in pop)
    console.log([...stack]); // [1, 2, 3, 4, 5];

    // Check length
    console.log(stack.size); // 5;

    // Push a new element to the top
    stack.push(6);
    console.log(stack.size); // 6;

pushMany()​

pushMany(elements): boolean[];

Defined in: data-structures/stack/stack.ts:456

Push many elements from an iterable.

Parameters​

elements​

Iterable<E, any, any> | Iterable<R, any, any>

Iterable of elements (or raw records if toElementFn is set).

Returns​

boolean[]

Array of per-element success flags.

Remarks​

Time O(N), Space O(1)

reduce()​

Reduces all elements to a single accumulated value.

Param​

Reducer of signature (acc, value, index, self) => nextAcc. The first element is used as the initial accumulator.

Param​

Reducer of signature (acc, value, index, self) => nextAcc.

Param​

The initial accumulator value of type E.

Template​

The accumulator type when it differs from E.

Param​

Reducer of signature (acc: U, value, index, self) => U.

Param​

The initial accumulator value of type U.

Remarks​

Time O(n), Space O(1). Throws if called on an empty structure without initialValue.

Call Signature​

reduce(callbackfn): E;

Defined in: data-structures/base/iterable-element-base.ts:193

Parameters​
callbackfn​

ReduceElementCallback<E, R>

Returns​

E

Inherited from​

IterableElementBase.reduce

Call Signature​

reduce(callbackfn, initialValue): E;

Defined in: data-structures/base/iterable-element-base.ts:194

Parameters​
callbackfn​

ReduceElementCallback<E, R>

initialValue​

E

Returns​

E

Inherited from​

IterableElementBase.reduce

Call Signature​

reduce<U>(callbackfn, initialValue): U;

Defined in: data-structures/base/iterable-element-base.ts:195

Type Parameters​
U​

U

Parameters​
callbackfn​

ReduceElementCallback<E, R, U>

initialValue​

U

Returns​

U

Inherited from​

IterableElementBase.reduce

setEquality()​

setEquality(equals): this;

Defined in: data-structures/stack/stack.ts:782

Set the equality comparator used by delete/search operations.

Parameters​

equals​

(a, b) => boolean

Equality predicate (a, b) → boolean.

Returns​

this

This stack.

Remarks​

Time O(1), Space O(1)

some()​

some(predicate, thisArg?): boolean;

Defined in: data-structures/base/iterable-element-base.ts:109

Tests whether at least one element satisfies the predicate.

Parameters​

predicate​

ElementCallback<E, R, boolean>

Function invoked for each element with signature (value, index, self).

thisArg?​

unknown

Optional this binding for the predicate.

Returns​

boolean

true if any element passes; otherwise false.

Remarks​

Time O(n) in the worst case; may exit early on first success. Space O(1).

Inherited from​

IterableElementBase.some

toArray()​

toArray(): E[];

Defined in: data-structures/base/iterable-element-base.ts:245

Materializes the elements into a new array.

Returns​

E[]

A shallow array copy of the iteration order.

Remarks​

Time O(n), Space O(n).

Inherited from​

IterableElementBase.toArray

toVisual()​

toVisual(): E[];

Defined in: data-structures/base/iterable-element-base.ts:257

Returns a representation of the structure suitable for quick visualization. Defaults to an array of elements; subclasses may override to provide richer visuals.

Returns​

E[]

A visual representation (array by default).

Remarks​

Time O(n), Space O(n).

Inherited from​

IterableElementBase.toVisual

values()​

values(): IterableIterator<E>;

Defined in: data-structures/base/iterable-element-base.ts:71

Returns an iterator over the values (alias of the default iterator).

Returns​

IterableIterator<E>

An IterableIterator<E> over all elements.

Remarks​

Creating the iterator is O(1); full iteration is Time O(n), Space O(1).

Inherited from​

IterableElementBase.values

fromArray()​

static fromArray<E, R>(
   this, 
   elements, 
   options?): any;

Defined in: data-structures/stack/stack.ts:220

Create a stack from an array of elements.

Type Parameters​

E​

E

R​

R = any

Parameters​

this​

Object

The constructor (subclass) to instantiate.

elements​

E[]

Array of elements to push in order.

options?​

StackOptions<E, R>

Options forwarded to the constructor.

Returns​

any

A new Stack populated from the array.

Remarks​

Time O(N), Space O(N)

Protected Members​

_toElementFn?​

protected optional _toElementFn?: (rawElement) => E;

Defined in: data-structures/base/iterable-element-base.ts:38

The converter used to transform a raw element (R) into a public element (E).

Parameters​

rawElement​

R

Returns​

E

Remarks​

Time O(1), Space O(1).

Inherited from​

IterableElementBase._toElementFn

Accessors​

_createInstance()​

protected _createInstance(options?): this;

Defined in: data-structures/stack/stack.ts:806

(Protected) Create an empty instance of the same concrete class.

Parameters​

options?​

StackOptions<E, R>

Options forwarded to the constructor.

Returns​

this

An empty like-kind stack instance.

Remarks​

Time O(1), Space O(1)

_createLike()​

protected _createLike<T, RR>(elements?, options?): Stack<T, RR>;

Defined in: data-structures/stack/stack.ts:821

(Protected) Create a like-kind stack and seed it from an iterable.

Type Parameters​

T​

T = E

RR​

RR = R

Parameters​

elements?​

Iterable<T, any, any> | Iterable<RR, any, any>

Iterable used to seed the new stack.

options?​

StackOptions<T, RR>

Options forwarded to the constructor.

Returns​

Stack<T, RR>

A like-kind Stack instance.

Remarks​

Time O(N), Space O(N)

_getIterator()​

protected _getIterator(): IterableIterator<E>;

Defined in: data-structures/stack/stack.ts:838

(Protected) Iterate elements from bottom to top.

Returns​

IterableIterator<E>

Iterator of elements.

Remarks​

Time O(N), Space O(1)

Overrides​

IterableElementBase._getIterator

_indexOfByEquals()​

protected _indexOfByEquals(target): number;

Defined in: data-structures/stack/stack.ts:794

(Protected) Find the index of a target element using the equality function.

Parameters​

target​

E

Element to search for.

Returns​

number

Index or -1 if not found.

Remarks​

Time O(N), Space O(1)