Stack

type Stack<T> = Types.Stack<T>

public func toPure<T>(stack : Stack<T>) : PureList.List<T>

Convert a mutable stack to an immutable, purely functional list. Please note that functional lists are ordered like stacks (FIFO).

Example:

import Stack "mo:base/Stack";
import PureList "mo:base/pure/List";

persistent actor {
  let mutableStack = Stack.empty<Nat>();
  Stack.push(mutableStack, 0);
  Stack.push(mutableStack, 1);
  Stack.push(mutableStack, 2);
  let immutableList = Stack.toPure(mutableStack);
  assert(PureList.size(immutableList) == Stack.size(mutableStack));
}

Runtime: O(1). Space: O(1). where n denotes the number of elements stored in the stack.

public func fromPure<T>(list : PureList.List<T>) : Stack<T>

Convert an immutable, purely functional list to a mutable stack. Please note that functional lists are ordered like stacks (FIFO).

Example:

import Stack "mo:base/Stack";
import PureList "mo:base/pure/List";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let immutableList = PureList.fromIter<Nat>([1, 2, 3].values());
  // pure (functional) list is a FIFO data structure, similar to imperative stack.
  let mutableStack = Stack.fromPure<Nat>(immutableList);
  for (element in Stack.values(mutableStack)) {
    Debug.print(Nat.toText(element));
  }
  // prints:
  // `3`
  // `2`
  // `1`
}

Runtime: O(n). Space: O(n). where n denotes the number of elements stored in the queue.

public func empty<T>() : Stack<T>

Create a new empty mutable stack.

Example:

import Stack "mo:base/Stack";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let stack = Stack.empty<Text>();
  Debug.print(Nat.toText(Stack.size(stack))); // prints `0`
}

Runtime: O(1). Space: O(1).

public func tabulate<T>(size : Nat, generator : Nat -> T) : Stack<T>

Creates a new stack with size elements by applying the generator function to indices [0..size-1]. Elements are pushed in ascending index order.

Example:

import Stack "mo:base/Stack";
import Debug "mo:base/Debug";
import Nat "mo:base/Nat";

persistent actor {
  let stack = Stack.tabulate<Nat>(3, func(i) { 2 * i });
  for (number in Stack.values(stack)) {
    Debug.print(Nat.toText(number))
  }
  // prints:
  // `4`
  // `2`
  // `0`
}

Runtime: O(n) Space: O(n) where n denotes the number of elements stored on the stack and assuming that generator has O(1) costs.

public func singleton<T>(element : T) : Stack<T>

Creates a new stack containing a single element.

Example:

import Stack "mo:base/Stack";

persistent actor {
  let stack = Stack.singleton<Text>("motoko");
  assert (Stack.peek(stack) ==?"motoko");
}

Runtime: O(1) Space: O(1)

public func clear<T>(stack : Stack<T>)

Removes all elements from the stack.

Example:

import Stack "mo:base/Stack";

persistent actor {
  let stack = Stack.fromIter<Nat>([1, 2, 3].values());
  Stack.clear(stack);
  assert (Stack.isEmpty(stack));
}

Runtime: O(1) Space: O(1)

public func clone<T>(stack : Stack<T>) : Stack<T>

Creates a deep copy of the stack with the same elements in the same order.

Example:

import Stack "mo:base/Stack";
import Nat "mo:base/Nat";

persistent actor {
  let original = Stack.fromIter<Nat>([1, 2, 3].values());
  let copy = Stack.clone(original);
  assert (Stack.equal(copy, original, Nat.equal))
}

Runtime: O(n) Space: O(n) where n denotes the number of elements stored on the stack.

public func isEmpty<T>(stack : Stack<T>) : Bool

Returns true if the stack contains no elements.

Example:

import Stack "mo:base/Stack";

persistent actor {
  let stack = Stack.empty<Nat>();
  assert (Stack.isEmpty(stack));
}

Runtime: O(1) Space: O(1)

public func size<T>(stack : Stack<T>) : Nat

Returns the number of elements on the stack.

Example:

import Stack "mo:base/Stack";

persistent actor {
  let stack = Stack.fromIter<Nat>([1, 2, 3].values());
  assert (Stack.size(stack) == 3);
}

Runtime: O(1) Space: O(1)

public func contains<T>(
  stack : Stack<T>,
  element : T,
  equal : (T, T) -> Bool
) : Bool

Returns true if the stack contains the specified element. Uses the provided equality function to compare elements.

Example:

import Stack "mo:base/Stack";
import Nat "mo:base/Nat";

persistent actor {
  let stack = Stack.fromIter<Nat>([1, 2, 3].values());
  assert (Stack.contains(stack, 2, Nat.equal));
}

Runtime: O(n) Space: O(1) where n denotes the number of elements stored on the stack and assuming that equal has O(1) costs.

public func push<T>(stack : Stack<T>, value : T)

Pushes a new element onto the top of the stack.

Example:

import Stack "mo:base/Stack";

persistent actor {
  let stack = Stack.empty<Nat>();
  Stack.push(stack, 42);
}

Runtime: O(1) Space: O(1)

public func peek<T>(stack : Stack<T>) : ?T

Returns the top element of the stack without removing it. Returns null if the stack is empty.

Example:

import Stack "mo:base/Stack";

persistent actor {
  let stack = Stack.empty<Nat>();
  Stack.push(stack, 1);
  Stack.push(stack, 2);
  Stack.push(stack, 3);
  assert (Stack.peek(stack) == ?3);
}

Runtime: O(1) Space: O(1)

public func pop<T>(stack : Stack<T>) : ?T

Removes and returns the top element of the stack. Returns null if the stack is empty.

Example:

import Stack "mo:base/Stack";

persistent actor {
  let stack = Stack.empty<Nat>();
  Stack.push(stack, 1);
  Stack.push(stack, 2);
  Stack.push(stack, 3);
  assert (Stack.pop(stack) == ?3);
  assert (Stack.pop(stack) == ?2);
  assert (Stack.pop(stack) == ?1);
  assert (Stack.pop(stack) == null);
}

Runtime: O(1) Space: O(1)

public func get<T>(stack : Stack<T>, position : Nat) : ?T

Returns the element at the specified position from the top of the stack. Returns null if position is out of bounds. Position 0 is the top of the stack.

Example:

import Stack "mo:base/Stack";

persistent actor {
  let stack = Stack.empty<Nat>();
  Stack.push(stack, 1);
  Stack.push(stack, 2);
  Stack.push(stack, 3);
  assert (Stack.get(stack, 0) == ?3);
  assert (Stack.get(stack, 1) == ?2);
  assert (Stack.get(stack, 2) == ?1);
  assert (Stack.get(stack, 3) == null);
}

Runtime: O(n) Space: O(1) where n denotes the number of elements stored on the stack.

public func reverse<T>(stack : Stack<T>)

Reverses the order of elements in the stack.

Example:

import Stack "mo:base/Stack";

persistent actor {
  let stack = Stack.empty<Nat>();
  Stack.push(stack, 1);
  Stack.push(stack, 2);
  Stack.push(stack, 3);
  Stack.reverse(stack);
  assert (Stack.pop(stack) == ?1);
  assert (Stack.pop(stack) == ?2);
  assert (Stack.pop(stack) == ?3);
  assert (Stack.pop(stack) == null);
}

Runtime: O(n) Space: O(n) where n denotes the number of elements stored on the stack.

public func values<T>(stack : Stack<T>) : Types.Iter<T>

Returns an iterator over the elements in the stack, from top to bottom.

Example:

import Stack "mo:base/Stack";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let stack = Stack.empty<Nat>();
  Stack.push(stack, 1);
  Stack.push(stack, 2);
  Stack.push(stack, 3);
  for (element in Stack.values(stack)) {
    Debug.print(Nat.toText(element));
  };
  // prints:
  // `3`
  // `2`
  // `1`
}

Runtime: O(1) for iterator creation, O(n) for full traversal Space: O(1) where n denotes the number of elements stored on the stack.

public func all<T>(stack : Stack<T>, predicate : T -> Bool) : Bool

Returns true if all elements in the stack satisfy the predicate.

Example:

import Stack "mo:base/Stack";

persistent actor {
  let stack = Stack.fromIter<Nat>([2, 4, 6].values());
  assert (Stack.all<Nat>(stack, func(n) { n % 2 == 0 }));
}

Runtime: O(n) Space: O(1) where n denotes the number of elements stored on the stack and assuming that predicate has O(1) costs.

public func any<T>(stack : Stack<T>, predicate : T -> Bool) : Bool

Returns true if any element in the stack satisfies the predicate.

Example:

import Stack "mo:base/Stack";

persistent actor {
  let stack = Stack.fromIter<Nat>([1, 2, 3].values());
  assert (Stack.any<Nat>(stack, func(n) { n == 2 }));
}

Runtime: O(n) Space: O(1) where n denotes the number of elements stored on the stack and assuming predicate has O(1) costs.

public func forEach<T>(stack : Stack<T>, operation : T -> ())

Applies the operation to each element in the stack, from top to bottom.

Example:

import Stack "mo:base/Stack";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let stack = Stack.empty<Nat>();
  Stack.push(stack, 1);
  Stack.push(stack, 2);
  Stack.push(stack, 3);
  Stack.forEach<Nat>(stack, func(n) {
    Debug.print(Nat.toText(n))
  });
  // prints:
  // `3`
  // `2`
  // `1`
}

Runtime: O(n) Space: O(1) where n denotes the number of elements stored on the stack and assuming that operation has O(1) costs.

public func map<T, U>(stack : Stack<T>, project : T -> U) : Stack<U>

Creates a new stack by applying the projection function to each element. Maintains the original order of elements.

Example:

import Stack "mo:base/Stack";

persistent actor {
  let stack = Stack.empty<Nat>();
  Stack.push(stack, 1);
  Stack.push(stack, 2);
  Stack.push(stack, 3);
  let doubled = Stack.map<Nat, Nat>(stack, func(n) { 2 * n });
  assert (Stack.get(doubled, 0) == ?6);
  assert (Stack.get(doubled, 1) == ?4);
  assert (Stack.get(doubled, 2) == ?2);
  assert (Stack.get(doubled, 3) == null);
}

Runtime: O(n) Space: O(n) where n denotes the number of elements stored on the stack and assuming that project has O(1) costs.

public func filter<T>(stack : Stack<T>, predicate : T -> Bool) : Stack<T>

Creates a new stack containing only elements that satisfy the predicate. Maintains the relative order of elements.

Example:

import Stack "mo:base/Stack";

persistent actor {
  let stack = Stack.empty<Nat>();
  Stack.push(stack, 1);
  Stack.push(stack, 2);
  Stack.push(stack, 3);
  Stack.push(stack, 4);
  let evens = Stack.filter<Nat>(stack, func(n) { n % 2 == 0 });
  assert(Stack.pop(evens) == ?4);
  assert(Stack.pop(evens) == ?2);
  assert(Stack.pop(evens) == null);
}

Runtime: O(n) Space: O(n) where n denotes the number of elements stored on the stack and assuming predicate has O(1) costs.

public func filterMap<T, U>(stack : Stack<T>, project : T -> ?U) : Stack<U>

Creates a new stack by applying the projection function to each element and keeping only the successful results (where project returns ?value). Maintains the relative order of elements.

Example:

import Stack "mo:base/Stack";

persistent actor {
  let stack = Stack.empty<Nat>();
  Stack.push(stack, 1);
  Stack.push(stack, 2);
  Stack.push(stack, 3);
  Stack.push(stack, 4);
  let evenDoubled = Stack.filterMap<Nat, Nat>(stack, func(n) {
    if (n % 2 == 0) {
      ?(n * 2)
    } else {
      null
    }
  });
  assert(Stack.pop(evenDoubled) == ?8);
  assert(Stack.pop(evenDoubled) == ?4);
  assert(Stack.pop(evenDoubled) == null);
}

Runtime: O(n) Space: O(n) where n denotes the number of elements stored on the stack and assuming that project has O(1) costs.

public func equal<T>(
  stack1 : Stack<T>,
  stack2 : Stack<T>,
  equal : (T, T) -> Bool
) : Bool

Compares two stacks for equality using the provided equality function.

Example:

import Stack "mo:base/Stack";
import Nat "mo:base/Nat";

persistent actor {
  let stack1 = Stack.fromIter<Nat>([1, 2, 3].values());
  let stack2 = Stack.fromIter<Nat>([1, 2, 3].values());
  assert (Stack.equal(stack1, stack2, Nat.equal));
}

Runtime: O(n) Space: O(1) where n denotes the number of elements stored on the stack and assuming that equal has O(1) costs.

public func fromIter<T>(iter : Types.Iter<T>) : Stack<T>

Creates a new stack from an iterator. Elements are pushed in iteration order.

Example:

import Stack "mo:base/Stack";

persistent actor {
  let stack = Stack.fromIter<Nat>([1, 2, 3].values());
  assert(Stack.pop(stack) == ?3);
  assert(Stack.pop(stack) == ?2);
  assert(Stack.pop(stack) == ?1);
  assert(Stack.pop(stack) == null);
}

Runtime: O(n) Space: O(n) where n denotes the number of iterated elements.

public func toText<T>(stack : Stack<T>, format : T -> Text) : Text

Converts the stack to its string representation using the provided element formatting function.

Example:

import Stack "mo:base/Stack";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let stack = Stack.empty<Nat>();
  Stack.push(stack, 1);
  Stack.push(stack, 2);
  Stack.push(stack, 3);
  let text = Stack.toText(stack, Nat.toText);
  Debug.print(text);
  // prints `[3, 2, 1]`
}

Runtime: O(n) Space: O(n) where n denotes the number of elements stored on the stack and assuming that format has O(1) costs.

public func compare<T>(
  stack1 : Stack<T>,
  stack2 : Stack<T>,
  compare : (T, T) -> Order.Order
) : Order.Order

Compares two stacks lexicographically using the provided comparison function.

Example:

import Stack "mo:base/Stack";
import Nat "mo:base/Nat";

persistent actor {
  let stack1 = Stack.fromIter<Nat>([1, 2].values());
  let stack2 = Stack.fromIter<Nat>([1, 2, 3].values());
  assert (Stack.compare(stack1, stack2, Nat.compare) == #less);
}

Runtime: O(n) Space: O(1) where n denotes the number of elements stored on the stack and assuming that compare has O(1) costs.