Java program to reverse a string using stack

What is a stack
A stack is a data structure which holds elements in Last-In-First-Out(LIFO) order. This means that the elements which are inserted first on the stack will be removed last and the elements which are inserted last will be removed first.
In simple words, the elements of the stack are retrieved in the reverse order of their insertion.
Though you can create your own custom stack data structure but java provides a built-in java.util.Stack class which can be used as a stack and it can be used to reverse a string.


Reverse characters of a string with stack
A stack can be used to reverse a string in java using the following algorithm.

  1. Push the characters one by one to the stack. Insertion operation in stack is called push.
  2. Initialize an empty string which will hold the reversed string.
  3. Iterate over the stack till it becomes empty.
  4. In every iteration, pop a character and add it to a string initialized in Step 2. Removing an element from a stack is called pop.
  5. When the stack becomes empty, the string created in Step 2 will contain the reversed string.

Java program to reverse a string using stack based on the above steps is given below.

import java.util.Stack;
 
public class StringReverseExample {
 
   public static void main(String[] args) {
      String string = "codippa";
      // create stack
      Stack<Character> stack = new Stack<Character>();
      // iterate over the string
      for (Character character : string.toCharArray()) {
	// push character on stack
	stack.push(character);
      }
      // initialize string to hold the result
      String reversed = "";
      while(!stack.isEmpty()) {
	// pop a character and add it to result
	reversed += stack.pop();
      }
      // print result
      System.out.println("Original string is: " + string);
      System.out.println("Reversed string is: " + reversed);
   }
}

Output is

Original string is: codippa
Reversed string is: appidoc

Though this code works perfectly but there is some problem in the line reversed += stack.pop();. It performs multiple string concatenation operations which is not good.
This is because for every concatenation operation, a new String object is created. This is fine for small strings but for larger strings, it will consume a lot of memory.
To resolve this, use a java.lang.StringBuffer or java.lang.StringBuilder object in place of a String and use its append method to add a character to it.
Thus, modified example will be

import java.util.Stack;
 
public class StringReverseExample {
 
   public static void main(String[] args) {
      String string = "codippa";
      // create stack
      Stack<Character> stack = new Stack<Character>();
      // iterate over the string
      for (Character character : string.toCharArray()) {
         // push character on stack
         stack.push(character);
      }
      // initialize empty StringBuffer to hold the result
      StringBuffer reversed = new StringBuffer("");
      while(!stack.isEmpty()) {
         // pop a character and append it to buffer
         reversed.append(stack.pop());
      }
      // print result
      System.out.println("Original string is: " + string);
      System.out.println("Reversed string is: " + reversed.toString());
   }
}

There are many different methods to reverse a string in java but one using stack is explained in this article. Hit the clap below if it proved to be helpful

0

Mark Your Impression

Close Menu