Write a program to reverse a string using stack data structure ?

  • Given a string, reverse it using stack. For example “Wikitechy” should be converted to “yhcetikiW”.
  • Following is simple algorithm to reverse a string using stack.
    • Empty stack to be created.
    • String to stack put one by one push all characters.
    • From the stack and put them back to string one by one pop all characters.
 Reserve a String Using Stack

Sample Code in Java

import java.util.*; 

//stack
class Stack
{
int size;
int top;
char[] a;

//function to check if stack is empty
boolean isEmpty()
{
return (top < 0);
}

Stack(int n)
{
top = -1;
size = n;
a = new char[size];
}

//function to push element in Stack
boolean push(char x)
{
if (top >= size)
{
System.out.println("Stack Overflow");
return false;
}
else
{
a[++top] = x;
return true;
}
}

//function to pop element from stack
char pop()
{
if (top < 0)
{
System.out.println("Stack Underflow");
return 0;
}
else
{
char x = a[top--];
return x;
}
}
}


// Driver code
class Main
{
//function to reverse the string
public static void reverse(StringBuffer str)
{
// Create a stack of capacity
// equal to length of string
int n = str.length();
Stack obj = new Stack(n);

// Push all characters of string
// to stack
int i;
for (i = 0; i < n; i++)
obj.push(str.charAt(i));

// Pop all characters of string
// and put them back to str
for (i = 0; i < n; i++)
{
char ch = obj.pop();
str.setCharAt(i,ch);
}
}

//driver function
public static void main(String args[])
{
//create a new string
StringBuffer s= new StringBuffer("Wikitechy");

//call reverse method
reverse(s);

//print the reversed string
System.out.println("Reversed string is " + s);
}
}

Output

Reversed string is yhcetikiW.

Time Complexity:

  • O(n) where n is number of characters in stack.

Categorized in:

Tagged in:

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,