Reverse a String using Stack

Reversing a String using Stack

Reversing a string using a stack involves pushing each character of the string onto the stack and then popping them off the stack to form the reversed string. This utilizes the Last In, First Out (LIFO) property of the stack.

---

Step-by-Step Process

Consider a string:

"hello"

To reverse this string using a stack, follow these steps:

1. Initialize an Empty Stack: Use a stack to keep track of characters.
2. Push Characters onto the Stack: Iterate through each character in the string and push it onto the stack.
3. Pop Characters from the Stack: Pop characters off the stack until the stack is empty, appending each character to the reversed string.

After performing these steps, the string will be reversed:

"olleh"

---

Pseudo Code

Function reverse_string(string):
    # Initialize an empty stack
    stack = []
    # Push each character of the string onto the stack
    For char in string:
        stack.append(char)
    # Initialize an empty string for the reversed result
    reversed_string = ''
    # Pop characters from the stack until it is empty
    While stack:
        reversed_string += stack.pop()
    # Return the reversed string
    Return reversed_string

---

Python Program to Reverse a String using Stack

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

    def push(self, data):
        self.stack.append(data)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        return None

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

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

    def traverse(self):
        for item in reversed(self.stack):
            print(item, end=" -> ")
        print("None")

# Function to reverse a string using a stack
def reverse_string(string):
    stack = Stack()
    # Push each character of the string onto the stack
    for char in string:
        stack.push(char)
    # Initialize an empty string for the reversed result
    reversed_string = ''
    # Pop characters from the stack until it is empty
    while not stack.is_empty():
        reversed_string += stack.pop()
    # Return the reversed string
    return reversed_string

# Example usage:
input_string = "hello"
print(f"Original string: {input_string}")  # Output: hello
reversed_str = reverse_string(input_string)
print(f"Reversed string: {reversed_str}")  # Output: olleh

This Python program defines a stack with methods for pushing, popping, peeking, checking if the stack is empty, and traversing the stack. The reverse_string function uses the stack to reverse a given string by pushing each character onto the stack and then popping them off the stack to form the reversed string.