Solution Review: Reverse a Stack

This review provides a detailed analysis of the solution to reverse a stack using recursion.

We'll cover the following

Solution: Using Recursion

Press + to interact
main.py
stack.py
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(stack) :
  # Recursive case
  if not s.isEmpty(stack) :
    temp = s.pop(stack)
    reverse(stack)
    insertAtBottom(stack, 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 data structure or stack.

This is where recursion comes in the picture. We pop the top element from the given stack. Then recursively call another instance of the same function. When this child function will return back to parent function append the popped element to the bottom of the stack.

In the code snippet above, we have created two functions: reverse() and insertAtBottom().

  1. The reverse() function checks whether the stack is empty or not. If the stack is not empty, we pop the top element and store it in temp variable. We then call reverse() function again on the updated stack. When this child function returns, we call the helper function insertAtBottom().

    What will be the base case for this function?

  1. The insertAtBottom() function recursively inserts an element at the bottom of a stack. If the stack is empty, it simply pushes the item else, it pops the top element and stores in the temp variable. Then call the function again on the updated stack. When this child function returns it pushes temp back in the stack.

Let’s have a look at the sequence of function calls for this code:

Let’s try solving another problem in the next lesson.