Learn Programming and technology with ease @ developerpublish.com

HomePythonPython Program to Reverse a Stack using Recursion

# 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

### You May Also Like

#### Python Program to Remove Duplicates from a Linked List

In this Python program, we will create a singly linked list and remove duplicate elements from it. A linked list...

#### Python Program to Solve the Celebrity Problem

This Python program solves the Celebrity Problem by finding a person who is known by everyone but does not know...

#### Python Program to Solve n-Queen Problem with Recursion

This Python program uses a recursive approach to solve the n-Queens problem. It explores all possible combinations of queen placements...