data_structures.queues.double_ended_queue

Implementation of double ended queue.

Attributes

dq

Classes

Deque

Deque data structure.

Module Contents

class data_structures.queues.double_ended_queue.Deque(iterable: collections.abc.Iterable[Any] | None = None)

Deque data structure. Operations ———- append(val: Any) -> None appendleft(val: Any) -> None extend(iterable: Iterable) -> None extendleft(iterable: Iterable) -> None pop() -> Any popleft() -> Any Observers ——— is_empty() -> bool Attributes ———- _front: _Node

front of the deque a.k.a. the first element

_back: _Node

back of the element a.k.a. the last element

_len: int

the number of nodes

class _Iterator(cur: Deque | None)

Helper class for iteration. Will be used to implement iteration. Attributes ———- _cur: _Node

the current node of the iteration.

__iter__() → Deque

>>> our_deque = Deque([1, 2, 3])
>>> iterator = iter(our_deque)

__next__() → Any

>>> our_deque = Deque([1, 2, 3])
>>> iterator = iter(our_deque)
>>> next(iterator)
1
>>> next(iterator)
2
>>> next(iterator)
3

__slots__ = ('_cur',)

_cur

class _Node

Representation of a node. Contains a value and a pointer to the next node as well as to the previous one.

next_node: Deque | None = None

prev_node: Deque | None = None

val: Any = None

__eq__(other: object) → bool

Implements “==” operator. Returns if self is equal to other. Time complexity: O(n) >>> our_deque_1 = Deque([1, 2, 3]) >>> our_deque_2 = Deque([1, 2, 3]) >>> our_deque_1 == our_deque_2 True >>> our_deque_3 = Deque([1, 2]) >>> our_deque_1 == our_deque_3 False >>> from collections import deque >>> deque_collections_1 = deque([1, 2, 3]) >>> deque_collections_2 = deque([1, 2, 3]) >>> deque_collections_1 == deque_collections_2 True >>> deque_collections_3 = deque([1, 2]) >>> deque_collections_1 == deque_collections_3 False >>> (our_deque_1 == our_deque_2) == (deque_collections_1 == deque_collections_2) True >>> (our_deque_1 == our_deque_3) == (deque_collections_1 == deque_collections_3) True

__iter__() → Deque

Implements iteration. Time complexity: O(1) >>> our_deque = Deque([1, 2, 3]) >>> for v in our_deque: … print(v) 1 2 3 >>> from collections import deque >>> deque_collections = deque([1, 2, 3]) >>> for v in deque_collections: … print(v) 1 2 3

__len__() → int

Implements len() function. Returns the length of the deque. Time complexity: O(1) >>> our_deque = Deque([1, 2, 3]) >>> len(our_deque) 3 >>> our_empty_deque = Deque() >>> len(our_empty_deque) 0 >>> from collections import deque >>> deque_collections = deque([1, 2, 3]) >>> len(deque_collections) 3 >>> empty_deque_collections = deque() >>> len(empty_deque_collections) 0 >>> len(our_empty_deque) == len(empty_deque_collections) True

__repr__() → str

Implements representation of the deque. Represents it as a list, with its values between ‘[’ and ‘]’. Time complexity: O(n) >>> our_deque = Deque([1, 2, 3]) >>> our_deque [1, 2, 3]

append(val: Any) → None

Adds val to the end of the deque. Time complexity: O(1) >>> our_deque_1 = Deque([1, 2, 3]) >>> our_deque_1.append(4) >>> our_deque_1 [1, 2, 3, 4] >>> our_deque_2 = Deque(‘ab’) >>> our_deque_2.append(‘c’) >>> our_deque_2 [‘a’, ‘b’, ‘c’] >>> from collections import deque >>> deque_collections_1 = deque([1, 2, 3]) >>> deque_collections_1.append(4) >>> deque_collections_1 deque([1, 2, 3, 4]) >>> deque_collections_2 = deque(‘ab’) >>> deque_collections_2.append(‘c’) >>> deque_collections_2 deque([‘a’, ‘b’, ‘c’]) >>> list(our_deque_1) == list(deque_collections_1) True >>> list(our_deque_2) == list(deque_collections_2) True

appendleft(val: Any) → None

Adds val to the beginning of the deque. Time complexity: O(1) >>> our_deque_1 = Deque([2, 3]) >>> our_deque_1.appendleft(1) >>> our_deque_1 [1, 2, 3] >>> our_deque_2 = Deque(‘bc’) >>> our_deque_2.appendleft(‘a’) >>> our_deque_2 [‘a’, ‘b’, ‘c’] >>> from collections import deque >>> deque_collections_1 = deque([2, 3]) >>> deque_collections_1.appendleft(1) >>> deque_collections_1 deque([1, 2, 3]) >>> deque_collections_2 = deque(‘bc’) >>> deque_collections_2.appendleft(‘a’) >>> deque_collections_2 deque([‘a’, ‘b’, ‘c’]) >>> list(our_deque_1) == list(deque_collections_1) True >>> list(our_deque_2) == list(deque_collections_2) True

extend(iterable: collections.abc.Iterable[Any]) → None

Appends every value of iterable to the end of the deque. Time complexity: O(n) >>> our_deque_1 = Deque([1, 2, 3]) >>> our_deque_1.extend([4, 5]) >>> our_deque_1 [1, 2, 3, 4, 5] >>> our_deque_2 = Deque(‘ab’) >>> our_deque_2.extend(‘cd’) >>> our_deque_2 [‘a’, ‘b’, ‘c’, ‘d’] >>> from collections import deque >>> deque_collections_1 = deque([1, 2, 3]) >>> deque_collections_1.extend([4, 5]) >>> deque_collections_1 deque([1, 2, 3, 4, 5]) >>> deque_collections_2 = deque(‘ab’) >>> deque_collections_2.extend(‘cd’) >>> deque_collections_2 deque([‘a’, ‘b’, ‘c’, ‘d’]) >>> list(our_deque_1) == list(deque_collections_1) True >>> list(our_deque_2) == list(deque_collections_2) True

extendleft(iterable: collections.abc.Iterable[Any]) → None

Appends every value of iterable to the beginning of the deque. Time complexity: O(n) >>> our_deque_1 = Deque([1, 2, 3]) >>> our_deque_1.extendleft([0, -1]) >>> our_deque_1 [-1, 0, 1, 2, 3] >>> our_deque_2 = Deque(‘cd’) >>> our_deque_2.extendleft(‘ba’) >>> our_deque_2 [‘a’, ‘b’, ‘c’, ‘d’] >>> from collections import deque >>> deque_collections_1 = deque([1, 2, 3]) >>> deque_collections_1.extendleft([0, -1]) >>> deque_collections_1 deque([-1, 0, 1, 2, 3]) >>> deque_collections_2 = deque(‘cd’) >>> deque_collections_2.extendleft(‘ba’) >>> deque_collections_2 deque([‘a’, ‘b’, ‘c’, ‘d’]) >>> list(our_deque_1) == list(deque_collections_1) True >>> list(our_deque_2) == list(deque_collections_2) True

is_empty() → bool

Checks if the deque is empty. Time complexity: O(1) >>> our_deque = Deque([1, 2, 3]) >>> our_deque.is_empty() False >>> our_empty_deque = Deque() >>> our_empty_deque.is_empty() True >>> from collections import deque >>> empty_deque_collections = deque() >>> list(our_empty_deque) == list(empty_deque_collections) True

pop() → Any

Removes the last element of the deque and returns it. Time complexity: O(1) @returns topop.val: the value of the node to pop. >>> our_deque1 = Deque([1]) >>> our_popped1 = our_deque1.pop() >>> our_popped1 1 >>> our_deque1 []

>>> our_deque2 = Deque([1, 2, 3, 15182])
>>> our_popped2 = our_deque2.pop()
>>> our_popped2
15182
>>> our_deque2
[1, 2, 3]

>>> from collections import deque
>>> deque_collections = deque([1, 2, 3, 15182])
>>> collections_popped = deque_collections.pop()
>>> collections_popped
15182
>>> deque_collections
deque([1, 2, 3])
>>> list(our_deque2) == list(deque_collections)
True
>>> our_popped2 == collections_popped
True

popleft() → Any

Removes the first element of the deque and returns it. Time complexity: O(1) @returns topop.val: the value of the node to pop. >>> our_deque1 = Deque([1]) >>> our_popped1 = our_deque1.pop() >>> our_popped1 1 >>> our_deque1 [] >>> our_deque2 = Deque([15182, 1, 2, 3]) >>> our_popped2 = our_deque2.popleft() >>> our_popped2 15182 >>> our_deque2 [1, 2, 3] >>> from collections import deque >>> deque_collections = deque([15182, 1, 2, 3]) >>> collections_popped = deque_collections.popleft() >>> collections_popped 15182 >>> deque_collections deque([1, 2, 3]) >>> list(our_deque2) == list(deque_collections) True >>> our_popped2 == collections_popped True

__slots__ = ('_back', '_front', '_len')

_back: Any = None

_front: Any = None

_len: int = 0

data_structures.queues.double_ended_queue.dq