Skip to main content

/

Docs

Nightly

v24.6

Log in

Mojo struct

Deque

struct Deque[ElementType: CollectionElement]

Implements a double-ended queue.

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

Parameters​

  • ​ElementType (CollectionElement): The type of the elements in the deque. Must implement the trait CollectionElement.

Aliases​

  • default_capacity = 64: The default capacity of the deque: must be the power of 2.

Implemented traits​

AnyType, Boolable, ExplicitlyCopyable, Movable, Sized, UnknownDestructibility

Methods​

__init__​

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

Constructs a deque.

Args:

  • ​elements (Optional[List[ElementType]]): 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, owned *values: ElementType)

Constructs a deque from the given values.

Args:

  • ​*values (ElementType): The values to populate the deque with.

__init__(out self, *, owned elements: VariadicListMem[ElementType, origin])

Constructs a deque from the given values.

Args:

  • ​elements (VariadicListMem[ElementType, origin]): The values to populate the deque with.

__init__(out self, other: Self)

Creates a deepcopy of the given deque.

Args:

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

__moveinit__​

__moveinit__(out self, owned existing: Self)

Moves data of an existing deque into a new one.

Args:

  • ​existing (Self): The existing deque.

__del__​

__del__(owned 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:

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

__getitem__​

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

Gets the deque element at the given index.

Args:

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

Returns:

A reference to the element at the given index.

__eq__​

__eq__[EqualityElementType: EqualityComparableCollectionElement, //](self: Deque[EqualityElementType], other: Deque[EqualityElementType]) -> Bool

Checks if two deques are equal.

Parameters:

  • ​EqualityElementType (EqualityComparableCollectionElement): The type of the elements in the deque. Must implement the trait EqualityComparableCollectionElement.

Args:

  • ​other (Deque[EqualityElementType]): The deque to compare with.

Returns:

True if the deques are equal, False otherwise.

__ne__​

__ne__[EqualityElementType: EqualityComparableCollectionElement, //](self: Deque[EqualityElementType], other: Deque[EqualityElementType]) -> Bool

Checks if two deques are not equal.

Parameters:

  • ​EqualityElementType (EqualityComparableCollectionElement): The type of the elements in the deque. Must implement the trait EqualityComparableCollectionElement.

Args:

  • ​other (Deque[EqualityElementType]): The deque to compare with.

Returns:

True if the deques are not equal, False otherwise.

__contains__​

__contains__[EqualityElementType: EqualityComparableCollectionElement, //](self: Deque[EqualityElementType], value: EqualityElementType) -> Bool

Verify if a given value is present in the deque.

Parameters:

  • ​EqualityElementType (EqualityComparableCollectionElement): The type of the elements in the deque. Must implement the trait EqualityComparableCollectionElement.

Args:

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

Returns:

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:

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:

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.

__iter__​

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

Iterates over elements of the deque, returning the references.

Returns:

An iterator of the references to the deque elements.

__reversed__​

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

Iterate backwards over the deque, returning the references.

Returns:

A reversed iterator of the references to the deque elements.

__len__​

__len__(self) -> Int

Gets the number of elements in the deque.

Returns:

The number of elements in the deque.

write_to​

write_to[RepresentableElementType: RepresentableCollectionElement, WriterType: Writer, //](self: Deque[RepresentableElementType], mut writer: WriterType)

Writes my_deque.__str__() to a Writer.

Parameters:

  • ​RepresentableElementType (RepresentableCollectionElement): The type of the Deque elements. Must implement the trait RepresentableCollectionElement.
  • ​WriterType (Writer): A type conforming to the Writable trait.

Args:

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

__str__​

__str__[RepresentableElementType: RepresentableCollectionElement, //](self: Deque[RepresentableElementType]) -> String

Returns a string representation of a Deque.

Note that since we can't condition methods on a trait yet, the way to call this method is a bit special. Here is an example below:

my_deque = Deque[Int](1, 2, 3)
print(my_deque.__str__())
my_deque = Deque[Int](1, 2, 3)
print(my_deque.__str__())

When the compiler supports conditional methods, then a simple str(my_deque) will be enough.

The elements' type must implement the __repr__() method for this to work.

Parameters:

  • ​RepresentableElementType (RepresentableCollectionElement): The type of the elements in the deque. Must implement the trait RepresentableCollectionElement.

Returns:

A string representation of the deque.

__repr__​

__repr__[RepresentableElementType: RepresentableCollectionElement, //](self: Deque[RepresentableElementType]) -> String

Returns a string representation of a Deque.

Note that since we can't condition methods on a trait yet, the way to call this method is a bit special. Here is an example below:

my_deque = Deque[Int](1, 2, 3)
print(my_deque.__repr__())
my_deque = Deque[Int](1, 2, 3)
print(my_deque.__repr__())

When the compiler supports conditional methods, then a simple repr(my_deque) will be enough.

The elements' type must implement the __repr__() for this to work.

Parameters:

  • ​RepresentableElementType (RepresentableCollectionElement): The type of the elements in the deque. Must implement the trait RepresentableCollectionElement.

Returns:

A string representation of the deque.

append​

append(mut self, owned value: ElementType)

Appends a value to the right side of the deque.

Args:

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

appendleft​

appendleft(mut self, owned 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[EqualityElementType: EqualityComparableCollectionElement, //](self: Deque[EqualityElementType], value: EqualityElementType) -> Int

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

Parameters:

  • ​EqualityElementType (EqualityComparableCollectionElement): The type of the elements in the deque. Must implement the trait EqualityComparableCollectionElement.

Args:

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

Returns:

The number of occurrences of the value in the deque.

extend​

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

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

Args:

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

extendleft​

extendleft(mut self, owned 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[ElementType]): List whose elements will be added at the left side of the deque.

index​

index[EqualityElementType: EqualityComparableCollectionElement, //](self: Deque[EqualityElementType], value: EqualityElementType, start: Int = 0, stop: Optional[Int] = Optional(None)) -> Int

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

Parameters:

  • ​EqualityElementType (EqualityComparableCollectionElement): The type of the elements in the deque. Must implement the EqualityComparableCollectionElement trait.

Args:

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

Returns:

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, owned 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[EqualityElementType: EqualityComparableCollectionElement, //](mut self: Deque[EqualityElementType], value: EqualityElementType)

Removes the first occurrence of the value.

Parameters:

  • ​EqualityElementType (EqualityComparableCollectionElement): The type of the elements in the deque. Must implement the EqualityComparableCollectionElement trait.

Args:

  • ​value (EqualityElementType): 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:

The 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:

The 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:

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:

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).