Reverse a string using stack in C++
In this tutorial, we will learn to reverse a string using the stack in C++.
For Example:
Given string: " codespeedy"
- Reverse the given string.
Output: " ydeepsdoc''
Simple Method:
- Firstly, create a swap function.
- Then, simply create a reverse function.
- This method will not use any auxiliary space.
Reverse without using stack
Implementation:
// reverse string without stack #include <bits/stdc++.h> #include<iostream> using namespace std; // function to swap two character void swap(char *x, char *y) { char temp = *x; *x = *y; *y = temp; } // to reverse a string void reversestring(char str[]) { // get size int ne = strlen(str), i; for (i = 0; i < ne/2; i++) swap(&str[i], &str[ne-i-1]); } int main() { char str[] = "codespeedy"; reversestring(str); cout<< str; return 0; }
OUTPUT: "ydeepsedoc"
However, it has a high time complexity.
Now, we will solve this problem using a stack.
Moreover, we can directly use STL. In STL, push() and pop() functions are already defined in the header file.
These are some following steps using the stack.
- Firstly, create an empty stack.
- Then, push characters of the string one by one to the empty stack.
- Finally, pop each character from the stack and again, put it into the string.
- The time complexity is O(n) where n is the number of characters in the stack.
- The Auxiliary Space: O(n)
You may also like:
Exception handling in C++
Reverse a string using stack in C++
Hence, below is the implementation of the above approach.
// reverse a string using stack #include<iostream> #include <bits/stdc++.h> using namespace std; // Astructure class Stack { public: int top; unsigned cap; char* arr; }; // create a stack of capacity (given) Stack* createst(unsigned cap) { Stack* st = new Stack(); st->cap = cap; st->top = -1; st->arr = new char[(st->cap * sizeof(char))]; return st; } // Stack will be full when top will equal to the last index int isFull(Stack* st) { return st->top == st->cap - 1; } // Stack will be empty when top will equal to -1 int isEmpty(Stack* st) { return st->top == -1; } // Function to add an item to stack. // It increases top by 1 void push(Stack* st, char character) { if (isFull(st)) return; st->arr[++st->top] = character; } // Function to remove the character char pop(Stack* st) { if (isEmpty(st)) return -1; return st->arr[st->top--]; } void reversestring(char string[]) { // Create a stack int strsm = strlen(string); Stack* st = createst(strsm); // Push all characters for (int i = 0; i < strsm; i++) push(st, string[i]); // Pop all characters for (int i = 0; i < strsm; i++) string[i] = pop(st); } int main() { char string[] = "codespeedy"; reversestring(string); cout<< string; return 0; }
Output Explanation:
INPUT: "codespeedy" OUTPUT: " ydeepsedoc"
Leave a Reply