Search⌘ K
AI Features
Home
Courses
Recursion for Coding Interviews in Python

Solution Review: Reverse a Stack

Explore how to reverse a stack using recursion by popping and inserting elements at the bottom without additional data structures. Understand the use of helper functions and recursive calls to manipulate the stack in place, improving efficiency and preparing for coding interviews.

We'll cover the following...

Solution: Using Recursion

Python 3.5
import stack as s
 
def insertAtBottom(stack, item) : # Recursive function that inserts an element at the bottom of a stack.
  # Base case
  if s.isEmpty(stack) :
    s.push(stack, item)
  # Recursive case
  else:
    temp = s.pop(stack)
    insertAtBottom(stack, item)
    s.push(stack, temp) 
def reverse(testVariable) :
  # Recursive case
  if not s.isEmpty(testVariable) :
    temp = s.pop(testVariable)
    reverse(testVariable)
    insertAtBottom(testVariable, temp) 
# Driver Code 
myStack = s.createStack() 
s.push(myStack, str(8)) 
s.push(myStack, str(5)) 
s.push(myStack, str(3)) 
s.push(myStack, str(2)) 
print("Original Stack") 
s.printStack(myStack) 
reverse(myStack) 
print("\n\nReversed Stack") 
s.printStack(myStack)

Explanation

A simple solution to reversing a stack is to create another stack. Pop elements from the old stack into the new stack and we will have the reversed contents in the new stack.

However, the problem statement asked us specifically to not use any other ...