Skip to content

ArrayStack (Array-based)

Download Source Files NEW

Specification

IStack

Bases: Generic[T], ABC

Interface for a stack data structure

Source code in src/datastructures/istack.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
class IStack(Generic[T], ABC):
    ''' Interface for a stack data structure '''

    @abstractmethod
    def push(self, item: T) -> None:
        ''' Pushes an item onto the stack.

            Arguments:
                item: T -- The item to push onto the stack.
        '''
        ...

    @abstractmethod
    def pop(self) -> T:
        ''' Pops an item from the stack.

            Returns:
                T -- The item popped from the stack.
        '''
        ...

    @abstractmethod
    def peek(self) -> T:
        ''' Returns the top item on the stack without removing it.

            Returns:
                T -- The top item on the stack.
        '''
        ...

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

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

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

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

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

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

    @abstractmethod
    def __eq__(self, other: object) -> bool:
        ''' Returns True if the stack is equal to another stack, False otherwise.

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

            Returns:
                bool: True if the stack is equal to another stack, False otherwise.
        '''
        ...

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

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

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

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

empty abstractmethod property

Returns True if the stack is empty, False otherwise.

Returns:

Name Type Description
bool bool

True if the stack is empty, False otherwise.

__contains__(item) abstractmethod

Returns True if the item is in the stack, 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 stack, False otherwise.
Source code in src/datastructures/istack.py 
51
52
53
54
55
56
57
58
59
60
61
@abstractmethod
def __contains__(self, item: T) -> bool:
    ''' Returns True if the item is in the stack, False otherwise.

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

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

__eq__(other) abstractmethod

Returns True if the stack is equal to another stack, False otherwise.

Parameters:

Name Type Description Default
other object

object -- The other stack to compare.

 required

Returns:

Name Type Description
bool bool

True if the stack is equal to another stack, False otherwise.
Source code in src/datastructures/istack.py 
63
64
65
66
67
68
69
70
71
72
73
@abstractmethod
def __eq__(self, other: object) -> bool:
    ''' Returns True if the stack is equal to another stack, False otherwise.

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

        Returns:
            bool: True if the stack is equal to another stack, False otherwise.
    '''
    ...

__len__() abstractmethod

Returns the number of items in the stack.

Returns:

Type Description
int

int -- The number of items in the stack.
Source code in src/datastructures/istack.py 
75
76
77
78
79
80
81
82
@abstractmethod
def __len__(self) -> int:
    ''' Returns the number of items in the stack.

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

__repr__() abstractmethod

Returns a string representation of the stack.

Source code in src/datastructures/istack.py 
89
90
91
92
@abstractmethod
def __repr__(self) -> str:
    ''' Returns a string representation of the stack.'''
    ...

__str__() abstractmethod

Returns a string representation of the stack.

Source code in src/datastructures/istack.py 
84
85
86
87
@abstractmethod
def __str__(self) -> str:
    ''' Returns a string representation of the stack.'''
    ...

clear() abstractmethod

Clears the stack.

Source code in src/datastructures/istack.py 
46
47
48
49
@abstractmethod
def clear(self) -> None:
    ''' Clears the stack. '''
    ...

peek() abstractmethod

Returns the top item on the stack without removing it.

Returns:

Type Description
T

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

        Returns:
            T -- The top item on the stack.
    '''
    ...

pop() abstractmethod

Pops an item from the stack.

Returns:

Type Description
T

T -- The item popped from the stack.
Source code in src/datastructures/istack.py 
18
19
20
21
22
23
24
25
@abstractmethod
def pop(self) -> T:
    ''' Pops an item from the stack.

        Returns:
            T -- The item popped from the stack.
    '''
    ...

push(item) abstractmethod

Pushes an item onto the stack.

Parameters:

Name Type Description Default
item T

T -- The item to push onto the stack.

 required
Source code in src/datastructures/istack.py 
 9
10
11
12
13
14
15
16
@abstractmethod
def push(self, item: T) -> None:
    ''' Pushes an item onto the stack.

        Arguments:
            item: T -- The item to push onto the stack.
    '''
    ...

ArrayStack

Bases: IStack[T]

ArrayStack class that implements the IStack interface. The ArrayStack is a fixed-size stack that uses an Array to store the items.

Source code in src/datastructures/arraystack.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
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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
class ArrayStack(IStack[T]):
    ''' ArrayStack class that implements the IStack interface. The ArrayStack is a 
        fixed-size stack that uses an Array to store the items.'''

    def __init__(self, max_size: int = 0, data_type=object) -> None:
        ''' Constructor to initialize the stack 

            Examples:
                >>> s = ArrayStack(max_size=5, data_type=int)
                >>> s.empty
                True
                >>> s.full
                False
                >>> s.maxsize
                5

            Arguments: 
                max_size: int -- The maximum size of the stack. 
                data_type: type -- The data type of the stack.       
        '''
        raise NotImplementedError('ArrayStack is not implemented')

    def push(self, item: T) -> None:
        ''' Pushes an item onto the stack.

            Examples:
                >>> s = ArrayStack(max_size=5, data_type=int)
                >>> s.push(1)
                >>> s.push(2)
                >>> s.push(3)
                >>> s.push(4)
                >>> s.push(5)
                >>> s.full
                True
                >>> print(repr(s))
                ArrayStack(5): items: [1, 2, 3, 4, 5]
                >>> s.push(6)
                IndexError('Stack is full')

            Arguments:
                item: T -- The item to push onto the stack.
        '''
        raise NotImplementedError

    def pop(self) -> T:
        ''' Pops an item from the stack.

            Examples:
                >>> s = ArrayStack(max_size=5, data_type=int)
                >>> s.push(1)
                >>> s.push(2)
                >>> s.push(3)
                >>> s.pop()
                3
                >>> s.pop()
                2
                >>> s.pop()
                1
                >>> s.empty
                True
                >>> print(repr(s))
                ArrayStack(5): items: []
                >>> s.pop()
                IndexError('Stack is empty')

            Returns:
                T -- The item popped from the stack.
        '''
        raise NotImplementedError

    def clear(self) -> None:
       ''' Clears the stack. 

           Examples:
               >>> s = ArrayStack(max_size=5, data_type=int)
               >>> s.push(1)
               >>> s.push(2)
               >>> s.push(3)
               >>> s.clear()
               >>> s.empty
               True
               >>> print(repr(s))
               ArrayStack(5): items: []
        '''
       raise NotImplementedError

    @property
    def peek(self) -> T:
        ''' Returns the top item on the stack without removing it.

            Returns:
                T -- The top item on the stack.

            Examples:
                >>> s = ArrayStack(max_size=5, data_type=int)
                >>> s.push(1)
                >>> s.push(2)
                >>> s.push(3)
                >>> s.peek
                3
                >>> s.pop()
                3
                >>> s.peek
                2
                >>> s.pop()
                2
                >>> s.peek
                1
                >>> s.pop()
                1
                >>> s.empty
                True
                >>> s.peek
                IndexError('Stack is empty')
        '''
        raise NotImplementedError

    @property
    def maxsize(self) -> int:
        ''' Returns the maximum size of the stack. 

            Examples:
                >>> s = ArrayStack(max_size=5, data_type=int)
                >>> s.maxsize
                5

            Returns:
                int: The maximum size of the stack.
        '''
        raise NotImplementedError    
    @property
    def full(self) -> bool:
        ''' Returns True if the stack is full, False otherwise. 

            Examples:


            Returns:
                bool: True if the stack is full, False otherwise.
        '''
        raise NotImplementedError

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

            Examples:
                >>> s = ArrayStack(max_size=5, data_type=int)
                >>> s.empty
                True
                >>> s.push(1)
                >>> s.empty
                False
                >>> s.pop()
                1
                >>> s.empty
                True

            Returns:
                bool: True if the stack is empty, False otherwise.
        '''
        raise NotImplementedError

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

            Examples:
                >>> s1 = ArrayStack(max_size=5, data_type=int)
                >>> s2 = ArrayStack(max_size=5, data_type=int)
                >>> s1 == s2
                True
                >>> s1.push(1)
                >>> s1 == s2
                False
                >>> s2.push(1)
                >>> s1 == s2
                True
                >>> s1.push(2)
                >>> s2.push(3)
                >>> s1 == s2
                False

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

            Returns:
                bool -- True if the stacks are equal, False otherwise.
        '''
        raise NotImplementedError

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

            Examples:
                >>> s = ArrayStack(max_size=5, data_type=int)
                >>> len(s)
                0
                >>> s.push(1)
                >>> len(s)
                1
                >>> s.push(2)
                >>> len(s)
                2
                >>> s.pop()
                2
                >>> len(s)
                1
                >>> s.pop()
                1
                >>> len(s)
                0

            Returns:
                int -- The number of items in the stack.
        '''
        raise NotImplementedError

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

            Examples:
                >>> s = ArrayStack(max_size=5, data_type=int)
                >>> s.push(1)
                >>> s.push(2)
                >>> s.push(3)
                >>> 1 in s
                True
                >>> 2 in s
                True
                >>> 3 in s
                True
                >>> 4 in s
                False
                >>> 5 in s
                False

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

            Returns:
                bool -- True if the item is in the stack, False otherwise.
        '''
        raise NotImplementedError

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

            Examples:
                >>> s = ArrayStack(max_size=5, data_type=int)
                >>> s.push(1)
                >>> s.push(2)
                >>> s.push(3)
                >>> print(s)
                [1, 2, 3]

            Returns:
                str -- A string representation of the stack.
        '''
        return str([self.stack[i] for i in range(self._top)])

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

            Examples:
                >>> s = ArrayStack(max_size=5, data_type=int)
                >>> s.push(1)
                >>> s.push(2)
                >>> s.push(3)
                >>> repr(s)
                'ArrayStack(5): items: [1, 2, 3]'

            Returns:
                str -- A string representation of the stack.
        '''
        return f"ArrayStack({self.maxsize}): items: {str(self)}"

empty property

Returns True if the stack is empty, False otherwise.

Examples:

>>> s = ArrayStack(max_size=5, data_type=int)
>>> s.empty
True
>>> s.push(1)
>>> s.empty
False
>>> s.pop()
1
>>> s.empty
True

Returns:

Name Type Description
bool bool

True if the stack is empty, False otherwise.

full property

Returns True if the stack is full, False otherwise.

Examples:

Returns:

Name Type Description
bool bool

True if the stack is full, False otherwise.

maxsize property

Returns the maximum size of the stack.

Examples:

>>> s = ArrayStack(max_size=5, data_type=int)
>>> s.maxsize
5

Returns:

Name Type Description
int int

The maximum size of the stack.

peek property

Returns the top item on the stack without removing it.

Returns:

Type Description
T

T -- The top item on the stack.

Examples:

>>> s = ArrayStack(max_size=5, data_type=int)
>>> s.push(1)
>>> s.push(2)
>>> s.push(3)
>>> s.peek
3
>>> s.pop()
3
>>> s.peek
2
>>> s.pop()
2
>>> s.peek
1
>>> s.pop()
1
>>> s.empty
True
>>> s.peek
IndexError('Stack is empty')

__contains__(item)

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

Examples:

>>> s = ArrayStack(max_size=5, data_type=int)
>>> s.push(1)
>>> s.push(2)
>>> s.push(3)
>>> 1 in s
True
>>> 2 in s
True
>>> 3 in s
True
>>> 4 in s
False
>>> 5 in s
False

Parameters:

Name Type Description Default
item T

T -- The item to search for.

 required

Returns:

Type Description
bool

bool -- True if the item is in the stack, False otherwise.
Source code in src/datastructures/arraystack.py 
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
def __contains__(self, item: T) -> bool:
    ''' Returns True if the item is in the stack, False otherwise.

        Examples:
            >>> s = ArrayStack(max_size=5, data_type=int)
            >>> s.push(1)
            >>> s.push(2)
            >>> s.push(3)
            >>> 1 in s
            True
            >>> 2 in s
            True
            >>> 3 in s
            True
            >>> 4 in s
            False
            >>> 5 in s
            False

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

        Returns:
            bool -- True if the item is in the stack, False otherwise.
    '''
    raise NotImplementedError

__eq__(other)

Compares two stacks for equality.

Examples:

>>> s1 = ArrayStack(max_size=5, data_type=int)
>>> s2 = ArrayStack(max_size=5, data_type=int)
>>> s1 == s2
True
>>> s1.push(1)
>>> s1 == s2
False
>>> s2.push(1)
>>> s1 == s2
True
>>> s1.push(2)
>>> s2.push(3)
>>> s1 == s2
False

Parameters:

Name Type Description Default
other object

object -- The other stack to compare.

 required

Returns:

Type Description
bool

bool -- True if the stacks are equal, False otherwise.
Source code in src/datastructures/arraystack.py 
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
def __eq__(self, other: object) -> bool:
    ''' Compares two stacks for equality.

        Examples:
            >>> s1 = ArrayStack(max_size=5, data_type=int)
            >>> s2 = ArrayStack(max_size=5, data_type=int)
            >>> s1 == s2
            True
            >>> s1.push(1)
            >>> s1 == s2
            False
            >>> s2.push(1)
            >>> s1 == s2
            True
            >>> s1.push(2)
            >>> s2.push(3)
            >>> s1 == s2
            False

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

        Returns:
            bool -- True if the stacks are equal, False otherwise.
    '''
    raise NotImplementedError

__init__(max_size=0, data_type=object)

Constructor to initialize the stack

Examples:

>>> s = ArrayStack(max_size=5, data_type=int)
>>> s.empty
True
>>> s.full
False
>>> s.maxsize
5

Parameters:

Name Type Description Default
max_size int

int -- The maximum size of the stack.

0
data_type

type -- The data type of the stack.

 object
Source code in src/datastructures/arraystack.py 
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def __init__(self, max_size: int = 0, data_type=object) -> None:
    ''' Constructor to initialize the stack 

        Examples:
            >>> s = ArrayStack(max_size=5, data_type=int)
            >>> s.empty
            True
            >>> s.full
            False
            >>> s.maxsize
            5

        Arguments: 
            max_size: int -- The maximum size of the stack. 
            data_type: type -- The data type of the stack.       
    '''
    raise NotImplementedError('ArrayStack is not implemented')

__len__()

Returns the number of items in the stack.

Examples:

>>> s = ArrayStack(max_size=5, data_type=int)
>>> len(s)
0
>>> s.push(1)
>>> len(s)
1
>>> s.push(2)
>>> len(s)
2
>>> s.pop()
2
>>> len(s)
1
>>> s.pop()
1
>>> len(s)
0

Returns:

Type Description
int

int -- The number of items in the stack.
Source code in src/datastructures/arraystack.py 
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
def __len__(self) -> int:
    ''' Returns the number of items in the stack.

        Examples:
            >>> s = ArrayStack(max_size=5, data_type=int)
            >>> len(s)
            0
            >>> s.push(1)
            >>> len(s)
            1
            >>> s.push(2)
            >>> len(s)
            2
            >>> s.pop()
            2
            >>> len(s)
            1
            >>> s.pop()
            1
            >>> len(s)
            0

        Returns:
            int -- The number of items in the stack.
    '''
    raise NotImplementedError

__repr__()

Returns a string representation of the stack.

Examples:

>>> s = ArrayStack(max_size=5, data_type=int)
>>> s.push(1)
>>> s.push(2)
>>> s.push(3)
>>> repr(s)
'ArrayStack(5): items: [1, 2, 3]'

Returns:

Type Description
str

str -- A string representation of the stack.
Source code in src/datastructures/arraystack.py 
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
def __repr__(self) -> str:
    ''' Returns a string representation of the stack.

        Examples:
            >>> s = ArrayStack(max_size=5, data_type=int)
            >>> s.push(1)
            >>> s.push(2)
            >>> s.push(3)
            >>> repr(s)
            'ArrayStack(5): items: [1, 2, 3]'

        Returns:
            str -- A string representation of the stack.
    '''
    return f"ArrayStack({self.maxsize}): items: {str(self)}"

__str__()

Returns a string representation of the stack.

Examples:

>>> s = ArrayStack(max_size=5, data_type=int)
>>> s.push(1)
>>> s.push(2)
>>> s.push(3)
>>> print(s)
[1, 2, 3]

Returns:

Type Description
str

str -- A string representation of the stack.
Source code in src/datastructures/arraystack.py 
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
def __str__(self) -> str:
    ''' Returns a string representation of the stack.

        Examples:
            >>> s = ArrayStack(max_size=5, data_type=int)
            >>> s.push(1)
            >>> s.push(2)
            >>> s.push(3)
            >>> print(s)
            [1, 2, 3]

        Returns:
            str -- A string representation of the stack.
    '''
    return str([self.stack[i] for i in range(self._top)])

clear()

Clears the stack.

Examples:

>>> s = ArrayStack(max_size=5, data_type=int)
>>> s.push(1)
>>> s.push(2)
>>> s.push(3)
>>> s.clear()
>>> s.empty
True
>>> print(repr(s))
ArrayStack(5): items: []
Source code in src/datastructures/arraystack.py 
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
def clear(self) -> None:
   ''' Clears the stack. 

       Examples:
           >>> s = ArrayStack(max_size=5, data_type=int)
           >>> s.push(1)
           >>> s.push(2)
           >>> s.push(3)
           >>> s.clear()
           >>> s.empty
           True
           >>> print(repr(s))
           ArrayStack(5): items: []
    '''
   raise NotImplementedError

pop()

Pops an item from the stack.

Examples:

>>> s = ArrayStack(max_size=5, data_type=int)
>>> s.push(1)
>>> s.push(2)
>>> s.push(3)
>>> s.pop()
3
>>> s.pop()
2
>>> s.pop()
1
>>> s.empty
True
>>> print(repr(s))
ArrayStack(5): items: []
>>> s.pop()
IndexError('Stack is empty')

Returns:

Type Description
T

T -- The item popped from the stack.
Source code in src/datastructures/arraystack.py 
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
def pop(self) -> T:
    ''' Pops an item from the stack.

        Examples:
            >>> s = ArrayStack(max_size=5, data_type=int)
            >>> s.push(1)
            >>> s.push(2)
            >>> s.push(3)
            >>> s.pop()
            3
            >>> s.pop()
            2
            >>> s.pop()
            1
            >>> s.empty
            True
            >>> print(repr(s))
            ArrayStack(5): items: []
            >>> s.pop()
            IndexError('Stack is empty')

        Returns:
            T -- The item popped from the stack.
    '''
    raise NotImplementedError

push(item)

Pushes an item onto the stack.

Examples:

>>> s = ArrayStack(max_size=5, data_type=int)
>>> s.push(1)
>>> s.push(2)
>>> s.push(3)
>>> s.push(4)
>>> s.push(5)
>>> s.full
True
>>> print(repr(s))
ArrayStack(5): items: [1, 2, 3, 4, 5]
>>> s.push(6)
IndexError('Stack is full')

Parameters:

Name Type Description Default
item T

T -- The item to push onto the stack.

 required
Source code in src/datastructures/arraystack.py 
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def push(self, item: T) -> None:
    ''' Pushes an item onto the stack.

        Examples:
            >>> s = ArrayStack(max_size=5, data_type=int)
            >>> s.push(1)
            >>> s.push(2)
            >>> s.push(3)
            >>> s.push(4)
            >>> s.push(5)
            >>> s.full
            True
            >>> print(repr(s))
            ArrayStack(5): items: [1, 2, 3, 4, 5]
            >>> s.push(6)
            IndexError('Stack is full')

        Arguments:
            item: T -- The item to push onto the stack.
    '''
    raise NotImplementedError