How to reverse a string using stack?

The data structure stack gives you access to the last data item that you inserted onto the stack. If you delete the last item from the stack, you can access it next to the last item.

Algorithm for Reverse a String using Stack:

  • Initializes a string of length n.
  •  Create a pile of the same size to store the characters.
  • Go through the chain and push all the characters onto the pile one at a time.
  • Go back through, remove the characters, and concatenate them into the string.
  • Print the text reversed.

For example:

reverse

reverse

Here Code:

#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[] = "Programmer's
Academy";  
    reverse(s); 
    cout<<s;  
    return 0; 
}

Complexity Analysis:

  • Time Complexity: O (n) where n is number of characters in string.
  • Auxiliary Space: O (n) because space on the stack was used to store n characters.

Algorithm for Reverse a String Without using Stack:

  • Initializes a string of length n.
  •  Traverses the string to half its length and replaces the character at the current index with the character at position – length – current index – 1.
  • Print the string.

For example:

reverse

Here Code:

#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[] = " Programmer's Academy ";  
    reverse(s);  
    cout<<s;  
    return 0;  
}

Complexity Analysis:

  • Time Complexity: O (n) where n is number of characters in string.
  • Auxiliary Space: O (1) because it uses a certain amount of extra space.

Recommended Articles:

  1. How to split a circular linked list into two halves?
  2. How to reverse a doubly linked list?
  3. How to reverse a linked list?
  4. How to swap nodes in a linked list without Swapping data?
  5. How to delete a node in a linked list at a given Location?

References:

Help Me Please: If you found any error in the content or example please let us know by comment also write your suggestion or if any doubt in the concept please feel free to write us in the comment section.

Practice your Code online here

(Visited 30 times, 1 visits today)

0 0 votes
Article Rating
Subscribe
Notify of
4 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
trackback

[…] How to reverse a string using stack? […]

trackback

[…] How to reverse a string using stack? […]

trackback

[…] How to reverse a string using stack? […]

trackback

[…] How to reverse a string using stack? […]

You cannot copy content of this page
Scroll Up
4
0
Would love your thoughts, please comment.x
()
x

  • Name

  • Minimum length of 8 characters.