stack.py

from __future__ importannotations

fromtypingimportGeneric, TypeVar

T=TypeVar("T")


classStackOverflowError(BaseException):
pass


classStackUnderflowError(BaseException):
pass


classStack(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:
returnbool(self.stack)

def__str__(self) ->str:
returnstr(self.stack)

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

 """
iflen(self.stack) >=self.limit:
raiseStackOverflowError
self.stack.append(data)

defpop(self) ->T:
"""
 Pop an element off of the top of the stack.

 >>> S = Stack()
 >>> S.push(-5)
 >>> S.push(10)
 >>> S.pop()
 10

 >>> Stack().pop()
 Traceback (most recent call last):
 ...
 data_structures.stacks.stack.StackUnderflowError
 """
ifnotself.stack:
raiseStackUnderflowError
returnself.stack.pop()

defpeek(self) ->T:
"""
 Peek at the top-most element of the stack.

 >>> S = Stack()
 >>> S.push(-5)
 >>> S.push(10)
 >>> S.peek()
 10

 >>> Stack().peek()
 Traceback (most recent call last):
 ...
 data_structures.stacks.stack.StackUnderflowError
 """
ifnotself.stack:
raiseStackUnderflowError
returnself.stack[-1]

defis_empty(self) ->bool:
"""
 Check if a stack is empty.

 >>> S = Stack()
 >>> S.is_empty()
 True

 >>> S = Stack()
 >>> S.push(10)
 >>> S.is_empty()
 False
 """
returnnotbool(self.stack)

defis_full(self) ->bool:
"""
 >>> S = Stack()
 >>> S.is_full()
 False

 >>> S = Stack(1)
 >>> S.push(10)
 >>> S.is_full()
 True
 """
returnself.size() ==self.limit

defsize(self) ->int:
"""
 Return the size of the stack.

 >>> S = Stack(3)
 >>> S.size()
 0

 >>> S = Stack(3)
 >>> S.push(10)
 >>> S.size()
 1

 >>> S = Stack(3)
 >>> S.push(10)
 >>> S.push(20)
 >>> S.size()
 2
 """
returnlen(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
 """
returniteminself.stack


deftest_stack() ->None:
"""
 >>> test_stack()
 """
stack: Stack[int] =Stack(10)
assertbool(stack) isFalse
assertstack.is_empty() isTrue
assertstack.is_full() isFalse
assertstr(stack) =="[]"

try:
_=stack.pop()
raiseAssertionError# This should not happen
exceptStackUnderflowError:
assertTrue# This should happen

try:
_=stack.peek()
raiseAssertionError# This should not happen
exceptStackUnderflowError:
assertTrue# This should happen

foriinrange(10):
assertstack.size() ==i
stack.push(i)

assertbool(stack)
assertnotstack.is_empty()
assertstack.is_full()
assertstr(stack) ==str(list(range(10)))
assertstack.pop() ==9
assertstack.peek() ==8

stack.push(100)
assertstr(stack) ==str([0, 1, 2, 3, 4, 5, 6, 7, 8, 100])

try:
stack.push(200)
raiseAssertionError# This should not happen
exceptStackOverflowError:
assertTrue# This should happen

assertnotstack.is_empty()
assertstack.size() ==10

assert5instack
assert55notinstack


if__name__=="__main__":
test_stack()

importdoctest

doctest.testmod()