The Self-Taught Computer Scientist

Data Structures
122
If 
n
is not less than or equal to the last item in 
self.min
(and is, therefore, larger), you append the 
last item in 
self.min
to 
self.min
:
else:
self.min.append(self.min[− 1])
Appending the last item in 
self
.
min
to 
self
.
min
keeps the number of items in 
self.main
the same 
as 
self.min
so that you can keep track of the smallest number in the stack.
Let’s take a look at an example. When you push the first number onto your stack, your two internal 
stacks look like this:
min_stack = MinStack()
min_stack.push(10)
print(min_stack.main)
print(min_stack.min)
>> [10]
>> [10]
Here’s what happens when you push another, bigger number onto your stack:
min_stack.push(15)
print(min_stack.main)
print(min_stack.min)
>> [10, 15]
>> [10, 10]
Notice that 
min_stack.main
is a normal stack, holding items in the order they come onto it:
>> [10, 15]
However, 
min_stack.min
does not keep track of the items as they come onto the stack. Instead, it 
keeps track of whatever the smallest number is. In this case, it has 10 twice:
>> [10, 10]
Fifteen is not in 
min_stack.min
because 15 will never be the smallest item in the stack.
When you call 
get_min
, it returns the last item in 
self.min
, which is the smallest number in 
the stack:
print(min_stack.get_min())
>> 10
In this case, it returns 10.

---

Chapter 11 Stacks
123
After you’ve popped an item, your two stacks look like this:
min_stack.pop()
print(min_stack.main)
print(min_stack.min)
>> [10]
>> [10]
And when you call 
get_min
a second time, the method once again returns 10:
print(min_stack.get_min())
>> 10
When you call 
pop
one last time, both stacks are empty:
min_stack.pop()
print(min_stack.main)
print(min_stack.min)
>> []
>> []
As you can see, 
self.min
kept track of the smallest number in the stack without ever having to 
store the number 15.
Stacked Parentheses
One time, when I was interviewing at a startup, they gave me the following problem: “Given a string, 
use a stack to check whether it has balanced parentheses, meaning every time there is an open paren-
thesis, there is a subsequently closed parenthesis.”
(str(1)) # Balanced
print(Hi!)) # Not balanced
Unfortunately, I messed up my answer badly. Your initial reaction to this problem may be to quickly 
solve it by parsing a string while using one counter for opening parentheses and another counter for 
closing parentheses. If the counters are equal at the end of the string, then the parentheses are bal-
anced. However, what happens if you encounter a string like the following one?
a_string = ")( )("
In this case, your solution will not work.

---