Python Program to Reverse a Stack using Recursion

This is a Python program to reverse a stack using recursion.

Problem Description

The program creates a stack and allows the user to perform push and pop operations on it.

Problem Solution

1. Create a class Stack with instance variable items initialized to an empty list.
2. Define methods push, pop, is_empty and display inside the class Stack.
3. The method push appends data to items.
4. The method pop pops the first element in items.
5. The method is_empty returns True only if items is empty.
6. The method display prints the elements of the stack from top to bottom.
7. Define function insert_at_bottom which takes a stack and a data item as arguments.
8. The function insert_at_bottom adds the data item to the bottom of the stack using recursion.
9. Define function reverse_stack which takes a stack as argument.
10. The function reverse_stack reverses the stack using recursion.
11. Create an instance of Stack, push data to it and reverse the stack.

Program/Source Code

Here is the source code of a Python program to reverse a stack. The program output is shown below.

class Stack:
    def __init__(self):
        self.items = []
 
    def is_empty(self):
        return self.items == []
 
    def push(self, data):
        self.items.append(data)
 
    def pop(self):
        return self.items.pop()
 
    def display(self):
        for data in reversed(self.items):
            print(data)
 
def insert_at_bottom(s, data):
    if s.is_empty():
        s.push(data)
    else:
        popped = s.pop()
        insert_at_bottom(s, data)
        s.push(popped)
 
 
def reverse_stack(s):
    if not s.is_empty():
        popped = s.pop()
        reverse_stack(s)
        insert_at_bottom(s, popped)
 
 
s = Stack()
data_list = input('Please enter the elements to push: ').split()
for data in data_list:
    s.push(int(data))
 
print('The stack:')
s.display()
reverse_stack(s)
print('After reversing:')
s.display()
Program Explanation

1. An instance of Stack is created.
2. The user is prompted to enter data items to push to the stack.
3. The stack is displayed.
4. The stack is reversed by passing it to the function reverse_stack.
5. The stack is displayed again.

advertisement
advertisement
Runtime Test Cases
Case 1:
Please enter the elements to push: 7 3 1 5
The stack:
5
1
3
7
After reversing:
7
3
1
5
 
Case 2:
Please enter the elements to push: 3
The stack:
3
After reversing:
3
 
Case 3:
Please enter the elements to push: 1 2
The stack:
2
1
After reversing:
1
2

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

Note: Join free Sanfoundry classes at Telegram or Youtube

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.