Skip to content

Deque (LinkedList-based Double-ended Queue)

Download Source Files NEW

Specification

IQueue

Bases: Generic[T]

Interface for a queue data structure

Source code in src/datastructures/iqueue.py 
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
class IQueue(Generic[T]):
    ''' Interface for a queue data structure '''

    @abstractmethod
    def enqueue(self, item: T) -> None:
        ''' Enqueues an item into the queue.

            Arguments:
                item: T -- The item to enqueue.
        '''
        ...

    @abstractmethod
    def dequeue(self) -> T:
        ''' Dequeues an item from the queue.

            Returns:
                T -- The item dequeued from the queue.
        '''
        ...

    @abstractmethod
    def front(self) -> T:
        ''' Returns the front item in the queue without removing it.

            Returns:
                T -- The front item in the queue.
        '''
        ...

    @abstractmethod
    def back(self) -> T:
        ''' Returns the back item in the queue without removing it.

            Returns:
                T -- The back item in the queue.
        '''
        ...

    @abstractmethod
    def __len__(self) -> int:
        ''' Returns the number of items in the queue.   

            Returns:
                int -- The number of items in the queue.
        '''
        ...

    @abstractmethod
    def empty(self) -> bool:
        ''' Returns True if the queue is empty, False otherwise. 

            Returns:
                bool: True if the queue is empty, False otherwise.
        '''
        ...

    @abstractmethod
    def clear(self) -> None:
        ''' Clears the queue. '''
        ...

    @abstractmethod
    def __contains__(self, item: T) -> bool:
        ''' Returns True if the item is in the queue, False otherwise.

            Arguments:
                item: T -- The item to search for.

            Returns:
                bool: True if the item is in the queue, False otherwise.
        '''
        ...

    @abstractmethod
    def __eq__(self, other: object) -> bool:
        ''' Compares two queues for equality.

            Arguments:
                other: object -- The other queue to compare.

            Returns:
                bool -- True if the queues are equal, False otherwise.
        '''
        ...

    @abstractmethod
    def __str__(self) -> str:
        ''' Returns a string representation of the queue.

            Returns:
                str -- A string representation of the queue.
        '''
        ...

    @abstractmethod
    def __repr__(self) -> str:
        ''' Returns a string representation of the queue.

            Returns:
                str -- A string representation of the queue.
        '''
        ...

__contains__(item) abstractmethod

Returns True if the item is in the queue, False otherwise.

Parameters:

Name Type Description Default
item T

T -- The item to search for.

 required

Returns:

Name Type Description
bool bool

True if the item is in the queue, False otherwise.
Source code in src/datastructures/iqueue.py 
68
69
70
71
72
73
74
75
76
77
78
@abstractmethod
def __contains__(self, item: T) -> bool:
    ''' Returns True if the item is in the queue, False otherwise.

        Arguments:
            item: T -- The item to search for.

        Returns:
            bool: True if the item is in the queue, False otherwise.
    '''
    ...

__eq__(other) abstractmethod

Compares two queues for equality.

Parameters:

Name Type Description Default
other object

object -- The other queue to compare.

 required

Returns:

Type Description
bool

bool -- True if the queues are equal, False otherwise.
Source code in src/datastructures/iqueue.py 
80
81
82
83
84
85
86
87
88
89
90
@abstractmethod
def __eq__(self, other: object) -> bool:
    ''' Compares two queues for equality.

        Arguments:
            other: object -- The other queue to compare.

        Returns:
            bool -- True if the queues are equal, False otherwise.
    '''
    ...

__len__() abstractmethod

Returns the number of items in the queue.

Returns:

Type Description
int

int -- The number of items in the queue.
Source code in src/datastructures/iqueue.py 
45
46
47
48
49
50
51
52
@abstractmethod
def __len__(self) -> int:
    ''' Returns the number of items in the queue.   

        Returns:
            int -- The number of items in the queue.
    '''
    ...

__repr__() abstractmethod

Returns a string representation of the queue.

Returns:

Type Description
str

str -- A string representation of the queue.
Source code in src/datastructures/iqueue.py 
101
102
103
104
105
106
107
108
@abstractmethod
def __repr__(self) -> str:
    ''' Returns a string representation of the queue.

        Returns:
            str -- A string representation of the queue.
    '''
    ...

__str__() abstractmethod

Returns a string representation of the queue.

Returns:

Type Description
str

str -- A string representation of the queue.
Source code in src/datastructures/iqueue.py 
92
93
94
95
96
97
98
99
@abstractmethod
def __str__(self) -> str:
    ''' Returns a string representation of the queue.

        Returns:
            str -- A string representation of the queue.
    '''
    ...

back() abstractmethod

Returns the back item in the queue without removing it.

Returns:

Type Description
T

T -- The back item in the queue.
Source code in src/datastructures/iqueue.py 
36
37
38
39
40
41
42
43
@abstractmethod
def back(self) -> T:
    ''' Returns the back item in the queue without removing it.

        Returns:
            T -- The back item in the queue.
    '''
    ...

clear() abstractmethod

Clears the queue.

Source code in src/datastructures/iqueue.py 
63
64
65
66
@abstractmethod
def clear(self) -> None:
    ''' Clears the queue. '''
    ...

dequeue() abstractmethod

Dequeues an item from the queue.

Returns:

Type Description
T

T -- The item dequeued from the queue.
Source code in src/datastructures/iqueue.py 
18
19
20
21
22
23
24
25
@abstractmethod
def dequeue(self) -> T:
    ''' Dequeues an item from the queue.

        Returns:
            T -- The item dequeued from the queue.
    '''
    ...

empty() abstractmethod

Returns True if the queue is empty, False otherwise.

Returns:

Name Type Description
bool bool

True if the queue is empty, False otherwise.
Source code in src/datastructures/iqueue.py 
54
55
56
57
58
59
60
61
@abstractmethod
def empty(self) -> bool:
    ''' Returns True if the queue is empty, False otherwise. 

        Returns:
            bool: True if the queue is empty, False otherwise.
    '''
    ...

enqueue(item) abstractmethod

Enqueues an item into the queue.

Parameters:

Name Type Description Default
item T

T -- The item to enqueue.

 required
Source code in src/datastructures/iqueue.py 
 9
10
11
12
13
14
15
16
@abstractmethod
def enqueue(self, item: T) -> None:
    ''' Enqueues an item into the queue.

        Arguments:
            item: T -- The item to enqueue.
    '''
    ...

front() abstractmethod

Returns the front item in the queue without removing it.

Returns:

Type Description
T

T -- The front item in the queue.
Source code in src/datastructures/iqueue.py 
27
28
29
30
31
32
33
34
@abstractmethod
def front(self) -> T:
    ''' Returns the front item in the queue without removing it.

        Returns:
            T -- The front item in the queue.
    '''
    ...

Deque

Bases: IQueue[T]

A double-ended queue (deque) implementation.

Source code in src/datastructures/deque.py 
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
class Deque[T](IQueue[T]):
    """
    A double-ended queue (deque) implementation.
    """

    def __init__(self, data_type: type = object) -> None:
        """
        Initializes the deque with a specified data type.

        Args:
            - data_type (type): The type of data the deque will hold.
        """
        raise NotImplementedError("Deque initialization is not implemented.")

    def enqueue(self, item: T) -> None:
        """
        Adds an item to the back of the deque.

        Args:
            - item (T): The item to add to the back of the deque.

        Raises:
            - TypeError: If the item is not of the correct type.
        """
        raise NotImplementedError("Method to add an item to the back of the deque is not implemented.")

    def dequeue(self) -> T:
        """
        Removes and returns the item from the front of the deque.

        Returns:
            - T: The item removed from the front of the deque.

        Raises:
            - IndexError: If the deque is empty.
        """
        raise NotImplementedError("Method to remove an item from the front of the deque is not implemented.")

    def enqueue_front(self, item: T) -> None:
        """
        Adds an item to the front of the deque.

        Args:
            - item (T): The item to add to the front of the deque.

        Raises:
            - TypeError: If the item is not of the correct type.
        """
        raise NotImplementedError("Method to add an item to the front of the deque is not implemented.")

    def dequeue_back(self) -> T:
        """
        Removes and returns the item from the back of the deque.

        Returns:
            - T: The item removed from the back of the deque.

        Raises:
            - IndexError: If the deque is empty.
        """
        raise NotImplementedError("Method to remove an item from the back of the deque is not implemented.")

    def front(self) -> T:
        """
        Returns the front item of the deque without removing it.

        Returns:
            - T: The front item of the deque.

        Raises:
            - IndexError: If the deque is empty.
        """
        raise NotImplementedError("Method to get the front item of the deque is not implemented.")

    def back(self) -> T:
        """
        Returns the back item of the deque without removing it.

        Returns:
            - T: The back item of the deque.

        Raises:
            - IndexError: If the deque is empty.
        """
        raise NotImplementedError("Method to get the back item of the deque is not implemented.")

    def empty(self) -> bool:
        """
        Checks if the deque is empty.

        Returns:
            - bool: True if the deque is empty, False otherwise.
        """
        raise NotImplementedError("Method to check if the deque is empty is not implemented.")

    def __len__(self) -> int:
        """
        Returns the number of items in the deque.

        Returns:
            - int: The number of items in the deque.
        """
        raise NotImplementedError("Method to get the length of the deque is not implemented.")

    def __contains__(self, item: T) -> bool:
        """
        Checks if an item exists in the deque.

        Args:
            - item (T): The item to check for existence.

        Returns:
            - bool: True if the item exists in the deque, False otherwise.
        """
        raise NotImplementedError("Method to check if an item exists in the deque is not implemented.")

    def __eq__(self, other) -> bool:
        """
        Compares two deques for equality.

        Args:
            - other (Deque): The deque to compare with.

        Returns:
            - bool: True if the deques are equal, False otherwise.
        """
        raise NotImplementedError("Method to compare two deques is not implemented.")

    def clear(self):
        """
        Clears all items from the deque.
        """
        raise NotImplementedError("Method to clear the deque is not implemented.")

    def __str__(self) -> str:
        """
        Returns a string representation of the deque.

        Returns:
            - str: A string representation of the deque.
        """
        raise NotImplementedError("Method to get the string representation of the deque is not implemented.")

    def __repr__(self) -> str:
        """
        Returns a detailed string representation of the deque.

        Returns:
            - str: A detailed string representation of the deque.
        """
        raise NotImplementedError("Method to get the detailed string representation of the deque is not implemented.")

__contains__(item)

Checks if an item exists in the deque.

Parameters:

Name Type Description Default
- item T

The item to check for existence.

 required

Returns:

Type Description
bool
  • bool: True if the item exists in the deque, False otherwise.
Source code in src/datastructures/deque.py 
112
113
114
115
116
117
118
119
120
121
122
def __contains__(self, item: T) -> bool:
    """
    Checks if an item exists in the deque.

    Args:
        - item (T): The item to check for existence.

    Returns:
        - bool: True if the item exists in the deque, False otherwise.
    """
    raise NotImplementedError("Method to check if an item exists in the deque is not implemented.")

__eq__(other)

Compares two deques for equality.

Parameters:

Name Type Description Default
- other Deque

The deque to compare with.

 required

Returns:

Type Description
bool
  • bool: True if the deques are equal, False otherwise.
Source code in src/datastructures/deque.py 
124
125
126
127
128
129
130
131
132
133
134
def __eq__(self, other) -> bool:
    """
    Compares two deques for equality.

    Args:
        - other (Deque): The deque to compare with.

    Returns:
        - bool: True if the deques are equal, False otherwise.
    """
    raise NotImplementedError("Method to compare two deques is not implemented.")

__init__(data_type=object)

Initializes the deque with a specified data type.

Parameters:

Name Type Description Default
- data_type type

The type of data the deque will hold.

 required
Source code in src/datastructures/deque.py 
13
14
15
16
17
18
19
20
def __init__(self, data_type: type = object) -> None:
    """
    Initializes the deque with a specified data type.

    Args:
        - data_type (type): The type of data the deque will hold.
    """
    raise NotImplementedError("Deque initialization is not implemented.")

__len__()

Returns the number of items in the deque.

Returns:

Type Description
int
  • int: The number of items in the deque.
Source code in src/datastructures/deque.py 
103
104
105
106
107
108
109
110
def __len__(self) -> int:
    """
    Returns the number of items in the deque.

    Returns:
        - int: The number of items in the deque.
    """
    raise NotImplementedError("Method to get the length of the deque is not implemented.")

__repr__()

Returns a detailed string representation of the deque.

Returns:

Type Description
str
  • str: A detailed string representation of the deque.
Source code in src/datastructures/deque.py 
151
152
153
154
155
156
157
158
def __repr__(self) -> str:
    """
    Returns a detailed string representation of the deque.

    Returns:
        - str: A detailed string representation of the deque.
    """
    raise NotImplementedError("Method to get the detailed string representation of the deque is not implemented.")

__str__()

Returns a string representation of the deque.

Returns:

Type Description
str
  • str: A string representation of the deque.
Source code in src/datastructures/deque.py 
142
143
144
145
146
147
148
149
def __str__(self) -> str:
    """
    Returns a string representation of the deque.

    Returns:
        - str: A string representation of the deque.
    """
    raise NotImplementedError("Method to get the string representation of the deque is not implemented.")

back()

Returns the back item of the deque without removing it.

Returns:

Type Description
T
  • T: The back item of the deque.

Raises:

Type Description
-IndexError

If the deque is empty.
Source code in src/datastructures/deque.py 
82
83
84
85
86
87
88
89
90
91
92
def back(self) -> T:
    """
    Returns the back item of the deque without removing it.

    Returns:
        - T: The back item of the deque.

    Raises:
        - IndexError: If the deque is empty.
    """
    raise NotImplementedError("Method to get the back item of the deque is not implemented.")

clear()

Clears all items from the deque.

Source code in src/datastructures/deque.py 
136
137
138
139
140
def clear(self):
    """
    Clears all items from the deque.
    """
    raise NotImplementedError("Method to clear the deque is not implemented.")

dequeue()

Removes and returns the item from the front of the deque.

Returns:

Type Description
T
  • T: The item removed from the front of the deque.

Raises:

Type Description
-IndexError

If the deque is empty.
Source code in src/datastructures/deque.py 
34
35
36
37
38
39
40
41
42
43
44
def dequeue(self) -> T:
    """
    Removes and returns the item from the front of the deque.

    Returns:
        - T: The item removed from the front of the deque.

    Raises:
        - IndexError: If the deque is empty.
    """
    raise NotImplementedError("Method to remove an item from the front of the deque is not implemented.")

dequeue_back()

Removes and returns the item from the back of the deque.

Returns:

Type Description
T
  • T: The item removed from the back of the deque.

Raises:

Type Description
-IndexError

If the deque is empty.
Source code in src/datastructures/deque.py 
58
59
60
61
62
63
64
65
66
67
68
def dequeue_back(self) -> T:
    """
    Removes and returns the item from the back of the deque.

    Returns:
        - T: The item removed from the back of the deque.

    Raises:
        - IndexError: If the deque is empty.
    """
    raise NotImplementedError("Method to remove an item from the back of the deque is not implemented.")

empty()

Checks if the deque is empty.

Returns:

Type Description
bool
  • bool: True if the deque is empty, False otherwise.
Source code in src/datastructures/deque.py 
 94
 95
 96
 97
 98
 99
100
101
def empty(self) -> bool:
    """
    Checks if the deque is empty.

    Returns:
        - bool: True if the deque is empty, False otherwise.
    """
    raise NotImplementedError("Method to check if the deque is empty is not implemented.")

enqueue(item)

Adds an item to the back of the deque.

Parameters:

Name Type Description Default
- item T

The item to add to the back of the deque.

 required

Raises:

Type Description
-TypeError

If the item is not of the correct type.
Source code in src/datastructures/deque.py 
22
23
24
25
26
27
28
29
30
31
32
def enqueue(self, item: T) -> None:
    """
    Adds an item to the back of the deque.

    Args:
        - item (T): The item to add to the back of the deque.

    Raises:
        - TypeError: If the item is not of the correct type.
    """
    raise NotImplementedError("Method to add an item to the back of the deque is not implemented.")

enqueue_front(item)

Adds an item to the front of the deque.

Parameters:

Name Type Description Default
- item T

The item to add to the front of the deque.

 required

Raises:

Type Description
-TypeError

If the item is not of the correct type.
Source code in src/datastructures/deque.py 
46
47
48
49
50
51
52
53
54
55
56
def enqueue_front(self, item: T) -> None:
    """
    Adds an item to the front of the deque.

    Args:
        - item (T): The item to add to the front of the deque.

    Raises:
        - TypeError: If the item is not of the correct type.
    """
    raise NotImplementedError("Method to add an item to the front of the deque is not implemented.")

front()

Returns the front item of the deque without removing it.

Returns:

Type Description
T
  • T: The front item of the deque.

Raises:

Type Description
-IndexError

If the deque is empty.
Source code in src/datastructures/deque.py 
70
71
72
73
74
75
76
77
78
79
80
def front(self) -> T:
    """
    Returns the front item of the deque without removing it.

    Returns:
        - T: The front item of the deque.

    Raises:
        - IndexError: If the deque is empty.
    """
    raise NotImplementedError("Method to get the front item of the deque is not implemented.")