1.
Introduction
2.
Problem Statement
3.
Approach
4.
4.1.
What is the Time and Space complexity of the approach used to reverse an array?
4.2.
What if there is only one element in the Stack?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Python Program to Reverse a Stack

Nishant Rana
0 upvote

## Introduction

Time and again there are Data Structures and Algorithms have been at the heart of the technical interviews. Data structures such as stacks are among the favorites of interviewers to ask questions. Mastery of data structures would help in solving a huge amount of problems and improve your knowledge of the concepts in general as well. In this article, we will take a look at one of the popular stack problems.

## Problem Statement

We need to reverse a stack of ‘N’ elements. A stack is a linear data structure in which we can add or remove the element from the top of the stack only.

Input 1:

[1, 2, 3, 4, 5]

Output 1:

[5, 4, 3, 2, 1]

## 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()``````

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

### 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.