Repository navigation
Expand file tree
/
Copy pathstack.py
More file actions
133 lines (101 loc) · 3.26 KB
/
Copy pathstack.py
File metadata and controls
133 lines (101 loc) · 3.26 KB
1
2
3
4
5
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
from __future__ import annotations
from typing import Generic, TypeVar
T = TypeVar("T")
class StackOverflowError(BaseException):
pass
class StackUnderflowError(BaseException):
pass
class Stack(Generic[T]):
"""A stack is an abstract data type that serves as a collection of
elements with two principal operations: push() and pop(). push() adds an
element to the top of the stack, and pop() removes an element from the top
of a stack. The order in which elements come off of a stack are
Last In, First Out (LIFO).
https://en.wikipedia.org/wiki/Stack_(abstract_data_type)
"""
def __init__(self, limit: int = 10):
self.stack: list[T] = []
self.limit = limit
def __bool__(self) -> bool:
return bool(self.stack)
def __str__(self) -> str:
return str(self.stack)
def push(self, data: T) -> None:
"""Push an element to the top of the stack."""
if len(self.stack) >= self.limit:
raise StackOverflowError
self.stack.append(data)
def pop(self) -> T:
"""
Pop an element off of the top of the stack.
>>> Stack().pop()
Traceback (most recent call last):
...
data_structures.stacks.stack.StackUnderflowError
"""
if not self.stack:
raise StackUnderflowError
return self.stack.pop()
def peek(self) -> T:
"""
Peek at the top-most element of the stack.
>>> Stack().pop()
Traceback (most recent call last):
...
data_structures.stacks.stack.StackUnderflowError
"""
if not self.stack:
raise StackUnderflowError
return self.stack[-1]
def is_empty(self) -> bool:
"""Check if a stack is empty."""
return not bool(self.stack)
def is_full(self) -> bool:
return self.size() == self.limit
def size(self) -> int:
"""Return the size of the stack."""
return len(self.stack)
def __contains__(self, item: T) -> bool:
"""Check if item is in stack"""
return item in self.stack
def test_stack() -> None:
"""
>>> test_stack()
"""
stack: Stack[int] = Stack(10)
assert bool(stack) is False
assert stack.is_empty() is True
assert stack.is_full() is False
assert str(stack) == "[]"
try:
_ = stack.pop()
assert False # This should not happen
except StackUnderflowError:
assert True # This should happen
try:
_ = stack.peek()
assert False # This should not happen
except StackUnderflowError:
assert True # This should happen
for i in range(10):
assert stack.size() == i
stack.push(i)
assert bool(stack)
assert not stack.is_empty()
assert stack.is_full()
assert str(stack) == str(list(range(10)))
assert stack.pop() == 9
assert stack.peek() == 8
stack.push(100)
assert str(stack) == str([0, 1, 2, 3, 4, 5, 6, 7, 8, 100])
try:
stack.push(200)
assert False # This should not happen
except StackOverflowError:
assert True # This should happen
assert not stack.is_empty()
assert stack.size() == 10
assert 5 in stack
assert 55 not in stack
if __name__ == "__main__":
test_stack()