FilesExpand file tree

master

/

stack.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

133 lines (101 loc) · 3.26 KB

master

/

stack.py

Copy path

Top

File metadata and controls

• Code
• Blame

133 lines (101 loc) · 3.26 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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()