Skip to main content

core/Queue

A mutable double-ended queue of elements. The queue has two ends, front and back. Elements can be added and removed at the two ends.

This can be used for different use cases, such as:

  • Queue (FIFO) by using pushBack() and popFront()
  • Stack (LIFO) by using pushFront() and popFront().

Example:

import Queue "mo:core/Queue";

persistent actor {
  let orders = Queue.empty<Text>();
  Queue.pushBack(orders, "Motoko");
  Queue.pushBack(orders, "Mops");
  Queue.pushBack(orders, "IC");
  assert Queue.popFront(orders) == ?"Motoko";
  assert Queue.popFront(orders) == ?"Mops";
  assert Queue.popFront(orders) == ?"IC";
  assert Queue.popFront(orders) == null;
}

The internal implementation is a doubly-linked list.

Performance:

  • Runtime: O(1) for push, pop, and peek operations.
  • Space: O(n). n denotes the number of elements stored in the queue.

Type Queue​

type Queue<T> = Types.Queue.Queue<T>

Function toPure​

func toPure<T>(queue : Queue<T>) : PureQueue.Queue<T>

Converts a mutable queue to an immutable, purely functional queue.

Example:

import Queue "mo:core/Queue";

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3].values());
  let pureQueue = Queue.toPure<Nat>(queue);
}

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

Function fromPure​

func fromPure<T>(pureQueue : PureQueue.Queue<T>) : Queue<T>

Converts an immutable, purely functional queue to a mutable queue.

Example:

import Queue "mo:core/Queue";
import PureQueue "mo:core/pure/Queue";

persistent actor {
  let pureQueue = PureQueue.fromIter<Nat>([1, 2, 3].values());
  let queue = Queue.fromPure<Nat>(pureQueue);
}

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

Function empty​

func empty<T>() : Queue<T>

Create a new empty mutable double-ended queue.

Example:

import Queue "mo:core/Queue";

persistent actor {
  let queue = Queue.empty<Text>();
  assert Queue.size(queue) == 0;
}

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

Function singleton​

func singleton<T>(element : T) : Queue<T>

Creates a new queue with a single element.

Example:

import Queue "mo:core/Queue";

persistent actor {
  let queue = Queue.singleton<Nat>(123);
  assert Queue.size(queue) == 1;
}

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

Function clear​

func clear<T>(queue : Queue<T>)

Removes all elements from the queue.

Example:

import Queue "mo:core/Queue";

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

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

Function clone​

func clone<T>(queue : Queue<T>) : Queue<T>

Creates a deep copy of the queue.

Example:

import Queue "mo:core/Queue";

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

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

Function size​

func size<T>(queue : Queue<T>) : Nat

Returns the number of elements in the queue.

Example:

import Queue "mo:core/Queue";

persistent actor {
  let queue = Queue.fromIter<Text>(["A", "B", "C"].values());
  assert Queue.size(queue) == 3;
}

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

Function isEmpty​

func isEmpty<T>(queue : Queue<T>) : Bool

Returns true if the queue contains no elements.

Example:

import Queue "mo:core/Queue";

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

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

Function contains​

func contains<T>(queue : Queue<T>, equal : (T, T) -> Bool, element : T) : Bool

Checks if an element exists in the queue using the provided equality function.

Example:

import Queue "mo:core/Queue";
import Nat "mo:core/Nat";

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

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

Function peekFront​

func peekFront<T>(queue : Queue<T>) : ?T

Returns the first element in the queue without removing it. Returns null if the queue is empty.

Example:

import Queue "mo:core/Queue";

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3].values());
  assert Queue.peekFront(queue) == ?1;
}

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

Function peekBack​

func peekBack<T>(queue : Queue<T>) : ?T

Returns the last element in the queue without removing it. Returns null if the queue is empty.

Example:

import Queue "mo:core/Queue";

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3].values());
  assert Queue.peekBack(queue) == ?3;
}

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

Function pushFront​

func pushFront<T>(queue : Queue<T>, element : T)

Adds an element to the front of the queue.

Example:

import Queue "mo:core/Queue";

persistent actor {
  let queue = Queue.empty<Nat>();
  Queue.pushFront(queue, 1);
  assert Queue.peekFront(queue) == ?1;
}

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

Function pushBack​

func pushBack<T>(queue : Queue<T>, element : T)

Adds an element to the back of the queue.

Example:

import Queue "mo:core/Queue";

persistent actor {
  let queue = Queue.empty<Nat>();
  Queue.pushBack(queue, 1);
  assert Queue.peekBack(queue) == ?1;
}

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

Function popFront​

func popFront<T>(queue : Queue<T>) : ?T

Removes and returns the first element in the queue. Returns null if the queue is empty.

Example:

import Queue "mo:core/Queue";

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3].values());
  assert Queue.popFront(queue) == ?1;
  assert Queue.size(queue) == 2;
}

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

Function popBack​

func popBack<T>(queue : Queue<T>) : ?T

Removes and returns the last element in the queue. Returns null if the queue is empty.

Example:

import Queue "mo:core/Queue";

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3].values());
  assert Queue.popBack(queue) == ?3;
  assert Queue.size(queue) == 2;
}

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

Function fromIter​

func fromIter<T>(iter : Iter.Iter<T>) : Queue<T>

Creates a new queue from an iterator.

Example:

import Queue "mo:core/Queue";

persistent actor {
  let queue = Queue.fromIter<Text>(["A", "B", "C"].values());
  assert Queue.size(queue) == 3;
}

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

Function values​

func values<T>(queue : Queue<T>) : Iter.Iter<T>

Returns an iterator over the elements in the queue. Iterates from front to back.

Example:

import Queue "mo:core/Queue";
persistent actor {
  let queue = Queue.fromIter<Text>(["A", "B", "C"].values());
  transient let iter = Queue.values(queue);
  assert iter.next() == ?"A";
  assert iter.next() == ?"B";
  assert iter.next() == ?"C";
  assert iter.next() == null;
}

Runtime: O(1) for iterator creation, O(n) for full iteration Space: O(1)

Function all​

func all<T>(queue : Queue<T>, predicate : T -> Bool) : Bool

Tests whether all elements in the queue satisfy the given predicate.

Example:

import Queue "mo:core/Queue";

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

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

Function any​

func any<T>(queue : Queue<T>, predicate : T -> Bool) : Bool

Tests whether any element in the queue satisfies the given predicate.

Example:

import Queue "mo:core/Queue";

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

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

Function forEach​

func forEach<T>(queue : Queue<T>, operation : T -> ())

Applies the given operation to all elements in the queue.

Example:

import Queue "mo:core/Queue";

persistent actor {
  var sum = 0;
  let queue = Queue.fromIter<Nat>([1, 2, 3].values());
  Queue.forEach<Nat>(queue, func(x) { sum += x });
  assert sum == 6;
}

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

Function map​

func map<T, U>(queue : Queue<T>, project : T -> U) : Queue<U>

Creates a new queue by applying the given function to all elements.

Example:

import Queue "mo:core/Queue";

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3].values());
  let doubled = Queue.map<Nat, Nat>(queue, func(x) { x * 2 });
  assert Queue.peekFront(doubled) == ?2;
}

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

Function filter​

func filter<T>(queue : Queue<T>, criterion : T -> Bool) : Queue<T>

Creates a new queue containing only elements that satisfy the given predicate.

Example:

import Queue "mo:core/Queue";

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3, 4].values());
  let evens = Queue.filter<Nat>(queue, func(x) { x % 2 == 0 });
  assert Queue.size(evens) == 2;
}

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

Function filterMap​

func filterMap<T, U>(queue : Queue<T>, project : T -> ?U) : Queue<U>

Creates a new queue by applying the given function to all elements and keeping only the non-null results.

Example:

import Queue "mo:core/Queue";

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3, 4].values());
  let evenDoubled = Queue.filterMap<Nat, Nat>(
    queue,
    func(x) {
      if (x % 2 == 0) { ?(x * 2) } else  { null }
    }
  );
  assert Queue.size(evenDoubled) == 2;
}

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

Function equal​

func equal<T>(queue1 : Queue<T>, queue2 : Queue<T>, equal : (T, T) -> Bool) : Bool

Compares two queues for equality using the provided equality function.

Example:

import Queue "mo:core/Queue";
import Nat "mo:core/Nat";

persistent actor {
  let queue1 = Queue.fromIter<Nat>([1, 2, 3].values());
  let queue2 = Queue.fromIter<Nat>([1, 2, 3].values());
  assert Queue.equal(queue1, queue2, Nat.equal);
}

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

Function toText​

func toText<T>(queue : Queue<T>, format : T -> Text) : Text

Converts a queue to its string representation using the provided element formatter.

Example:

import Queue "mo:core/Queue";
import Nat "mo:core/Nat";

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3].values());
  assert Queue.toText(queue, Nat.toText) == "Queue[1, 2, 3]";
}

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

Function compare​

func compare<T>(queue1 : Queue<T>, queue2 : Queue<T>, compareItem : (T, T) -> Order.Order) : Order.Order

Compares two queues using the provided comparison function. Returns #less, #equal, or #greater.

Example:

import Queue "mo:core/Queue";
import Nat "mo:core/Nat";

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

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