data_structures.queues.double_ended_queue
=========================================

.. py:module:: data_structures.queues.double_ended_queue

.. autoapi-nested-parse::

   Implementation of double ended queue.



Attributes
----------

.. autoapisummary::

   data_structures.queues.double_ended_queue.dq


Classes
-------

.. autoapisummary::

   data_structures.queues.double_ended_queue.Deque


Module Contents
---------------

.. py:class:: 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


   .. py:class:: _Iterator(cur: Deque | None)

      Helper class for iteration. Will be used to implement iteration.
      Attributes
      ----------
      _cur: _Node
          the current node of the iteration.


      .. py:method:: __iter__() -> Deque

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



      .. py:method:: __next__() -> Any

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



      .. py:attribute:: __slots__
         :value: ('_cur',)



      .. py:attribute:: _cur



   .. py:class:: _Node

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


      .. py:attribute:: next_node
         :type:  Deque | None
         :value: None



      .. py:attribute:: prev_node
         :type:  Deque | None
         :value: None



      .. py:attribute:: val
         :type:  Any
         :value: None




   .. py:method:: __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



   .. py:method:: __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



   .. py:method:: __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



   .. py:method:: __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]



   .. py:method:: 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



   .. py:method:: 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



   .. py:method:: 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



   .. py:method:: 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



   .. py:method:: 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



   .. py:method:: 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



   .. py:method:: 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



   .. py:attribute:: __slots__
      :value: ('_back', '_front', '_len')



   .. py:attribute:: _back
      :type:  Any
      :value: None



   .. py:attribute:: _front
      :type:  Any
      :value: None



   .. py:attribute:: _len
      :type:  int
      :value: 0



.. py:data:: dq