Python Program to Reverse a Stack using Recursion

In this Python program, we will reverse a stack using recursion. A stack is a data structure that follows the Last In First Out (LIFO) principle, where the last element added is the first one to be removed. Reversing a stack means that the bottom element becomes the top element and vice versa.

Problem Statement

Write a Python program to reverse a given stack using recursion, without using any extra data structures. You are allowed to use the standard stack operations: push, pop, and peek.

Python Program to Reverse a Stack using Recursion

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

def reverse_stack(stack):
    if not stack.is_empty():
        temp = stack.pop()
        reverse_stack(stack)
        insert_at_bottom(stack, temp)

def insert_at_bottom(stack, item):
    if stack.is_empty():
        stack.push(item)
    else:
        temp = stack.pop()
        insert_at_bottom(stack, item)
        stack.push(temp)

# Example usage
if __name__ == "__main__":
    my_stack = Stack()
    my_stack.push(1)
    my_stack.push(2)
    my_stack.push(3)
    my_stack.push(4)

    print("Original Stack:", my_stack.items)
    reverse_stack(my_stack)
    print("Reversed Stack:", my_stack.items)

How it Works

The Stack class represents a basic stack data structure with methods like push, pop, peek, and is_empty. The reverse_stack function uses recursion to reverse the stack by following these steps:

1. Pop an item from the stack.
2. Recursively call reverse_stack on the remaining elements.
3. Insert the popped item at the bottom of the stack using the insert_at_bottom function.

The insert_at_bottom function is responsible for inserting an element at the bottom of the stack using recursion. It pops items from the stack until it reaches an empty stack and then pushes the new item.

Input/Output