Python Program to Reverse a Stack

Approach

We will be implementing the code to reverse a Stack in Python. We will first implement the three famous functions of Stack i.e., push(), pop(), and isEmpty(). After implementing all three functions, we will implement a reverseStack() function to reverse the stack. We will use Recursion to reverse the Stack. First, we will remove all the elements from the Stack one by one and store them in the recursion stack space. After that, we will start pushing these removed elements back to the Stack in a reversed manner.

For example, we have the following elements in the Stack from top to bottom:-

Input: [1, 2, 3]

We will remove all the elements from the Stack and store them in the recursion stack space.

After removing Stack will be empty.

Now we will start to push these elements back to the Stack.

• 1st Iteration:

Since the stack is empty we will directly push 3 to the Stack.

• 2nd Iteration:

We will first empty the Stack and then add 2 to it. Hence, we will remove 3 and store in the recursion stack space and then add 2 and after this add 3 to the Stack again.

• 3rd Iteration:

We will first empty the Stack and then add 1 to it. Hence, we will remove 3, 2 and store them in the recursion stack space and then add 1. Then we will add 2 and then 3 to the Stack again.

In this way, we will reverse the Stack.

Refer to the below implementation for a better understanding of the above approach.

def insertAtBottom(stack, item):
    if isEmpty(stack):
        push(stack, item)
    else:
        temp = pop(stack)
        insertAtBottom(stack, item)
        push(stack, temp)
 
'''
Below is the function that
reverses the given stack
using insertAtBottom()
'''
def reverse(stack):
    if not isEmpty(stack):
        temp = pop(stack)
        reverse(stack)
        insertAtBottom(stack, temp)

''' 
Below is a complete running
program for testing above
functions.
'''

''' 
Function to create a stack.
It initializes size of stack
as 0
'''
def createStack():
    stack = []
    return stack

''' 
Function to check if
the stack is empty
'''
def isEmpty( stack ):
    return len(stack) == 0

''' 
Function to push an
item to stack
'''
def push( stack, item ):
    stack.append( item )

''' 
Function to pop an
item from stack
'''
def pop( stack ):
 
    '''
    If stack is empty
    then error
    '''
    if(isEmpty( stack )):
        print("Stack Underflow ")
        exit(1)
 
    return stack.pop()
 
# Function to print the stack
def prints(stack):
    for i in range(len(stack)-1, -1, -1):
        print(stack[i], end = ' ')
    print()

You can also try this code with Online Python Compiler

Run Code

Time Complexity: O(N^2)

The time complexity of the above approach to reverse a stack is O(N * N) (where ‘N’ is the number of elements in the Stack) because we are first removing each element from the Stack and for each element to insert at the bottom we are again removing all the elements.

Space Complexity:O(1) 

The space complexity for the above approach to reverse a stack is O(1) because we are not using any auxiliary space.

You can also practice with the help of Online Python Compiler

Must Read  C Program to Reverse a Number

Frequently Asked Questions

What is the Time and Space complexity of the approach used to reverse an array?

Time Complexity: The time complexity to reverse a stack is O(N * N) (where N is the number of elements in the Stack) because we are first removing each element from the Stack and for each element to insert at the bottom we are again removing all the elements.

Space Complexity: The space complexity to reverse a stack is O(1) because we are not using any auxiliary space.

What if there is only one element in the Stack?

If there is only one element in the stack, we need to return a Stack containing that element itself.
 

Conclusion

In this blog, we have covered the following things:

1. We first discussed how to reverse a Stack.
2. Then we discussed the time and space complexity of the approach used to reverse a stack.
    

Recommended Reading:

• Fibonacci Series in Python
• Reverse a Stack Using Recursion
• Reverse Words in a Given String

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, DBMS, System Design, Basics of JavaScript, etc. as well as some Contests, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio. You can also consider our Mern Stack Course to give your career an edge over others.

Until then, All the best for your future endeavors, and Keep Coding.