iframe-proxy | Sunbelt Computer Software

History

215 lines (168 loc) · 4.61 KB

Raw

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

from __future__ import annotations

from typing import TypeVar

T = TypeVar("T")

class StackOverflowError(BaseException):

pass

class StackUnderflowError(BaseException):

pass

class Stack[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.

>>> S = Stack(2) # stack size = 2

>>> S.push(10)

>>> S.push(20)

>>> print(S)

[10, 20]

>>> S = Stack(1) # stack size = 1

>>> S.push(10)

>>> S.push(20)

Traceback (most recent call last):

...

data_structures.stacks.stack.StackOverflowError

"""

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.

>>> S = Stack()

>>> S.push(-5)

>>> S.push(10)

>>> S.pop()

>>> 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.

>>> S = Stack()

>>> S.push(-5)

>>> S.push(10)

>>> S.peek()

>>> Stack().peek()

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.

>>> S = Stack()

>>> S.is_empty()

True

>>> S = Stack()

>>> S.push(10)

>>> S.is_empty()

False

"""

return not bool(self.stack)

def is_full(self) -> bool:

"""

>>> S = Stack()

>>> S.is_full()

False

>>> S = Stack(1)

>>> S.push(10)

>>> S.is_full()

True

"""

return self.size() == self.limit

def size(self) -> int:

"""

Return the size of the stack.

>>> S = Stack(3)

>>> S.size()

>>> S = Stack(3)

>>> S.push(10)

>>> S.size()

>>> S = Stack(3)

>>> S.push(10)

>>> S.push(20)

>>> S.size()

"""

return len(self.stack)

def __contains__(self, item: T) -> bool:

"""

Check if item is in stack

>>> S = Stack(3)

>>> S.push(10)

>>> 10 in S

True

>>> S = Stack(3)

>>> S.push(10)

>>> 20 in S

False

"""

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

raise AssertionError # This should not happen

except StackUnderflowError:

assert True # This should happen

try:

_ = stack.peek()

raise AssertionError # 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)

raise AssertionError # 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()

import doctest

doctest.testmod()

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

stack.py

Latest commit

History

stack.py

File metadata and controls