The Self-Taught Computer Scientist

Chapter 11 Stacks
121
Here is how to implement a stack that keeps track of the minimum element in Python:
class MinStack():
def __init__(self):
self.main = []
self.min = []
def push(self, n):
if len(self.main) == 0:
self.min.append(n)
elif n <= self.min[− 1]:
self.min.append(n)
else:
self.min.append(self.min[− 1])
self.main.append(n)
def pop(self):
self.min.pop()
return self.main.pop()
def get_min(self):
return self.min[− 1]
First, you define a class called 
MinStack
. Inside 
__init__
, you define two instance variables: 
main
and 
min
. You assign both variables to empty lists. You will use 
main
to keep track of your main stack 
and use 
min
to keep track of the smallest element.
class MinStack():
def __init__(self):
self.main = []
self.min = [] 
Next, you define your stack’s 
push
method. Inside 
push
, you check to see whether 
self.main
is 
empty because if it is, then no matter what 
n
is, it is the smallest number in your stack. If 
self.main
is empty, you append 
n
to 
min
.
def push(self, n):
if len(self.main) == 0:
self.min.append(n) 
If 
self.main
is not empty, you check to see whether 
n
is less than or equal to the last item in 
self 
.min
. The last item in 
self.min
always needs to be the smallest number in your stack, so if 
n
is less 
than or equal to the last item in 
self.min
, you append 
n
to 
self.min
.
elif n <= self.min[− 1]:
self.min.append(n)

---