Class Stack<E, R>

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

Remarks

Time O(1), Space O(1)

Example

// 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

Example

// 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

Example

// Depth-First Search (DFS)
    const stack = new Stack<number>();
    const graph: { [key in number]: number[] } = { 1: [2, 3], 2: [4], 3: [5], 4: [], 5: [] };
    const visited: number[] = [];
    stack.push(1);
    while (!stack.isEmpty()) {
      const node = stack.pop()!;
      if (!visited.includes(node)) {
        visited.push(node);
        graph[node].forEach(neighbor => stack.push(neighbor));
      }
    }
    console.log(visited); // [1, 3, 5, 2, 4]

Example

// 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]);
        }
      }
    }

    expect(path).toContainEqual(end);

Example

// 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'

Example

// 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'

Example

// 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]

Type Parameters

E = any
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.

Hierarchy (view full)

IterableElementBase<E, R>
- Stack

Index

Constructors

constructor

new Stack<E, R>(elements?, options?): Stack<E, R>
Create a Stack and optionally bulk-push elements.
Type Parameters
- E = any
- R = any
Parameters
- Optionalelements: Iterable<E, any, any> | Iterable<R, any, any> = []
  Iterable of elements (or raw records if toElementFn is set).
- Optionaloptions: 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
- Defined in data-structures/stack/stack.ts:156

Properties

`Protected` `Optional`_toElementFn

_toElementFn?: ((rawElement: R) => E)

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

Remarks

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

Accessors

elements

get elements(): E[]
Get the backing array of elements.

Returns E[]
Internal elements array.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/stack/stack.ts:169

size

get size(): number
Get the number of stored elements.

Returns number
Current size.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/stack/stack.ts:179

toElementFn

get toElementFn(): undefined | ((rawElement: R) => E)
Exposes the current toElementFn, if configured.

Returns undefined | ((rawElement: R) => E)
The converter function or undefined when not set.

Remarks
Time O(1), Space O(1).
Inherited from IterableElementBase.toElementFn
- Defined in data-structures/base/iterable-element-base.ts:47

Methods

`Protected`_createInstance

_createInstance(options?): this
(Protected) Create an empty instance of the same concrete class.
Parameters
- Optionaloptions: StackOptions<E, R>
  Options forwarded to the constructor.
Returns this
An empty like-kind stack instance.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/stack/stack.ts:416

`Protected`_createLike

_createLike<T, RR>(elements?, options?): Stack<T, RR>
(Protected) Create a like-kind stack and seed it from an iterable.
Type Parameters
- T = E
- RR = R
Parameters
- Optionalelements: Iterable<T, any, any> | Iterable<RR, any, any> = []
  Iterable used to seed the new stack.
- Optionaloptions: StackOptions<T, RR>
  Options forwarded to the constructor.
Returns Stack<T, RR>
A like-kind Stack instance.

Remarks
Time O(N), Space O(N)
- Defined in data-structures/stack/stack.ts:431

`Protected`_getIterator

_getIterator(): IterableIterator<E, any, any>
(Protected) Iterate elements from bottom to top.

Returns IterableIterator<E, any, any>
Iterator of elements.

Remarks
Time O(N), Space O(1)
Overrides IterableElementBase._getIterator
- Defined in data-structures/stack/stack.ts:448

`Protected`_indexOfByEquals

_indexOfByEquals(target): number
(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)
- Defined in data-structures/stack/stack.ts:404

[iterator]

[iterator](...args): IterableIterator<E, any, any>
Returns an iterator over the structure's elements.
Parameters
- Rest...args: unknown[]
  Optional iterator arguments forwarded to the internal iterator.
Returns IterableIterator<E, any, any>
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]
- Defined in data-structures/base/iterable-element-base.ts:60

clear

clear(): void
Remove all elements and reset storage.

Returns void
void

Remarks
Time O(1), Space O(1)
Overrides IterableElementBase.clear
- Defined in data-structures/stack/stack.ts:308

clone

clone(): this
Deep clone this stack.

Returns this
A new stack with the same content.

Remarks
Time O(N), Space O(N)
Overrides IterableElementBase.clone
- Defined in data-structures/stack/stack.ts:318

delete

delete(element): boolean
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)
- Defined in data-structures/stack/stack.ts:267

deleteAt

deleteAt(index): boolean
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)
- Defined in data-structures/stack/stack.ts:279

deleteWhere

deleteWhere(predicate): boolean
Delete the first element that satisfies a predicate.
Parameters
- predicate: ((value: E, index: number, stack: this) => boolean)
  Function (value, index, stack) → boolean to decide deletion.
  - - (value, index, stack): boolean
    - Parameters
      value: E
      index: number
      stack: this
      Returns boolean
Returns boolean
True if a match was removed.

Remarks
Time O(N), Space O(1)
- Defined in data-structures/stack/stack.ts:292

every

every(predicate, thisArg?): boolean
Tests whether all elements satisfy the predicate.
Parameters
- predicate: ElementCallback<E, R, boolean>
  Function invoked for each element with signature (value, index, self).
- OptionalthisArg: 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
- Defined in data-structures/base/iterable-element-base.ts:86

filter

filter(predicate, thisArg?): this
Filter elements into a new stack of the same class.
Parameters
- predicate: ElementCallback<E, R, boolean>
  Predicate (value, index, stack) → boolean to keep value.
- OptionalthisArg: unknown
  Value for this inside the predicate.
Returns this
A new stack with kept values.

Remarks
Time O(N), Space O(N)
Overrides IterableElementBase.filter
- Defined in data-structures/stack/stack.ts:332

find

find<S>(predicate, thisArg?): undefined | S
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
Parameters
- predicate: ElementCallback<E, R, S>
  Type-guard predicate: (value, index, self) => value is S.
- OptionalthisArg: unknown
  Optional this binding for the predicate.
Returns undefined | S
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
- Defined in data-structures/base/iterable-element-base.ts:162

forEach

forEach(callbackfn, thisArg?): void
Invokes a callback for each element in iteration order.
Parameters
- callbackfn: ElementCallback<E, R, void>
  Function invoked per element with signature (value, index, self).
- OptionalthisArg: unknown
  Optional this binding for the callback.
Returns void
void.

Remarks
Time O(n), Space O(1).
Inherited from IterableElementBase.forEach
- Defined in data-structures/base/iterable-element-base.ts:132

has

has(element): boolean
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
- Defined in data-structures/base/iterable-element-base.ts:188

isEmpty

isEmpty(): boolean
Check whether the stack is empty.

Returns boolean
True if size is 0.

Remarks
Time O(1), Space O(1)
Overrides IterableElementBase.isEmpty
- Defined in data-structures/stack/stack.ts:208

map

map<EM, RM>(callback, options?, thisArg?): Stack<EM, RM>
Map values into a new stack (possibly different element type).
Type Parameters
- EM
- RM
Parameters
- callback: ElementCallback<E, R, EM>
  Mapping function (value, index, stack) → newElement.
- Optionaloptions: IterableElementBaseOptions<EM, RM>
  Options for the output stack (e.g., toElementFn).
- OptionalthisArg: unknown
  Value for this inside the callback.
Returns Stack<EM, RM>
A new Stack with mapped elements.

Remarks
Time O(N), Space O(N)
Overrides IterableElementBase.map
- Defined in data-structures/stack/stack.ts:371

mapSame

mapSame(callback, thisArg?): this
Map values into a new stack of the same element type.
Parameters
- callback: ElementCallback<E, R, E>
  Mapping function (value, index, stack) → newValue.
- OptionalthisArg: 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
- Defined in data-structures/stack/stack.ts:350

peek

peek(): undefined | E
Get the top element without removing it.

Returns undefined | E
Top element or undefined.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/stack/stack.ts:218

pop

pop(): undefined | E
Pop and return the top element.

Returns undefined | E
Removed element or undefined.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/stack/stack.ts:240

print

print(): void
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
- Defined in data-structures/base/iterable-element-base.ts:268

push

push(element): boolean
Push one element onto the top.
Parameters
- element: E
  Element to push.
Returns boolean
True when pushed.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/stack/stack.ts:229

pushMany

pushMany(elements): boolean[]
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)
- Defined in data-structures/stack/stack.ts:251

reduce

reduce(callbackfn): E
Parameters
- callbackfn: ReduceElementCallback<E, R>
Returns E
Inherited from IterableElementBase.reduce
- Defined in data-structures/base/iterable-element-base.ts:193
reduce(callbackfn, initialValue): E
Parameters
- callbackfn: ReduceElementCallback<E, R>
- initialValue: E
Returns E
Inherited from IterableElementBase.reduce
- Defined in data-structures/base/iterable-element-base.ts:194
reduce<U>(callbackfn, initialValue): U
Type Parameters
- U
Parameters
- callbackfn: ReduceElementCallback<E, R, U>
- initialValue: U
Returns U
Inherited from IterableElementBase.reduce
- Defined in data-structures/base/iterable-element-base.ts:195

setEquality

setEquality(equals): this
Set the equality comparator used by delete/search operations.
Parameters
- equals: ((a: E, b: E) => boolean)
  Equality predicate (a, b) → boolean.
  - - (a, b): boolean
    - Parameters
      a: E
      b: E
      Returns boolean
Returns this
This stack.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/stack/stack.ts:392

some

some(predicate, thisArg?): boolean
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).
- OptionalthisArg: 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
- Defined in data-structures/base/iterable-element-base.ts:109

toArray

toArray(): E[]
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
- Defined in data-structures/base/iterable-element-base.ts:245

toVisual

toVisual(): E[]
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
- Defined in data-structures/base/iterable-element-base.ts:257

values

values(): IterableIterator<E, any, any>
Returns an iterator over the values (alias of the default iterator).

Returns IterableIterator<E, any, any>
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
- Defined in data-structures/base/iterable-element-base.ts:71

`Static`fromArray

fromArray<E, R>(this, elements, options?): any
Create a stack from an array of elements.
Type Parameters
- E
- R = any
Parameters
- this: Object
  The constructor (subclass) to instantiate.
- elements: E[]
  Array of elements to push in order.
- Optionaloptions: StackOptions<E, R>
  Options forwarded to the constructor.
Returns any
A new Stack populated from the array.

Remarks
Time O(N), Space O(N)
- Defined in data-structures/stack/stack.ts:194

Class Stack<E, R>

Remarks

Example

Example

Example

Example

Example

Example

Example

Type Parameters

Hierarchy (view full)

Index

Constructors

Properties

Accessors

Methods

Constructors

constructor

Type Parameters

Parameters

Returns Stack<E, R>

Remarks

Properties

Protected Optional_toElementFn

Remarks

Accessors

elements

Returns E[]

Remarks

size

Returns number

Remarks

toElementFn

Returns undefined | ((rawElement: R) => E)

Remarks

Methods

Protected_createInstance

Parameters

Returns this

Remarks

Protected_createLike

Type Parameters

Parameters

Returns Stack<T, RR>

Remarks

Protected_getIterator

Returns IterableIterator<E, any, any>

Remarks

Protected_indexOfByEquals

Parameters

Returns number

Remarks

[iterator]

Parameters

Returns IterableIterator<E, any, any>

Remarks

clear

Returns void

Remarks

clone

Returns this

Remarks

delete

Parameters

Returns boolean

Remarks

deleteAt

Parameters

Returns boolean

Remarks

deleteWhere

Parameters

Parameters

Returns boolean

Returns boolean

Remarks

every

Parameters

Returns boolean

Remarks

`Protected` `Optional`_toElementFn

`Protected`_createInstance

`Protected`_createLike

`Protected`_getIterator

`Protected`_indexOfByEquals