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"