Q.Write a program to reverse a string using stack.

Question Shape

This is a code task: write a Python program that uses a stack to reverse a string.

Solution

A stack follows Last-In-First-Out (LIFO) order. When we push each character of a string onto a stack and then pop them all, they emerge in reverse order — the last character pushed (the end of the string) is the first popped.

We can implement the stack using a Python list, where append() acts as push and pop() removes and returns the top element.

def reverse_string(s):
    stack = []
    
    # Push all characters onto the stack
    for char in s:
        stack.append(char)
    
    # Pop all characters to build the reversed string
    reversed_s = ""
    while stack:
        reversed_s += stack.pop()
    
    return reversed_s

# Test the function
original = "HELLO"
reversed_str = reverse_string(original)
print(f"Original: {original}")
print(f"Reversed: {reversed_str}")

Expected Output:

Original: HELLO
Reversed: OLLEH

Key lines explained:

• stack.append(char) pushes each character from left to right. After processing "HELLO", the stack holds ['H', 'E', 'L', 'L', 'O'] with 'O' at the top.
• stack.pop() removes the top element. The first pop gives 'O', the second 'L', and so on, building "OLLEH".
• The while stack: loop continues until the stack is empty, ensuring every character is retrieved.

This approach directly exploits the LIFO property: the character that went in last (the string's end) comes out first, reversing the order.

Why a Stack?

A stack is a Last-In-First-Out (LIFO) data structure. When you push characters of a string onto a stack in order and then pop them all, they come out in reverse order. This makes the stack the natural tool for string reversal: the first character pushed becomes the last one popped.

The algorithm is straightforward:

1. Push each character of the original string onto the stack (left to right).
2. Pop all characters from the stack and concatenate them into a new string.

Because the last character pushed is the first one popped, the result is the reversed string.

Implementation

We can implement this using Python's built-in list as a stack (with append() for push and pop() for pop), or we can write a simple Stack class for clarity.

Approach 1: Using a List as a Stack

def reverse_string(s):
    stack = []
    
    # Push all characters onto the stack
    for char in s:
        stack.append(char)
    
    # Pop all characters to build the reversed string
    reversed_str = ""
    while stack:
        reversed_str += stack.pop()
    
    return reversed_str

# Test
original = "HELLO"
reversed_result = reverse_string(original)
print(f"Original: {original}")
print(f"Reversed: {reversed_result}")

Output:

Original: HELLO
Reversed: OLLEH

Key lines:

• stack.append(char) pushes each character onto the stack in the order they appear.
• stack.pop() removes and returns the top element (the last character pushed), so concatenating these gives the reverse.

Approach 2: Using a Custom Stack Class

For a more structured solution that explicitly shows stack operations:

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()
        return None
    
    def is_empty(self):
        return len(self.items) == 0

def reverse_string(s):
    stack = Stack()
    
    # Push all characters
    for char in s:
        stack.push(char)
    
    # Pop all characters
    reversed_str = ""
    while not stack.is_empty():
        reversed_str += stack.pop()
    
    return reversed_str

# Test
original = "PYTHON"
reversed_result = reverse_string(original)
print(f"Original: {original}")
print(f"Reversed: {reversed_result}")

Output:

Original: PYTHON
Reversed: NOHTYP

The Stack class encapsulates the stack behavior. The is_empty() check ensures we stop popping when the stack is exhausted.

Step-by-Step Trace

For the string "ABC":

The final reversed string is "CBA".

chars = []
while not stack.is_empty():
    chars.append(stack.pop())
reversed_str = "".join(chars)