Reverse String using Stack

This article describes how to reverse a string using a stack. There exist many algorithms to reverse the string.

The idea is to generate a new stack that is empty, and then transfer all of the characters from the string into the new stack. The next step is to remove each character from the stack one at a time and insert them back into the input string, beginning at the index 0 positions. Everyone is aware that stacks function according to the principle of “first in, last out.” The newly formed string would be in the opposite direction once all of the elements had been popped and reattached to the string.

Algorithm to reverse a string using stack

To reverse a string using a stack, you can follow these steps:

• Create an empty stack.
• Push each character of the string onto the stack in sequence.
• Pop each character from the stack and append it to a new string until the stack is empty.
• The new string will be the reverse of the original string.

Consider the following example. Consider the string “GOD”. Iteratively we push one by one character of the string on to stack.

As we know, the stack is LIFO (Last In First Out) data structure, so the first characters we push into the stack will be at the bottom and the last character of the string will be at the top. So when we read the characters from the top of the stack, naturally they will be read out in reverse order. Thus, stack is the natural choice in many routines to reverse the sequence of data.

Once the entire string is pushed into the stack, we start popping one character at a time from the stack and concrete characters in revString. On each pop, one character will be appended at the end of revString, and by the end, entire string appears reverse.

Python code:

class Stack:
    
    def __init__(self):
        self.STACK = []
        self.TOP = -1
        
    def push(self, item):
        self.TOP += 1
        self.STACK.append(item)

        
    def pop(self):
        item = self.STACK[self.TOP]
        self.TOP -= 1
        return item
    
    def reverse(self, String):
        
        for c in String:
            self.push(c)
        
        revString = ""        
        while(len(self.STACK) > 0):
            revString += self.STACK.pop()
            
        return revString
        
            
        
S = Stack()

String = 'Hello Codecrcks'
print('Original String :', String)
print('Reverse String  :', S.reverse(String))

Output:

Original String : Hello Codecrcks
Reverse String  : skcrcedoC olleH

---

YouTube Channel: CodeCrucks