Skip to main content

/

DocsCode

Mojo struct

Deque

struct Deque[ElementType: Copyable & ImplicitlyDestructible]

Implements a double-ended queue.

It supports pushing and popping from both ends in O(1) time resizing the underlying storage as needed.

Parameters​

Implemented traits​

AnyType, Boolable, Copyable, Equatable, Hashable, ImplicitlyDestructible, Iterable, IterableOwned, Movable, Sized, Writable

comptime members​

default_capacity​

comptime default_capacity = 64

The default capacity of the deque: must be the power of 2.

IteratorOwnedType​

comptime IteratorOwnedType = _DequeIterOwned[ElementType]

The owned iterator type for this deque.

IteratorType​

comptime IteratorType[iterable_mut: Bool, //, iterable_origin: Origin[mut=iterable_mut]] = _DequeIter[ElementType, iterable_origin]

The iterator type for this deque.

Parameters​

  • ​iterable_mut (Bool): Whether the iterable is mutable.
  • ​iterable_origin (Origin): The origin of the iterable.

Methods​

__init__​

__init__(out self, *, var elements: Optional[List[ElementType]] = None, capacity: Int = Deque[ElementType].default_capacity, min_capacity: Int = Deque[ElementType].default_capacity, maxlen: Int = -1, shrink: Bool = True)

Constructs a deque.

Args:

  • ​elements (Optional): The optional list of initial deque elements.
  • ​capacity (Int): The initial capacity of the deque.
  • ​min_capacity (Int): The minimum allowed capacity of the deque when shrinking.
  • ​maxlen (Int): The maximum allowed capacity of the deque when growing.
  • ​shrink (Bool): Should storage be de-allocated when not needed.

__init__(out self, var *values: ElementType, *, __list_literal__: Tuple[] = Tuple())

Constructs a deque from the given values.

Args:

  • ​*values (ElementType): The values to populate the deque with.
  • ​list_literal (Tuple): Tell Mojo to use this method for list literals.

__init__(out self, *, var elements: VariadicList[ElementType, elements.is_owned])

Constructs a deque from the given values.

Args:

  • ​elements (VariadicList): The values to populate the deque with.

__init__(out self, *, copy: Self)

Creates a deep copy of the given deque.

Args:

  • ​copy (Self): The deque to copy.

__del__​

__del__(deinit self)

Destroys all elements in the deque and free its memory.

__bool__​

__bool__(self) -> Bool

Checks whether the deque has any elements or not.

Returns:

Bool: False if the deque is empty, True if there is at least one element.

__getitem__​

__getitem__(ref self, idx: Int) -> ref[self_is_mut] ElementType

Gets the deque element at the given index.

Args:

  • ​idx (Int): The index of the element.

Returns:

ref: A reference to the element at the given index.

__eq__​

__eq__(self, other: Self) -> Bool where conforms_to(ElementType, AnyType & ImplicitlyDestructible & Equatable)

Checks if two deques are equal.

Args:

  • ​other (Self): The deque to compare with.

Returns:

Bool: True if the deques are equal, False otherwise.

__contains__​

__contains__(self, value: ElementType) -> Bool where conforms_to(ElementType, AnyType & ImplicitlyDestructible & Equatable)

Verify if a given value is present in the deque.

Args:

  • ​value (ElementType): The value to find.

Returns:

Bool: True if the value is contained in the deque, False otherwise.

__add__​

__add__(self, other: Self) -> Self

Concatenates self with other and returns the result as a new deque.

Args:

  • ​other (Self): Deque whose elements will be appended to the elements of self.

Returns:

Self: The newly created deque with the properties of self.

__mul__​

__mul__(self, n: Int) -> Self

Concatenates n deques of self and returns a new deque.

Args:

  • ​n (Int): The multiplier number.

Returns:

Self: The new deque.

__iadd__​

__iadd__(mut self, other: Self)

Appends the elements of other deque into self.

Args:

  • ​other (Self): Deque whose elements will be appended to self.

__imul__​

__imul__(mut self, n: Int)

Concatenates self n times in place.

Args:

  • ​n (Int): The multiplier number.

__hash__​

__hash__[H: Hasher](self, mut hasher: H) where conforms_to(ElementType, AnyType & Hashable)

Updates hasher with the hash of each element in the deque.

Parameters:

  • ​H (Hasher): The hasher type.

Args:

  • ​hasher (H): The hasher instance.

__iter__​

__iter__(var self) -> Deque[ElementType].IteratorOwnedType

Consume the deque and return an iterator over its elements.

Returns:

Deque: An iterator that owns the deque's elements.

__iter__(ref self) -> _DequeIter[ElementType, origin_of(self)]

Iterates over elements of the deque, returning the references.

Returns:

_DequeIter: An iterator of the references to the deque elements.

__reversed__​

__reversed__(ref self) -> _DequeIter[ElementType, origin_of(self), False]

Iterate backwards over the deque, returning the references.

Returns:

_DequeIter: A reversed iterator of the references to the deque elements.

__len__​

__len__(self) -> Int

Gets the number of elements in the deque.

Returns:

Int: The number of elements in the deque.

write_to​

write_to(self, mut writer: T) where conforms_to(ElementType, AnyType & ImplicitlyDestructible & Writable)

Writes my_deque.__str__() to a Writer.

Args:

  • ​writer (T): The object to write to.

write_repr_to​

write_repr_to(self, mut writer: T) where conforms_to(ElementType, AnyType & ImplicitlyDestructible & Writable)

Writes the repr representation of this deque to a Writer.

Args:

  • ​writer (T): The object to write to.

append​

append(mut self, var value: ElementType)

Appends a value to the right side of the deque.

Args:

  • ​value (ElementType): The value to append.

appendleft​

appendleft(mut self, var value: ElementType)

Appends a value to the left side of the deque.

Args:

  • ​value (ElementType): The value to append.

clear​

clear(mut self)

Removes all elements from the deque leaving it with length 0.

Resets the underlying storage capacity to _min_capacity.

count​

count(self, value: ElementType) -> Int where conforms_to(ElementType, AnyType & ImplicitlyDestructible & Equatable)

Counts the number of occurrences of a value in the deque.

Args:

  • ​value (ElementType): The value to count.

Returns:

Int: The number of occurrences of the value in the deque.

extend​

extend(mut self, var values: List[ElementType])

Extends the right side of the deque by consuming elements of the list argument.

Args:

  • ​values (List): List whose elements will be added at the right side of the deque.

extendleft​

extendleft(mut self, var values: List[ElementType])

Extends the left side of the deque by consuming elements from the list argument.

Acts as series of left appends resulting in reversed order of elements in the list argument.

Args:

  • ​values (List): List whose elements will be added at the left side of the deque.

index​

index(self, value: ElementType, start: Int = 0, stop: Optional[Int] = None) -> Int where conforms_to(ElementType, AnyType & ImplicitlyDestructible & Equatable)

Returns the index of the first occurrence of a value in a deque restricted by the range given the start and stop bounds.

Args:

  • ​value (ElementType): The value to search for.
  • ​start (Int): The starting index of the search, treated as a slice index (defaults to 0).
  • ​stop (Optional): The ending index of the search, treated as a slice index (defaults to None, which means the end of the deque).

Returns:

Int: The index of the first occurrence of the value in the deque.

Raises:

ValueError: If the value is not found in the deque.

insert​

insert(mut self, idx: Int, var value: ElementType)

Inserts the value into the deque at position idx.

Args:

  • ​idx (Int): The position to insert the value into.
  • ​value (ElementType): The value to insert.

Raises:

IndexError: If deque is already at its maximum size.

remove​

remove(mut self, value: ElementType) where conforms_to(ElementType, AnyType & ImplicitlyDestructible & Equatable)

Removes the first occurrence of the value.

Args:

  • ​value (ElementType): The value to remove.

Raises:

ValueError: If the value is not found in the deque.

peek​

peek(self) -> ElementType

Inspect the last (rightmost) element of the deque without removing it.

Returns:

ElementType: The last (rightmost) element of the deque.

Raises:

IndexError: If the deque is empty.

peekleft​

peekleft(self) -> ElementType

Inspect the first (leftmost) element of the deque without removing it.

Returns:

ElementType: The first (leftmost) element of the deque.

Raises:

IndexError: If the deque is empty.

pop​

pop(mut self) -> ElementType

Removes and returns the element from the right side of the deque.

Returns:

ElementType: The popped value.

Raises:

IndexError: If the deque is empty.

popleft​

popleft(mut self) -> ElementType

Removes and returns the element from the left side of the deque.

Returns:

ElementType: The popped value.

Raises:

IndexError: If the deque is empty.

reverse​

reverse(mut self)

Reverses the elements of the deque in-place.

rotate​

rotate(mut self, n: Int = 1)

Rotates the deque by n steps.

If n is positive, rotates to the right. If n is negative, rotates to the left.

Args:

  • ​n (Int): Number of steps to rotate the deque (defaults to 1).

View source

View source

Was this page helpful?

Models

Cookbook

Puzzles

Blog

Community

Contact