# Reverse a String using Stack

Difficulty Level Easy
Frequently asked in Accolite Capgemini Delhivery Fanatics Fourkites
Stack StringViews 6999

We have given a string s of length n which contains lower case letters, upper case letters, integers, and some special symbol. Reverse the given string using stack. Let’s see some examples for better understanding.

## Example

Input

s = “TutorialCup”

Output

puClairotuT

Input

s = “Stack”

Output

kcatS

## Using Stack

### Algorithm for Reverse a String using Stack

1. Initialize a string of length n.
2. Create a stack of the same size to store the characters.
3. Traverse the string and push each and every character into the stack one by one.
4. Traverse again and start popping the characters out and concatenate them together into a string.
5. Print the reversed string.

### Implementation

#### C++ Program

```#include <bits/stdc++.h>
using namespace std;

class Stack{
public:
int top;
unsigned capacity;
char* array;
};

Stack* createStack(unsigned capacity){

Stack* stack = new Stack();
stack->capacity = capacity;
stack->top = -1;
stack->array = new char[(stack->capacity * sizeof(char))];
return stack;
}

int isFull(Stack* stack){
return stack->top == stack->capacity - 1;
}

int isEmpty(Stack* stack){
return stack->top == -1;
}

void push(Stack* stack, char item){
if (isFull(stack))
return;
stack->array[++stack->top] = item;
}

char pop(Stack* stack){
if (isEmpty(stack))
return -1;
return stack->array[stack->top--];
}

void reverse(char s[]){
int n = strlen(s);
Stack* stack = createStack(n);

int i;
for(i = 0; i < n; i++){
push(stack, s[i]);
}

for(i = 0; i < n; i++){
s[i] = pop(stack);
}
}

int main(){
char s[] = "TutorialCup";

reverse(s);
cout<<s;

return 0;
}```
`puClairotuT`

#### Java Program

```import java.util.*;

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

boolean isEmpty(){
return (top < 0);
}

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

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

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

class Main{
public static void reverse(StringBuffer s){
int n = s.length();
Stack obj = new Stack(n);

int i;
for(i = 0; i < n; i++){
obj.push(s.charAt(i));
}

for(i = 0; i < n; i++){
char ch = obj.pop();
s.setCharAt(i,ch);
}
}

public static void main(String args[]){

StringBuffer s= new StringBuffer("TutorialCup");

reverse(s);

System.out.println(s);
}
}```
`puClairotuT`

### Complexity Analysis

Time Complexity: O(n) where n is the number of characters in the string.

Auxiliary Space: O(n) because we used space in the stack to store n characters.

## Without Using Stack

### Algorithm for Reverse a String using Stack

1. Initialize a string of length n.
2. Traverse the string till half of it’s the length and swap the character at the current index with character at length – current index – 1 position.
3. Print the string.

### Implementation

#### C++ Program

```#include <bits/stdc++.h>
using namespace std;

void swap(char *a, char *b){
char temp = *a;
*a = *b;
*b = temp;
}

void reverse(char s[]){

int n = strlen(s), i;

for (i = 0; i < n/2; i++)
swap(&s[i], &s[n-i-1]);
}

int main(){
char s[] = "animatedworld";

reverse(s);
cout<<s;

return 0;
}```
`dlrowdetamina`

#### Java Program

```class stringRev{

static void swap(char a[], int index1, int index2){
char temp = a[index1];
a[index1] = a[index2];
a[index2] = temp;
}

static void reverse(char s[]){

int n = s.length, i;

for(i = 0; i < n/2; i++) {
swap(s, i, n-i-1);
}
}

public static void main(String[] args){

char s[] = "animatedworld".toCharArray();

reverse(s);
System.out.printf(String.valueOf(s));

}
}```
`dlrowdetamina`

### Complexity Analysis for Reverse a String using Stack

Time Complexity: O(n) where n is the number of characters in the string.

Auxiliary Space: O(1) because we are using constant extra space.

References

Translate »