The Self-Taught Computer Scientist

super
r
e
p
u
s
Stack
repus
Figure 11.3: If you pop off the characters of 
super
, you get 
repus
.

---

Data Structures
120
Here is how to use a stack to reverse a string:
def reverse_string(a_string):
stack = []
string = ""
for c in a_string:
stack.append(c)
for c in a_string:
string += stack.pop()
return string
print(reverse_string("Bieber"))
>> "rebeiB"
Your function 
reverse_string
accepts a string as a parameter:
def reverse_string(a_string):
Inside your function, you use a 
for
loop to push each character onto your stack:
for c in a_string:
stack.append(c)
You then use another loop to iterate through your stack and add each character to your 
a_string
variable as you pop them off your stack:
for c in a_string:
string += stack.pop()
Finally, you return your reversed string:
return string
Min Stack
Another common technical interview challenge is to design a data structure that supports stack oper-
ations such as push and pop and includes a method to return the smallest element. All stack oper-
ations must be O(1). The key to solving this challenge is to use two stacks: a main stack and a min 
stack. Your main stack will keep track of all the push and pop operations, and your min stack will 
keep track of the smallest element in the stack. Learning how to solve this problem isn’t just helpful 
for passing a technical interview: learning how to create a stack that tracks the smallest number is 
helpful in various situations you will encounter in your day- to- day programming.

---